# Seminars & Events for Discrete Mathematics Seminar

##### Expansion of Random Graphs - New Proofs, New Results

We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on deep results from combinatorial group theory. It applies to both regular and irregular random graphs. Let G be a random d-regular graph on n vertices. It was conjectured by Alon (86) and proved by Friedman (08) in a ~100 page-long booklet that the highest non-trivial eigenvalue of G is a.a.s. arbitrarily close to 2\sqrt(d-1). We give a new, substantially simpler proof, that nearly recovers Friedman’s result. This approach also has the advantage of applying to a more general model of random graphs, concerning also non-regular graphs. Friedman (2003) extended Alon’s conjecture to this general case, and we obtain new, nearly optimal results here too.

##### Excluding topological minors and well-quasi-ordering

Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation and the weak immersion relation. In other words, given infinitely many graphs, one graph contains another as a minor (or a weak immersion, respectively). Unlike the relation of minor and weak immersion, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980s that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated. We will sketch the idea of our recent proof of this conjecture. In particular, we will give a structure theorem for excluding a fixed graph as a topological minor.

##### Bipartite decomposition of graphs

For a graph G, let bc(G) denote the minimum possible number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to (exactly) one of them. The study of this quantity and its variants received a considerable amount of attention and is related to problems in communication complexity and geometry. After a brief discussion of the background and earlier results on the subject I will focus on the problem of determining the typical value of bc(G) for the binomial random graph G=G(n,p), showing that a conjecture of Erdos about it is false, and suggesting a modified version. Partly based on joint work with Tom Bohman and Hao Huang.

##### Local and global colorability of graphs

It is shown that for any fixed c > 2 and r, the maximum possible chromatic number of a graph on n vertices in which every subgraph of radius at most r is c-colorable is equal to n^{1/(r+1)} up to a factor poly-logarithmic in n. The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random n-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius r in it are 2-degenerate. Joint work with Noga Alon.

##### Coloring digraphs with forbidden cycles

Let k and r be integers with k>1 and k\ge r>0. (Please click on seminar title for complete abstract.)

##### Stein's conjecture and other fair representation problems

Stein's conjecture states that if an n x n matrix has entries 1...n, where each symbol appears exactly n times, then there exists a generalized diagonal where all but two symbols appear exactly once. I will talk about this conjecture and other settings in which we look for a small structure proportionally representing the bigger structure from which it is taken.

##### Few distinct distances and perpendicular bisectors

Let d(n) be the smallest number of distinct distances determined by any set of n points in the real plane. For n sufficiently large, is each set of n points that determines d(n) distances the intersection of an equalateral triangular lattice with a convex set? Is there at least a line that contains n^ε points, for some ε>0? Erdős asked these questions 30 years ago, and an argument due to Szemerédi shows that, if P is a set of points that determines n/k distances, then the perpendicular bisector of some pair of the points must be incident to k of the points. I will present an upper bound on the number of quadruples (x,y,z,w) among a set of points such that the perpendicular bisector of (x,y) is the same as the bisector of (z,w).

##### Saturation in the hypercube

A subgraph of the d-dimensional cube Qd is (Qd,Qm)-saturated if it does not contain a copy of Qm, but adding any missing edge creates a copy of Qm. The subgraph is weakly (Qd,Qm)-saturated if we can add the missing edges one at a time, creating a new copy of Qm at each step. Answering a question of Johnson and Pinto, we show that for every fixed m, the minimum number of edges in a (Qd,Qm)-saturated graph is \Theta(2^d). We also determine exactly the minimum number of edges in a weakly (Qd,Qm)-saturated subgraph of Qd, and raise some further questions. Joint work with Natasha Morrison and Jonathan Noel.

##### On the number of rich lines in truly high dimensional sets

