# Seminars & Events for Discrete Mathematics Seminar

##### Maximising the number of induced cycles

How many holes can a graph on n vertices contain? How many induced cycles? For sufficiently large n, we determine the maximum number of induced cycles, the maximum number of holes, and the maximum number of

even or odd induced cycles, and in each case characterize the graphs achieving this bound. This answers a question of Tuza, and a conjecture of Chvatal and Tuza from 1988. Joint work with Natasha Morrison.

##### Recent advances in explicit constructions of Ramsey graphs

In his 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of (2 log n)-Ramsey graphs on n vertices. Matching Erdős' result with a constructive proof is an intriguing problem in combinatorics that has gained a significant attention in the literature. In this talk we will present recent works towards this goal.

##### Symmetric intersecting families

A family of sets is said to be intersecting if any two sets in the family have nonempty intersection. Families of sets subject to various intersection conditions have been studied over the last fifty years and a common feature of many of the results in the area is that the extremal families are often quite asymmetric. Motivated by this, Peter Frankl conjectured in 1981 that symmetric intersecting families must be very small; more precisely, Frankl conjectured that a family of subsets of {1, 2,..., n} where any three sets intersect must have size o(2^n) if its automorphism group is transitive. In this talk, I shall prove this conjecture. Based on joint work with David Ellis.

##### Complexity-separating graph classes for vertex, edge and total colouring

Given a class A of graphs and a decision problem X belonging to NP, we say that a full complexity dichotomy of A was obtained if one describes a partition of A into subclasses such that X is classified as polynomial or NP-complete when restricted to each subclass. The concept of full complexity dichotomy is particularly interesting for the investigation of NP-complete problems: as we partition a class A into NP-complete subclasses and polynomial subclasses, it becomes clearer why the problem is NP-complete in A. The class C of graphs that do not contain a cycle with a unique chord was studied by Trotignon and Vušković who proved a structure theorem which led to solving the vertex-colouring problem in polynomial time.

##### Assessing significance in a Markov chain without mixing

We will describe a new statistical test to demonstrate outlier status for a state of any reversible Markov Chain. Remarkably, the test can rigorously demonstrate outlier status without any bounds on the mixing time of the chain. With an eye on November 8, we will describe an application of our test to representative democracy. This is joint work with Maria Chikina and Alan Frieze.

##### Diameter bounds for Cayley graphs of finite simple groups of large rank

Given any non-abelian finite simple group G and any generating set S, it is conjectured by Laszlo Babai that its Cayley graph should always have diameter (log|G|)^O(1). This conjecture has been verified for all finite simple groups of Lie type with bounded rank, but little progress has been made in the cases with large rank. Motivated by the methods of Babai and Seress for symmetric groups, we obtained an improved diameter bound of q^O(n(log n + log q)^3) for finite simple groups of Lie type with large rank. Joint work with Arindam Biswas from University of Paris-Sud.

##### Three graph classes: mock threshold, cute, and nice graphs

A graph class, defined in one way, can be characterized in several other ways. Forbidden induced subgraphs, intersection of subobjects, relationship among invariants, and vertex ordering are some of the most common ways. A graph is mock threshold if every induced subgraph of it has a vertex with degree or codegree at most 1. I will present the forbidden induced subgraph characterization for this class due to Richard Behr, Thomas Zaslavsky, and myself. A graph is cute if every induced cycle in it is a triangle or a quadrilateral. We discuss chi-boundedness, recognition and optimization for this class. A graph is nice if the difference between the chromatic number and clique number is either 0 or 1 for every induced subgraph of it. Perfect graphs, planar graphs, tripartite graphs, and line graphs are nice.

##### The union-closed sets conjecture

The union-closed sets conjecture is an elementary problem posed by Frankl in 1979. It goes like this: for any finite family of finite sets, closed under taking union, there exists an element that belongs to at least half of the sets in the family. This problem attracted recent interest for being a polymath project. I will explain important partial results and discuss a graph-theoretic reformulation of the conjecture. Based on joint work with Henning Bruhn, Jan-Arne Telle and Pierre Charbit.

##### Matrices with large permanent

The permanent of a matrix has long been an important quantity in combinatorics and computer science, and more recently it has also had applications to physics and linear-optical quantum computing. A result of Gurvits bounds the permanent of an n by n matrix in terms of its operator norm via |perm(A)| \leq |A|^n, and he characterized the matrices for which this is tight (they are essentially just scalar multiples of permutation matrices except that each entry can be replaced by anything with the same modulus).

##### Capsets, sunflower-free sets in {0,1}^n, and the slice rank method

We call a family of sets F "sunflower-free'' if for every three of its sets, some element belongs to exactly two of them. In this talk we will look at the recent breakthrough of Ellenberg and Gijswijt and Croot, Lev and Pach, which used polynomial method to obtain exponential upper bounds for the ``capset problem'', that is, upper bounds for the size of the largest set in GF(3)^n which contains no three term arithmetic progression. In particular we will look at Tao's reformulation of this approach using the so-called "Slice Rank Method," and apply it directly to the Erdos-Szemeredi sunflower problem, proving an exponential upper bound for the size of any sunflower-free family of subsets of {1,2,…,n}.

