# Seminars & Events for Discrete Mathematics Seminar

##### Expansion for simplicial complexes

For graphs, the notion of expansion is a highly useful concept that has found applications in various areas, especially in combinatorics and theoretical computer science. In recent years, the success of this concept has inspired the search for a corresponding notion in higher dimensions. Graph expansion can be expressed spectrally (via the spectrum of the Laplacian or the adjacency matrix) or combinatorially, e.g., as the edge expansion ratio. The close connection of these two notions is expressed, e.g., by the discrete Cheeger inequality. This talk addresses generalizations of expansion properties to finite simplicial complexes of higher dimension.

##### The chromatic number of graphs without long holes

Andras Gyarfas conjectured in 1985 that for all k and t, every graph with sufficiently large chromatic number contains either a complete subgraph on k vertices or an induced cycle of length at least t. We prove this conjecture and discuss some related results. Joint work with Maria Chudnovsky and Paul Seymour.

##### Extremal number of edges in bipartite graphs as a function of the topological connectivity of the matching complex

The topological connectivity of the matching complex of a graph has been found to be a useful tool in solving many kinds of combinatorial problems such as finding rainbow matchings in edge-colored graphs. In this talk I find the extremal cases for this parameter in bipartite graphs in terms of the number of edges and the number of vertices in each side. More accurately, I answer the following question: given the topological connectivity of the matching complex and the number of vertices in each side of a bipartite graph, what is the maximum possible number of edges? I answer this question and find what the extremal graphs for this problem look like.

##### Augmented trees with high girth

Let G be a graph consisting of a complete binary tree of depth h together with a back edge from each leaf connecting it to one of its ancestors. Suppose further that the girth of G exceeds g. What is the minimum possible depth h=h(g) in such a graph ? This question is motivated by results in a joint paper with Kostochka, Reiniger, West and Zhu, where these graphs are used to provide simple explicit constructions of graphs and hypergraphs of high girth and high chromatic number, as well as tight examples of sparse high girth bipartite graphs with large list-chromatic number.

##### Clique-stable set separation

Consider the following communication complexity problem: Alice is given a clique K, Bob is given a stable set S, and they have to decide via a non-deterministic protocol whether K intersects S or not. A ``certificate'' for the non-intersection is a bipartition of the vertices such that K is included in one side, and S is included in the other side. A ``clique-stable set separator'' is a set of certificates which contains at least one certificate for each input (K,S). Given a class of graphs, the goal is to know whether there exists, for every graph of the class, a clique-stable set separator with only polynomially many certificates.

##### On graphs decomposable into induced matchings of linear size

A ``Ruzsa-Szemeredi graph'' is a graph on n vertices whose edge set can be partitioned into induced matchings of size cn. The study of these graphs goes back more than 35 years and has connections with number theory, combinatorics, complexity theory and information theory. In this talk we will discuss the history and some recent developments in this area. In particular, we show that when c>1/4, there can be only constantly many matchings. On the other hand, for c=1/4, the maximum number of induced matchings is logarithmic in n. This is joint work with Jacob Fox and Benny Sudakov.

##### On Erdos-Ko-Rado for random hypergraphs

One of the more interesting of recent combinatorial directions has been the attempt to understand the extent to which various classical facts remain true in a random setting. The present talk will mostly discuss what we know about this question when the ``classical fact" is the Erdos-Ko-Rado Theorem.

##### Excluding theta graphs

A theta graph, denoted T(a,b,c), consists of a pair of vertices together with three disjoint paths between the vertices of lengths a, b, and c. In this talk, we characterize graphs which exclude certain theta graphs as a minor. We begin with small theta graphs, in particular those with at most 7 edges. This work is part of a larger project which characterizes H-minor-free graphs for all 2-connected graphs H on at most 7 edges and is joint with Mark Ellingham, Tom McCourt, and Tony Nixon. Next we look at excluding large theta graphs. We allow at least one of the paths to be arbitrarily long. The most complicated case is excluding T(t,t,t) where t is any large integer. The work on large theta graphs is joint with Guoli Ding.

##### Positroids, non-crossing partitions, 1/e^2, and a conjecture of Da Silva

We investigate the role that non-crossing partitions play in the study of positroids, a class of matroids introduced by Postnikov. We prove that every positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then freely placing the structure of a connected positroid on each of the blocks of the partition. We use this to prove that the probability that a positroid on [n] is connected equals 1/e^2 asymptotically. We also prove da Silva’s 1987 conjecture that any positively oriented matroid is a positroid; that is, it can be realized by a set of vectors in a real vector space. It follows from this result that the positive matroid Grassmannian (or positive MacPhersonian) is homeomorphic to a closed ball. This is joint work with Felipe Rincón (Warwick) and Lauren Williams (Berkeley).

##### Permutons

What do permutations of 1 through n, for large n, look like? For example, how can we generate a random permutation that inverts a third of its pairs? How many such permutations are there? Permutons are doubly-stochastic measures; they are exactly the limit objects for large permutations, in the appropriate topology. By finding permutons that maximize entropy, we (with Rick Kenyon, Dan Kral and Charles Radin) are able in some cases to count and describe permutations with specified pattern densities. We'll show how permutons arise in several situations, and try to explain why they work, in some respects, better than graphons do for graphs.

