Title: Quantum Algorithms on Graphs

Abstract: In this talk, I will provide a brief introduction to quantum computation and demonstrate its potential for accelerating classical graph algorithms. Specifically, I will present an asymptotically tight result for learning a Hamiltonian cycle using OR queries, as well as a significant polynomial improvement on the best-known quantum algorithm for (Δ+1)-coloring a graph with maximum degree Δ. This work is based on joint research with Liam Hardiman (UCI) and Xiaonan Chen (UCI).

Location: Emory University, W303, MSC centre, 400 Dowman Dr
Date & Time: Thursday, November 7th, 4:30-5:30 (refreshments at 4)
Parking: Oxford Parking Deck, Oxford Road Building, 201 Dowman Dr, Atlanta, GA 30307

Title: TBD

Abstract: TBD

Location: Georgia State University, 25 Park Place, Room 1441 (tentative)
Date & Time: Monday, December 9th, 4-5pm (tentative)

Title: TBD

Abstract: TBD

Location: Georgia State University, 25 Park Place, Room 223 (tentative)
Date & Time: Friday, January 24th, 4-5pm (tentative)

Title: TBD

Abstract: TBD

Location: Georgia Tech
Date & Time: Thursday, April 3rd

Title: What is a combinatorial interpretation?

Abstract: In enumerative combinatorics, one is often asked to count the number of combinatorial objects. But the inverse problem is even more interesting: given some numbers, do they have a combinatorial interpretation? In the main part of the talk I will give a broad survey of this problem, formalize the question in the language of computational complexity, and describe some connections to deep results and open problems in algebraic and probabilistic combinatorics. In the last part of the talk, I will discuss our recent results on the defect and equality cases of Stanley inequalities for the numbers of bases of matroids and for the numbers of linear extensions of posets (joint work with Swee Hong Chan). The talk is aimed at the general audience.

Title: Recent progress in Ramsey Theory

Abstract: The Ramsey number \(r(s,t)\) denotes the minimum \(N\) such that in any red-blue coloring of the edges of the complete graph \(K_N\), there exists a red \(K_s\) or a blue \(K_t\). While the study of these quantities goes back almost one hundred years, to early papers of Ramsey and Erdős and Szekeres, the long-standing conjecture of Erdős that \(r(s,t)\) has order of magnitude close to \(t^{s - 1}\) as \(t \rightarrow \infty\) remains open in general. It took roughly sixty years before the order of magnitude of \(r(3,t)\) was determined by Jeong Han Kim, who showed \(r(3,t)\) has order of magnitude \(t^2/(\log t)\) as \(t \rightarrow \infty\). In this talk, we discuss a variety of new techniques which lead to the lower bound in the following statement: for some constants \(a\), \(b > 0\) and \(t \geq 2\), \[ a\frac{t^3}{(\log t)^4} \leq r(4,t) \leq b\frac{t^3}{(\log t)^2}.\] This solves a conjecture of Erdős. We also come close to determining related quantities known as Erdős–Rogers functions, as well as determine the current best bounds for other graph Ramsey numbers. Joint work in part with Sam Mattheus and Dhruv Mubayi.

Title: Measuring combinatorial complexity via regularity lemmas

Abstract: Many tools have been developed in combinatorics to study global structure in finite graphs. One such tool is called Szemerédi's regularity lemma, which gives a structural decomposition for any large finite graph. Beginning with work of Alon–Fischer–Newman, Lovász–Szegedy, and Malliaris–Shelah, it has been shown over the last 15 years that regularity lemmas can be used to detect structural dichotomies in graphs, and that these dichotomies have deep connections to model theory. In this talk, I present extensions of this type of result to arithmetic regularity lemmas, which are analogues of graph regularity lemmas, tailored to the study of combinatorial problems in finite groups. This work uncovered tight connections between tools from additive combinatorics, and ideas from the model theoretic study of infinite groups.

Title: Canonical colourings in random graphs

Abstract: Rödl and Ruciński established Ramsey's theorem for random graphs. In particular, for fixed integers \(r\), \(\ell\geq 2\) they showed that \(n^{-2/(\ell+1)}\) is a threshold for the Ramsey property that every \(r\)-colouring of the edges of the binomial random graph \(G(n,p)\) yields a monochromatic copy of \(K_\ell\).

We investigate how this result extends to arbitrary colourings of \(G(n,p)\) with an unbounded number of colours. In this situation Erdős and Rado showed that canonically coloured copies of \(K_\ell\) can be ensured in the deterministic setting. We transfer the Erdős–Rado theorem to the random environment and show that for \(\ell\geq 4\) both thresholds coincide. As a consequence the proof yields \(K_{\ell+1}\)-free graphs \(G\) for which every edge colouring yields a canonically coloured \(K_\ell\).

This is joint work with Nina Kamčev.

Title: Ascending subgraph decompositions