##### Improperly coloring K_t minor-free graphs

We show that for every t > 0 there exists a constant c=c(t) such that, if a graph G does not contain K_t as a minor, then its vertex set can be partitioned into at most t-1 parts such that every part induces a subgraph with maximum component of size at most c. This relaxation of Hadwiger's conjecture improves previous results of Kawarabayashi and Mohar, Wood, and Liu and Oum, who proved that the same conclusion holds for partitions into 31t/2, 7t/2 and 3t parts respectively. We also discuss applications of our results to extremal questions on bootstrap percolation for minor-closed graph families. Based on joint work with Zdenek Dvorak.

##### Independent sets, local algorithms and random regular graphs

An ''ndependent set'' in a graph is a set of vertices that have no edges between them. How large can an independent set be in a random d-regular graph? How large can it be if we are to construct it using a (possibly randomized) algorithm that is local in nature? I will discuss a notion of local algorithms for combinatorial optimization problems on large, random d-regular graphs. Then I will explain why, for asymptotically large d, local algorithms can only produce independent sets of size at most half of the largest ones. The factor of 1/2 turns out to be optimal. Joint work with Balint Virag.

##### The Kelmans-Seymour conjecture

Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of K_5. This conjecture was proved by Ma and Yu for graphs containing K_4^-. Recently, we proved the Kelmans-Seymour conjecture for all graphs. In this talk, I will give a sketch of our proof, and discuss related problems. This is joint work with Dawei He and Xingxing Yu.

##### The intersection of two matroids

If M and N are two matroids on the same ground sets, we can speak of the intersection of the two matroids, i.e., the set of sets that are independent both in M and in N. This structure turns out to be quite useful in combinatorics. For example, many problems of a matching in a hypergraph or of a rainbow matching in a graph can be translated into the language of the intersection of two matroids. I will discuss several results and conjectures about the intersection of two matroids, and compare them to what is known about one matroid. Some of the results use topological properties of the intersection of two matroids (viewed as a simplicial complex) which I will describe briefly.

##### Distance-uniform graphs with large diameter

We say that a graph is epsilon-distance-uniform if there is a value d (called the critical distance) such that, for every vertex v, all but an epsilon fraction of the other vertices are at distance exactly d from v. Random graphs are distance-uniform with logarithmic critical distance, and it was conjectured by Alon, Demaine, Hajiaghayi, and Leighton that the critical distance (equivalently, the diameter) of a distance-uniform graph must always be logarithmic. In this talk, we use a generalization of the Towers of Hanoi puzzle to construct distance-uniform graphs with a much larger diameter: for constant epsilon, as large as n^O(1/log log n). We show that this construction is more or less worst possible for sufficiently small epsilon, leaving open the possibility that for large epsilon, much worse cases exist.

##### Matchings and covers in families of d-intervals and their duals

A classical theorem of Gallai is that in any family of closed intervals in the real line, the maximal number of disjoint intervals is equal to the minimal number of points piercing all intervals. Tardos and Kaiser extended this result (appropriately modified) to families of ``d-intervals'', that is, hypergraphs in which each edge is the union of d intervals. We prove an analogous result for dual d-interval hypergraphs, in which the roles of the points and the edges are reversed. The proof is topological. We also discuss a recent Helly-type result for families of d-intervals.

##### Four conjectures in spectral extremal graph theory

We discuss how to prove four conjectures in extremal graph theory where the graph invariant being maximized is a function of the eigenvalues or eigenvectors of the adjacency matrix of the graph. Our most difficult result proves a conjecture of Boots and Royle from 1991: the planar graph of maximum spectral radius is the join of an edge and a path of length $n-2$. All of our proofs follow a similar template, and we will end the talk with several problems to which one might try to apply our method. This is joint work with Josh Tobin.

##### Stability results for graphs with a critical edge

The classical stability theorem of Erdos and Simonovits states that, for a fixed nonbipartite graph H with chromatic number k+1, every n-vertex graph that is H-free and has within o(n^2) of the maximal possible number of edges can be made into the k-partite Tur´an graph by adding and deleting o(n^2) edges. We prove sharper quantitative results for graphs H with a critical edge, both for distance to the Turan graph, and for the closely related question of how close an H-free graph is to being k-partite. In many cases, these results are optimal to within a constant factor. Joint work with Alex Roberts (Oxford).

##### What can infinity tell us about the finite?

What structure/randomness dichotomies can be found across families of infinite structures? How precisely can we pinpoint the interactions of randomness and freedom vs structure and control inside a structure? Model theory has long investigated these questions. It turns out that model theoretic theorems about infinite objects can have strong consequences for finite objects. The talk will expand on these questions and some motivating consequences from the speaker's work (joint with S. Shelah), including characterization of the existence of irregular pairs in Szemeredi's regularity lemma and improved Ramsey theorems for certain classes of graphs and hypergraphs.

##### Dreaming of independence

I'll mainly discuss one simple example of a common state of affairs: it would be nice to be able to say that some quantities of interest behave (more or less) as if they were independent. While we still can't show the behavior we expect for the question in question, what we do know is at least enough to settle an old conjecture of Alon and Spencer. Joint with Huseyin Acan.