##### Real rooted polynomials in graph theory

In this talk, I will discuss some recent applications of real rooted polynomials in graph theory. I will begin by discussing the more classical results concerning graph polynomials, including the real rootedness of the matching polynomial and the extension of Chudnovsky and Seymour to the independence polynomial of claw-free graphs. I will then discuss results using the ``method of interlacing polynomials'' developed by the speaker with Daniel Spielman and Nikhil Srivastava. In particular, I will mention recent results concerning the existence of Ramanujan graphs of all sizes and degrees as well as a recent improvement of the best known upper bound on the integrality gap in the asymmetric traveling salesman problem due to Anari and Oveis-Gharan.

##### Polynomials vanishing on Cartesian products

Let F(x,y,z) be a real trivariate polynomial of constant degree, and let A,B,C be three sets of real numbers, each of size n. How many roots can F have on A x B x C? This question has been studied by Elekes and Rónyai and then by Elekes and Szabó about 15 years ago. One of their striking results is that, for the special case where F(x,y,z) = z-f(x,y), either F vanishes at o(n2) number of points of A x B x C, or else f must have one of the special forms f(x,y) = h(p(x)+q(y)) or f(x,y) = h(p(x)q(y)), for univariate polynomials p, q, h. In the talk I will discuss several recent results, in which the analysis is greatly simplified, and the bounds become sharp: If F does not have a special form, the number of roots is at most O(n11/6).

##### Extremal problems for cycles in graphs

**Please note different time this week.** In this talk, I will give a selective survey of extremal problems for cycles in graphs. In particular, proofs of a number of conjectures of Erdos on this topic will be presented, employing a variety of methods from different branches of mathematics.

##### Some interesting algebraic aspects of graph chordality

I will describe some interesting phenomena within toric geometry related to chordality of graphs, and outline how classical techniques to analyze chordal graphs can be used to prove interesting algebraic results.

##### Coloring perfect graphs with bounded clique number

I will talk about optimally coloring Berge graphs (graphs with no odd hole or antihole). The main difficulty with finding a combinatorial algorithm is handling decompositions by balanced skew partitions. I will show how to solve this in the case of bounded clique number. Joint with with Maria Chudnovsky, Aurelie Lagoutte and Paul Seymour.

##### Ramanujan Coverings of Graphs

Ramanujan graphs are optimal expander graphs, and their existence and construction have been the focus of much research during the last three decades. We prove that every bipartite Ramanujan graph has a d-covering (a.k.a. d-lift) which is also Ramanujan. This generalizes the d=2 case, a recent major breakthrough in the subject due to Marcus, Spielman and Srivastava. The main tools we use are the Peter-Weyl theory in group representations, as well as the theory of interlacing polynomials. All notions will be explained. Joint work with Chris Hall and Will Sawin.

##### Graph Isomorphism in Quasipolynomial Time: The emergence of the Johnson graphs

**Please note different day (Tuesday) and location (Fine 314).** Babai will give two talks at IAS Mon/Tue morning on his new Graph Isomorphism algorithm and will give the third (self contained combinatorial) part here. This talk will give a brief outline of the algorithm, followed by technical details of the second combinatorial partitioning algorithm ("Split-or-Johnson" routine) required for the group theoretic recurrence. The technical material will be complementary to the IAS talks, so while attendance of the IAS lectures is not required for understanding this talk, for those who did attend the IAS talks, this lecture will provide details of the last remaining major ingredient.

##### Asymptotics of the TSP and related functionals for random Euclidean point-sets

The celebrated theorem of Beardwood, Halton and Hammersley gives that the shortest TSP tour through n random points in the unit square is asymptotically $\beta\sqrt{n}$, for some constant $\beta$. Similar asymptotic formulas for random point-sets are known to hold for other quantities; i.e., the minimum-length matching, shortest 2-factor, minimum spanning tree, etc. The constants $\beta$ in these formulas remain unknown, however, with only very weak rigorous bounds. We prove, at least, that the constants are different; that is, we prove that the TSP tour is asymptotically longer than the minimum spanning tree, than the minimum 2-factor, than twice a matching, etc. We will also asymptotically separate the TSP from its linear programming relaxation.

##### **CANCELLED** - Maximising the number of induced cycles

**THIS SEMINAR HAS BEEN CANCELLED.** 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.

##### The sensitivity conjecture: background and new results

What are smooth Boolean functions, and how simple are they? One measure of smoothness is the sensitivity of the function to local changes. Let the graph G(f) of a Boolean function f on the n-dimensional cube be the (bipartite) subgraph of the cube graph containing only edges with different f-values. The sensitivity of f, denoted s(f), is simply the maximum vertex degree of G(f). When s(f) is small compared to the number n of variables, it means that for every vertex x, flipping the bit in one coordinate will change the value of f only for very few coordinates. The basic high level question under study is what structure is implied by this smoothness? One measure of simplicity of a Boolean function is its Fourier degree.