We prove a new upper bound on the number of r-rich lines (lines with at least r points) in a `truly' d-dimensional configuration of points v_1,...,v_n over the complex numbers. More formally, we show that, if the number of r-rich lines is significantly larger than n^2/r^d then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor r^d can be replaced with a tight r^{d+1}. If true, this would generalize the classic Szemeredi-Trotter theorem which gives a bound of n^2/r^3 on the number of r-rich lines in a planar configuration. This conjecture was shown to hold in R^3 in a seminal work of Guth and Katz (2010) and was recently proved over R^4 (under some additional restrictions) by Solomon and Sharir. Although our bound is not optimal, it is the first to hold in arbitrary dimension.

##### TBA - Parzanchevski

##### Colouring graphs without odd holes

Gyarfas conjectured in 1985 that if G is a graph with no induced cycle of odd length at least 5, then the chromatic number of G is bounded by a function of its clique number. We present a proof of this conjecture, in joint work with Paul Seymour. We also discuss some further results, with Maria Chudnovsky and Paul Seymour.

##### Sylvester-Gallai for arrangements of subspaces

In this work we study arrangements of k-dimensional subspaces V_1,...,V_n over the complex numbers. Our main result shows that, if every pair V_a,V_b of subspaces is contained in a dependent triple (a triple V_a,V_b,V_c contained in a 2k-dimensional space), then the entire arrangement must be contained in a subspace whose dimension depends only on k (and not on n). The theorem holds under the assumption that any pair of subspaces intersect only at zero (otherwise it is false). This generalizes the Sylvester-Gallai theorem (or Kelly's theorem for complex numbers), which proves the k=1 case. One of the main ingredients in the proof is a strengthening of a Theorem of Barthe (from the k=1 to k>1 case) proving the existence of a linear map that makes the angles between pairs of subspaces large on average.

##### 5-critical triangle-free graphs

A graph G is k-critical if G is not (k-1)-colorable but every proper subgraph of G is (k-1)-colorable. A natural question is what is asymptotically the minimum average degree in a k-critical graph. In the 60's it was conjectured that a construction of Ore gives the best possible answer. Recently, Kostochka and Yancey proved this conjecture by showing that k-critical graphs have average degree at least (asymptotically) k - 2/(k-1). One may wonder if the lower bound can be improved if certain subgraphs are forbidden. We prove this is true for k=5 when forbidding triangles.

##### Dimension and matchings in comparability and incomparability graphs

In the combinatorics of posets, many theorems are in pairs, one for chains and one for antichains. Typically, the statements are exactly the same when roles are reversed, but the proofs are quite different. The classic pair of theorems due to Dilworth and Mirsky were the starting point for this pattern, followed by the more general pair known respectively as the Greene-Kleitman and Greene theorems dealing with saturated partitions. More recently, a new pair has been discovered dealing with matchings in the comparability and incomparability graphs of a poset. We show that if the dimension of a poset P is d and d is at least 3, then there is a matching of size d in the comparability graph of P, and a matching of size d in the incomparability graph of P.

##### Spectral theory of simplicial complexes

**Note the ***LATE START*** because of the conflict with the Morse lecture.** While spectral graph theory is a well established and fortuitous field, its higher dimensional analogue is still in its infancy. I will explain some approaches to the definition of a spectral theory for simplicial complexes, their applications to combinatorial questions, and examples such as random and Ramanujan complexes.

##### New advances in the Erdos-Hajnal conjecture

The celebrated open Erdos-Hajnal conjecture states that for every undirected graph H there exists epsilon(H)>0 such that every H-free undirected n-vertex graph contains a clique or a stable set of size at least n^{epsilon(H)}. (``H-free'' means it does not contain H as an induced subgraph.) A weaker version of the conjecture states that if one excludes both H and its complement H^{c} then there is a clique or a stable set of size at least n^{epsilon(H)}. This version is also open. There is also an equivalent directed variant of the conjecture, where undirected graphs are replaced by tournaments and cliques/stable sets by transitive subtournaments. In this talk I will present some new results regarding the conjecture.

##### On a problem of Erdos and Moser

A set A of vertices in an r-uniform hypergraph H is ``covered'' in H if, for every (r−1)-set B contained in A, the set B+{u} is an edge of H. Erdos and Moser (1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs. Joint work with Bela Bollobas.

##### Arithmetic Tutte polynomials and quasi-polynomials

We will introduce two invariants called the arithmetic Tutte polynomial and the Tutte quasi-polynomial, and we will survey their several applications, including: - generalization of graph colorings and flows to cellular complexes of higher dimension; - combinatorial and topological invariants of toric arrangements; - Ehrhart polynomials of zonotopes; - Hilberts series of some modules related to the vector partition function. The talk is partially based on joint work of the speaker with Petter Brändén, Michele D'Adderio and Alex Fink.

##### The list decoding radius of Reed-Muller codes over small fields

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well-studied codes, like Reed-Solomon or Reed-Muller codes. The Reed-Muller code F(n,d) for a finite field F is defined by n-variate degree-d polynomials over F. As far as we know, the list decoding radius of Reed-Muller codes can be as large as the minimal distance of the code. This is known in a number of cases: --The Goldreich-Levin theorem and its extensions established it for d=1 (Hadamard codes); --Gopalan, Klivans and Zuckerman established it for the binary field; --and Gopalan established it for d=2 and all fields.

##### Spectral theory of simplicial complexes

While spectral graph theory is a well established and fortuitous field, its higher dimensional analogue is still in its infancy. I will explain some approaches to the definition of a spectral theory for simplicial complexes, their applications to combinatorial questions, and examples such as random and Ramanujan complexes.