# Seminars & Events for Discrete Mathematics Seminar

##### An approximate version of Hadwiger's conjecture for claw-free graphs

Hadwiger's conjecture states that if a graph is not $t$-colorable then it contains the complete graph on $t+1$ vertices as a minor. The case $t=4$ is equivalent to the four color theorem and the case $t=5$ was proved by Robertson, Seymour, and Thomas with the use of the four color theorem. For $t>5$, the conjecture remains open. Reed and Seymour have also proved that Hadwiger's conjecture holds for line graphs and in a recent work with Maria Chudnovsky we proved that Hadwiger's conjecture holds for a proper superset of the class of line graphs, known as the class of quasi-line graphs (graphs where the neighbor set of every vertex is the union of two cliques).

##### The Maximum Number of Colorings of Graphs of Given Order and Size

Wilf asked in the 1980s about $f(n,m,l)$, the maximum number of $l$-colorings that a graph with $n$ vertices and $m$ edges can have. We essentially solve this problem for $l=3$, in particular proving, for all large $n$, the conjecture of Lazebnik (1989) that if $m\le n^2/4$ then the maximum number of 3-colorings is achieved by a semi-complete biparite graph. This is joint work with Po-Shen Loh and Benny Sudakov.

##### Eliminating cycles in the torus via isoperimetric inequalities

Let $G_{\infty}=(C_m^d)_{\infty}$ denote the graph whose set of vertices is $\{1,\ldots ,m\}^d$, where two distinct vertices are adjacent iff they are either equal or adjacent in $C_m$ in each coordinate. Let $G_{1}=(C_m^d)_1$ denote the graph on the same set of vertices in which two vertices are adjacent iff they are adjacent in one coordinate in $C_m$ and equal in all others. Both graphs can be viewed as graphs of the $d$-dimensional torus. We prove that one can delete $O(\sqrt d m^{d-1})$ vertices of $G_1$ so that no topologically nontrivial cycles remain. This improves an $O(d^{\log_2 (3/2)}m^{d-1})$ estimate of Bollob\'as, Kindler, Leader and O'Donnell.

##### On the Singular Probability of Random Discrete Matrices

Let $n$ be a large integer and $M_n$ be an $n$ by $n$ random matrix whose entries are independent (but not necessarily identically distributed) random variables. The main goal of this paper is to prove a general upper bound for the probability that $M_{n}$ is singular.

For a constant $0<p<1$ and a constant positive integer $r$, we will define a property called $p$-bounded of exponent $r$. Our main result shows that if the entries of $M_n$ satisfy this property, then the probability that $M_n$ is singular is at most $(p^{1/r} + o(1))^n$. Here are a few sample corollaries of this theorem:

##### Quasi-isometries, phase transitions, and other problems in additive number theory

This is a survey of recent work in combinatorial and additive number theory suggested by a problem of Richard Schwartz in metric geometry and geometric group theory. The central object is a group with an infinite set of generators, and the induced metric. Some results and many open problems will be discussed.

##### Coloring triangle-free graphs on surfaces

Let S be a fixed surface, and let k and q be fixed integers. Is there a polynomial-time algorithm that decides whether an input graph of girth at least q drawn in S is k-colorable? This question has been studied extensively during the last 15 years. We will briefly survey known results.

##### Packing cycles with modularity

Erdős and Posa proved that a there exists a function $f$ such that any graph either has $k$ disjoint cycles or there exists a set of $f(k)$ vertices that intersects every cycle. The analogous statement is not true for odd cycles - there exist numerous examples of graphs that do not have two disjoint odd cycles, and yet no bounded number of vertices intersects every odd cycle. However, Reed has given a partial characterization of when there does not exist a bounded size set of vertices intersecting every odd cycle.

##### On simple additive configurations in random sets

We show that with high probability a random subset of $[n]$ of size $\theta(n^{1-1/k})$ contains two elements $a$ and $a+d^k$, where $d$ is a positive integer. As a consequence, we prove an analogue of the Sarkozy-Furstenberg theorem for a random subset of $[n]$.

##### Square-paths and square-cycles in graphs with high minimum degree

We investigate under which minimum-degree condition does a graph G contain a square-path and a square-cycle of a given length. We give precise thresholds, assuming that the order of G is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B, 67(2), 167-182, 1996] and of Komlos, Sarkozy, and Szemeredi [Random Structures Algorithms, 9(1-2), 193-211, 1996] concerning containment of a spanning square-path and a spanning square-cycle, respectively. Joint work with P. Allen and J. Bottcher.

##### Randomness extractors - applications and constructions

