# Seminars & Events for Discrete Mathematics Seminar

##### Unfriendly partition of graphs without an infinite subdivided clique

In this talk I prove that every graph with less than $\aleph_\omega$ vertices, which does not contain a subdivision of an infinite clique as a subgraph, must have a partition of its vertices to two sets, so that no vertex has more neighbors in its own set than in the other set. The proof uses the theorem given by Robertson Seymour and Thomas (http://www.ams.org/mathscinet/pdf/1079057.pdf), saying that such a graph has a tree decomposition with certain properties. The unfriendly partition is then constructed by analyzing some infinite game played on this tree.

##### Asymptotic extremal graph theory is non-trivial

Many fundamental theorems in extremal graph theory can be expressed as linear inequalities between homomorphism densities. Lovasz and, in a slightly different formulation, Razborov asked whether it is true that every such inequality follows from a finite number of applications of the Cauchy-Schwarz inequality. In this talk we will show that the answer to this question is negative. Further, we will show that the problem of determining the validity of a linear inequality between homomorphism densities is undecidable. Hence such inequalities are inherently difficult in their full generality. These results are joint work with Hamed Hatami.

##### Bounding chromatic number for graphs in Forb*(bull)

Given a graph $H, Forb(H)$ is the class of all graphs that do not contain $H$ as an induced subgraph, and $Forb^*(H)$ is the class of all graphs that do not contain any subdivision of $H$ as an induced subgraph. A class $\Gamma$ of graphs is $\chi$-bound if there exists a function $f : N \rightarrow N$ (called a $\chi$-binding function for $\Gamma$) such that for all $G \in \Gamma, \chi(G) \leq f(\omega(G))$. $\chi$-bound classes of graphs were introduced in 1987 by András Gyárfás as a generalization of the class of perfect graphs. Gyárfás conjectured that for any tree $T$, the class $Forb(T)$ is $\chi$-bound. In 1997, Alex Scott proved a 'topological' version of this conjecture: for any tree $T$, the class $Forb^*(T)$ is $\chi$-bound; he then conjectured that for every graph $H$, the class $Forb^*(H)$ is $\chi$-bound.

##### Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for any first-order sentence $F$ in the theory of graphs, the probability that the random graph $G(n, p)$ satisfies $F$ approaches either 0 or 1 as $n$ grows. It is well known that this law fails to hold for properties involving parity phenomena (oddness/evenness): for certain properties, the probability that $G(n, p)$ satisfies the property need not converge, and for others the limit may be strictly between 0 and 1.

In this talk, I will discuss the behavior of FO[parity], first order logic equipped with the parity quantifier, on random graphs. Our main result is a "modular convergence law" which precisely captures the behavior of FO[parity] properties on large random graphs.

##### Nearly Tight Low Stretch Spanning Trees

We prove that any graph $G$ on $n$ vertices has a distribution over its spanning trees such that for any edge $(u,v)$ the expected stretch $E_T[d_T(u,v)]$ is bounded by $\tilde{O}(\log n)$. Our result is obtained via a new approach of building ``highways'' between portals and a new strong diameter probabilistic decomposition theorem. Joint work with Ittai Abraham and Yair Bartal

##### The size Ramsey number of a directed path

Given a graph $H$, the size Ramsey number $r_e(H,q)$ is the minimal number m for which there is a graph $G$ with $m$ edges such that every $q-coloring$ of $G$ contains a monochromatic copy of $H$. We study the size Ramsey number of the directed path of length $n$ in oriented graphs, where no antiparallel edges are allowed. We give nearly tight bounds for every fixed number of colors. For the case of two colors we show that there are constants $c_1,c_2$ such that $\frac{c_1 n^{2} \log n}{(\log\log n)^3} \leq r_e(P_n,2) \leq c_2 n^{2}(\log n)^2$.

Joint work with Michael Krivelevich and Benny Sudakov.

##### Unbalanced Allocations

Recently, there has been much research on processes that are mostly random, but also have a small amount of deterministic choice; e.g., Achlioptas processes on graphs. This talk builds on the balanced allocation algorithm first described by Azar, Broder, Karlin and Upfal. Their algorithm (and its relatives) uses randomness and some choice to distribute balls into bins in a balanced way. Here is a description of the opposite family of algorithms, with an analysis of exactly how unbalanced the distribution can become.

##### Hypergraph Turan Problem

The Turan function $ex(n,F)$ of a k-graph $F$ is the maximum number of edges in an $F$-free k-graph on $n$ vertices. This problem goes back to the fundamental paper of Turan from 1941 that solved it for complete graphs (k=2). Unfortunately, very few non-trivial instances of the problem have been solved when we consider hypergraphs (k>2).

We survey some recent results and methods on the hypergraph Turan function. In particular, we discuss the so-called stability approach that greatly helps in obtaining exact results from asymptotic computations (for example, those that use flag algebras or graph limits).

##### Hypergraph list coloring and Euclidean Ramsey Theory

A hypergraph is simple if it has no two edges sharing more than a single vertex. It is $s$-list colorable if for any assignment of a list of $s$ colors to each of its vertices, there is a vertex coloring assigning to each vertex a color from its list, so that no edge is monochromatic. I will discuss a recent result, obtained jointly with A. Kostochka, that asserts that for any $r$ and $s$ there is a finite $d=d(r,s)$ so that any $r$-uniform simple hypergraph with average degree at least $d(r,s)$ is not $s$-list-colorable. This extends a similar result for graphs, and has some geometric Ramsey-type consequences.

##### Higher-order Fourier analysis of $F_p^n$ and the complexity of systems of linear forms

We study the density of small linear structures (e.g. arithmetic progressions) in subsets $A$ of the group $F_p^n$. It is possible to express these densities as certain analytic averages involving $1_A$, the indicator function of $A$. In the higher-order Fourier analytic approach, the function $1_A$ is decomposed as a sum $f_1+f_2$ where $f_1$ is structured in the sense that it has a simple higher-order Fourier expansion, and $f_2$ is pseudorandom in the sense that the kth Gowers uniformity norm of $f_2$, denoted $|f_2\|_{U^k}$, is small for a proper value of $k$.

##### Proving the Lovász-Plummer conjecture

In the 1970s, Lovász and Plummer conjectured that every cubic bridgeless graph has exponentially many perfect matchings with respect to the number of vertices. The conjecture was proven by Voorhoeve for bipartite graphs and by Chudnovsky and Seymour for planar graphs. In this talk I will describe our proof of the general case, which uses elements of both aforementioned partial results as well as Edmonds' characterization of the perfect matching polytope. This is joint work with Louis Esperet, Frantisek Kardos, Daniel Kral, and Sergey Norin.

##### Concrete mathematical incompleteness

An unprovable theorem is a theorem about basic mathematical objects that can only be proved using more than the usual axioms for mathematics (ZFC = *Zermelo Frankel set theory with the Axiom of Choice*) — and that has been proved using standard extensions of ZFC generally adopted in the mathematical logic community. The highlight of the talk is the presentation of a new unprovable theorem concerning the structure of maximal cliques in certain graphs on Cartesian powers of the rational numbers. We first review some previous examples of unprovable theorems. 1-5 are unprovable in the weaker sense that any proof demonstrably requires some use of logical principles transcendental to the problem statement. These previous contexts include

##### Choice numbers and coloring numbers - the infinite case

The *choice number* or *list-chromatic number* $\chi_\ell(G)$ of a graph $G=(V,E)$ is the minimum $k$ such that for every assignment of a list $s(v)$ of $k$ colors to each $v\in V$ there exists a proper coloring $c$ of $V$ that colors each $v$ by a color from $s(v)$. The *coloring number* $col(G)$ of $G$ is the minimum $k$ such that there is an enumeration $V=\{v_0,v_1,\dots,v_{n-1}\}$ satisfying that for each $i<n$ the vertex $v_i$ has fewer than $k$ neighbors among $\{v_j:j<i\}$. For every $G$ it holds that $\chi(G)\le\chi_\ell(G)\le col(G)$ (where $\chi(G)$ is the usual *chromatic number* of $G$.)

##### Phase Transitions of Achlioptas Processes

Achlioptas processes are a class of modifications of the Erdős–Rényi random graph. At each step of an Achlioptas process we add one of two randomly selected edges to the graph according to a fixed rule. We present new results on the phase transitions of a group of Achlioptas processes called 'bounded-size rules' and show that qualitatively, these processes belong to the same class as the Erdős–Rényi process. The results include the size and structure of small components in the barely sub- and supercritical time periods. We will also discuss another type of Achlioptas process that seems to exhibit markedly different behavior at the phase transition.

##### Cops and robbers in random graphs

We will study the following game known as cops and robbers. There is a finite, connected, undirected graph $G$, and $m$ cops and one robber. At the start, each cop chooses one vertex, and then the robber makes his choice of a vertex. Then they move alternately (first the cops then the robber). In the cops' turn, each cop may move to an adjacent vertex, or remain where he is, and similarly for the robber. The cops win the game if one of the cops catches the robber, i.e. lands on the same vertex. We denote by $c(G)$ the 'cop-number' of $G$, meaning the minimal $m$ such that $m$ cops have a winning strategy in $G$, and by $c(n)$ the maximum of $c(G)$ over all graphs with $n$ vertices. Maamoun and Meyniel determined the cop-number for grids. Aigner and Fromme proved that in the case of planar graphs three cops can catch the robber.

##### Color 6-critical graphs on surfaces

We give a simple proof of a theorem of Thomassen that for every surface S there are only finitely many 6-critical graphs that embed in S. With a little bit of additional effort we can bound the number of vertices of a 6-critical graph embedded in S by a function that is linear in the genus of S. This is joint work with Luke Postle.

##### Rank bounds for design matrices with applications

We prove a lower bound on the rank of sparse matrices whose pattern of zeros and non zeros satisfies a certain 'design' like property. Namely, if the intersections of the supports of different columns are small compared to the size of the individual supports. This bound holds over fields of large characteristic or characteristic zero. As an application of this bound we get new robust generalizations of the well-known Sylvester-Gallai theorem which limits the way lines can intersect in $R^d$. Another application is an impossibility result for 2-query Locally-Correctable-Codes (LCCs) over fields of large characteristic. These codes, which do exist over fields of small characteristic, play an important role in theoretical computer science and understanding the limitations of q-query codes (for arbitrary q) is a major open problem.

##### Linear systems modulo composites

Computation modulo composite numbers is much less understood than computation over primes; and sometimes surprisingly much more powerful. A positive example is that the best construction of locally decodable codes known today heavily relies on computations modulo composites. A negative one if that while strong lower bounds are known for constant-depth circuits using $AND$, $OR$ and $MOD_5$ gates, no such lower bounds are known if the $MOD_5$ gates are replaced by $MOD_6$ gates. We consider in this work a restricted model of computation: linear systems modulo composites. This model was explicitly given by Beigel and Maciel (Complexity 97) as a barrier towards proving lowers bounds for computation modulo composites (i.e. ACC0). We completely resolve their problem in this work.

##### Tournament heroes

The chromatic number of a tournament $T4 is the smallest number of transitive tournaments that partition $V(T)$. Let us say that a tournament $S$ is a hero if for every tournament $T$ not containing $S$, the chromatic number of $T$ is at most a constant $c(S)$. Recently, in joint work with Eli Berger, Krzysztof Choromanski, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour and Stephan Thomasse, we proved a theorem that gives a complete description of all heroes. This talk will describe the result, and survey some of the proof ideas.

##### The group number function: the number of groups of a given order

The group number, gnu(n) of n, is defined to be the number of groups of order n. It is now known for all n < 211. I shall discuss the peculiar properties of this function and of the related function moa(n), defined to be the least number N for which gnu(N)=n.