Abstract: A graph \(G\) has a decomposition in to graphs \(H_1\), \(\ldots\), \(H_m\), if the edges of \(G\) can be partitioned into edge-disjoint copies of each of \(H_1\), \(\ldots\), \(H_m\). A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph \(G\) into copies \(H_1\), \(\ldots\), \(H_m\) are also sufficient. One such problem was posed by Alavi, Boals, Chartrand, Erdős, and Oellerman. They conjectured that the edges of every graph with \({m+1 \choose 2}\) edges can be decomposed into subgraphs \(H_1\), \(\ldots\), \(H_m\) such that each \(H_i\) has \(i\) edges and is isomorphic to a subgraph of \(H_{i+1}\). This talk will be about a proof of this for sufficiently large \(n\). Joint work with Kyriakos Katsamaktsis, Shoham Letzter, and Benny Sudakov.

Title: An exponential improvement for diagonal Ramsey

Abstract: The Ramsey number \(R(k)\) is the minimum \(n\) such that every red-blue colouring of the edges of the complete graph on \(n\) vertices contains a monochromatic copy of \(K_k\). It has been known since the work of Erdős and Szekeres in 1935, and Erdős in 1947, that \(2^{k/2} < R(k) < 4^k\), but in the decades since the only improvements have been by lower order terms. In this talk I will sketch the proof of a recent result, which improves the upper bound of Erdős and Szekeres by a (small) exponential factor.

Based on joint work with Marcelo Campos, Simon Griffiths and Julian Sahasrabudhe.

Title: \(k\)-Blocks and forbidden induced subgraphs

Abstract: A \(k\)-block in a graph is a set of \(k\) vertices every two of which are joined by \(k\) vertex disjoint paths. By a result of Weissauer, graphs with no \(k\)-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions to bounded tree width, a lot can be said about graphs with no \(k\)-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a \(k\)-block in a graph. We will discuss this phenomenon and its consequences on the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.

Title: Ramsey theory constructions from hypergraph matchings

Abstract: Erdős and Gyárfás (1997) investigated the following parameter that generalizes classical Ramsey numbers: let \(f(n,p,q)\) be the minimum number of colors required to color the edges of an \(n\)-clique so that every \(p\)-subclique receives at least \(q\) colors. This parameter has led to many interesting problems. I will show how a recent generalization of an old result of Frankl and Rödl about hypergraph matchings can be used to settle some cases of the Erdős–Gyárfás problem by giving asymptotically optimal constructions. This is joint work with Felix Joos.

Title: From triangulations to graphs and back

Abstract: I will discuss some problems in geometric topology, and relate them to graph-theoretic properties. I will give some open problems, and answer questions of Kalai, Belolipetski, Gromov and others.

Title: Random graphs and suprema of stochastic processes

Abstract: The threshold phenomenon is a central direction of study in probabilistic combinatorics, particularly the study of random graphs, and in theoretical computer science. The threshold of an increasing graph property (or more generally an increasing boolean function) is the density at which a random graph (or a random set) transitions from unlikely satisfying to likely satisfying the property (or the function). Kahn and Kalai conjectured that this threshold is always within a logarithmic factor of the expectation threshold, a natural lower bound to the threshold which is often much easier to compute. In probabilistic combinatorics and random graph theory, the Kahn–Kalai conjecture directly implies a number of difficult results, such as Shamir's problem on hypergraph matchings. I will discuss joint work with Jinyoung Park that resolves the Kahn–Kalai conjecture. I will also discuss recent joint work with Vishesh Jain that resolves a conjecture of Johansson, Keevash, and Luria and Simkin on the threshold for containment of Latin squares and Steiner triple systems, and joint work with Ashwin Sah, Mehtaab Sawhney, Michael Simkin on thresholds in robust settings. Zooming into finer details of random graphs beyond the threshold phenomenon, I will touch on nonlinear large deviation results for subgraph counts and connections to sparse regularity obtained in joint work with Nicholas Cook and Amir Dembo.

Interestingly, the proof of the Kahn–Kalai conjecture is closely related to our resolution of a conjecture of Talagrand on extreme events of suprema of certain stochastic processes driven by sparse Bernoulli random variables (known as selector processes), and a question of Talagrand on suprema of general positive empirical processes. These conjectures play an important role in generalizing the study of suprema of stochastic processes beyond the Gaussian case, and given recent advances on chaining and the resolution of the (generalized) Bernoulli conjecture, our results give the first steps towards Talagrand's last "Unfulfilled dreams" in the study of suprema of general stochastic processes.

Title: Sumset Estimates in Higher Dimensions

Abstract: We will describe recent progress, in joint work with Jeck Lim, on the study of sumset estimates in higher dimensions. The basic question we discuss is the following: given a subset \(A\) of \(d\)-dimensional space and a linear transformation \(L\), how large is the sumset \(A + LA\)?

Title: The Integrality Gap for the Santa Claus Problem

Abstract: In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players is maximized. In the restricted variant, also known as the Santa Claus Problem, each resource ("toy") has an intrinsic positive value, and each player ("child") covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Bezakova and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP of Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs.

Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of 3.808 for the general problem to 3.534. We also address the well-studied special case in which resources can take only two values, and improve the integrality gap in most cases. This is based on joint work with Tibor Szabo.

Title: Friendly Bisections of Random Graphs

Abstract: It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph \(G(n,1/2)\) on an even number of vertices admits a partition of its vertex set into two parts of equal size in which \(n - o(n)\) vertices have more neighbours on their own side than across.