We will investigate the minimal requirements from a random source under which it is potentially useful for generating perfect randomness. The efficient procedures which utilize such sources, "randomness extractors", turn out to have amazing pseudorandomness properties and are useful in numerous contexts. We'll demonstrate applications in complexity theory, error correction and network design. We'll also describe some constructions of near optimal extractors, with tools from expander graphs and the recent proof of the Kakeya conjecture in finite fields.

##### Finding Lovasz's Needle in an Exponential Haystack

The Lovasz Local Lemma is a subtle and far-reaching probability lemma. Roughly, given a large number of bad events which are "mostly" independent it sieves out an instance when none of the bad events occur. As an illustrative example, consider a huge family of 10-element sets, where each set overlaps at most 100 others. We color randomly red and blue and for each set e there is a bad event that e is monochromatic. The conclusion is the existence of a coloring where none of the e are monochromatic. In theory. But if there are n sets a random coloring only has exponentially small chance of succeeding. Finding a polynomial time algorithmic implementation has proven elusive. There were some results of Jozsef Beck and Noga Alon in the early 1990s but they had limited application.

##### New bounds on the size of Kakeya sets in finite fields

A Kakeya set is a set in $(F_q)^n$ (the $n$ dimensional vector space over a field of $q$ elements) which contains a line in every direction. In this talk I will present a recent result which gives a lower bound of $(q/2)^n$ on the size of such sets. This bound is tight to within a multiplicative factor of two from the known upper bounds. The proof extends the polynomial method used in [Dvir 08, Saraf Sudan 08] and uses polynomials of unbounded degree. If time allows I will also discuss the applications to the explicit construction of mergers that follow from our techniques.

Joint work with Kopparty, Saraf and Sudan (arxiv paper: "Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers").

##### Inverse Littlewood-Offord theory, Smooth Analysis and the Circular Law

A corner stone of the theory of random matrices is Wigner's semi-circle law, obtained in the 1950s, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random hermitian matrix with iid (upper diagonal) entries follows the semi-circle law. The non-hermitian case is the famous Circular Law Conjecture, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random matrix with iid entries is uniform in the unit circle.

##### Avoiding small subgraphs in Achlioptas processes

Consider the following random process. At each round, one is presented with two random edges from the edge set of the complete graph on n vertices, and is asked to choose one of them. The selected edges are collected into a graph, which thus grows at the rate of one edge per round. This is known in the literature as an Achlioptas process, and has been studied by many researchers, mainly in the context of delaying or accelerating the appearance of the giant component.

##### The number of 3-SAT functions

We are interested in the number, say $G(k,n)$, of k-SAT functions of $n$ variables (a k-SAT function being a Boolean function representable by a k-SAT formula in, say, conjunctive normal form).

We show that $G(3,n)$ is asymptotic to $2^{n + {n \choose 3}}$, a strong form of a conjecture of Bollobas, Brightwell and Leader.

(The corresponding result for 2-SAT was conjectured by BB&L, and proved by Peter Allen and (independently but later) by the present authors. As usual, the case $k=2$ doesn't seem to shed much light on larger $k$, while one expects (hopes) that $k=3$ is about as hard to handle as a general fixed $k$.) Joint with Liviu Ilinca

##### Linear Programming Relaxations for the TSP

The most successful solution approaches to the traveling salesman problem are based on lower bounds obtained from linear programming relaxations. We will discuss a number of open problems concerning this approach, with emphasis on topics that could improve the practical performance of LP-based algorithms.

##### Geometric selection theorems

In combinatorial geometry one frequently wants to select a point or a set of points that meets many simplices of a given family. The two examples are choosing a point in many simplices spanned by points of some $P$ in $R^d$, and choosing a small set of points which meets the convex hull of every large subset of $P$ (the weak epsilon-net problem). I will present a new class of constructions that yield the first nontrivial lower bound on the weak epsilon-net problem, and improve the best bounds for several other selection problems. Joint work with Jiří Matoušek and Gabriel Nivasch.

##### Packing seagulls in graphs with no stable set of size three

Hadwiger's conjecture is a well known open problem in graph theory. It states that every graph with chromatic number $k$, contains a certain structure, called a "clique minor" of size $k$. An interesting special case of the conjecture, that is still wide open, is when the graph $G$ does not contain three pairwise non-adjacent vertices. In this case, it should be true that $G$ contains a clique minor of size $t$ where $t\geq |V(G)|/2$. This remains open, but Jonah Blasiak proved it in the subcase when $|V(G)|$ is even and the vertex set of $G$ is the union of three cliques. Here we prove a strengthening of Blasiak's result: that the conjecture holds if some clique in $G$ contains at least $|V(G)|/4$ vertices.