The Schedule

Abstract: In this talk, we will present a new approach for approximating large independent sets when the input graph is a one-sided spectral expander – that is, the uniform random walk matrix of the graph has the second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost 3-colorable or are promised to contain an independent set of size (1/2 - ε)n. Surprisingly, we observe that the analogous task of finding a linear-sized independent set in almost 4-colorable one-sided expanders (even when the second eigenvalue is o(1)) is NP-hard, assuming the Unique Games Conjecture.

Our rounding builds on the method of simulating multiple samples from a pseudodistribution introduced in a prior work. for rounding Unique Games instances on small-set expanders. The key to our analysis is a new clustering property of large independent sets in expanding graphs – every large independent set has a larger-than-expected intersection with some member of a small list – and its formalization in the low-degree sum-of-squares proof system.

Based on joint work with Mitali Bafna (MIT) and Tim Hsieh (CMU)

Abstract: Everybody knows expanders are extremely useful. I'll try to describe a wide variety of applications in the hope that everyone will meet some they didn't already know. 

Abstract: We discuss the following relaxation of the Gyárfás-Sumner conjecture: for every forest T, every n-vertex graph with no induced copy of T and with bounded clique number has chromatic number n^(o(1)). To do so, we show that each such graph has a stable set of size at least n^(1-o(1)) via a ``poorly expanding stable sets'' argument. 

Joint work with Alex Scott and Paul Seymour.

Abstract: In a recent remarkable breakthrough, Kelley and Meka significantly improved the bounds for sets of integers lacking three-term arithmetic progressions. Soon thereafter, Filmus, Hatami, Hosseini and Kelman extended their methods to sets lacking so-called binary systems of linear forms. Central to their approach is a new sparse graph counting lemma which is tailored to density increment arguments in additive number theory. In this talk, I will discuss how one can combine improvements in certain quantitative aspects of their graph counting lemma with further Kelley-Meka-style arguments to get new bounds for sets lacking k-configurations, i.e. collections of k integers together with their pairwise arithmetic means. As a consequence, this gives an alternative proof of a bound for the Erdős-Moser sum-free set problem of best known shape.

Abstract: The Erdős-Sós Conjecture says that every graph with average degree k contains a copy of every k-edge tree, while the Loebl-Komlós-Sós Conjecture predicts that the same is true with "average degree" replaced by median degree. For dense graphs, these conjectures are quite well understood, but for sparse graphs (when k=o(n)), some mystery remains. This talk will be about the sparse cases of these conjectures as well as their relatives in the special case of bounded degree trees.

Abstract: In 1975, Erdos asked for the maximum number of edges that an n-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turan-type results can be used to prove an upper bound n^(3/2+o(1)). However, this approach cannot give an upper bound better than n^(3/2). We show that, for any k, every n-vertex graph with at least n*polylog(n) edges contains k pairwise edge-disjoint cycles with the same vertex set, resolving this old problem in a strong form up to a polylogarithmic factor. The well-known construction of Pyber, Rodl and Szemeredi of graphs without 4-regular subgraphs shows that there are n-vertex graphs with Ω(n log log n) edges which do not contain two edge-disjoint cycles with the same vertex set, so the polylogarithmic term in our result cannot be completely removed.

Joint work with Debsoumya Chakraborti, Abhishek Methuku and Richard Montgomery.

Abstract: It was recently shown that sparse pseudorandom graphs are Hamiltonian, resolving a well-known conjecture of Krivelevich and Sudakov. In this talk, we present a strengthening of that result, proving that such graphs remain Hamiltonian even after an adversary deletes up to a (1/2 – o(1))-fraction of the edges incident to each vertex. This extends resilience results previously established for random graphs to the pseudorandom setting.

Joint with J. Kim, H. Lee, D. Munhá Correia, M. Pavez-Signé, B. Sudakov

Abstract: Addressing a question of Heilbronn, in 1971-72 Roth famously showed that among any n points in the unit square one can find a triangle of area at most n^{-1-c} for some fixed c>0. The value of c was later improved by Komlos-Pintz-Szemeredi and recently by Cohen, Pohoata and myself.

In this work, we consider a three dimensional variant of Heilbronn's triangle problem and prove that among any n points in the unit cube one can find a triangle of area at most n^{-2/3-c} for some fixed c>0. This is the first non-trivial upper bound for this question.

Joint work with Dominique Maldague and Hong Wang.

Abstract: For a given graph H, its subdivisions carry the same topological structure. The existence of H-subdivisions within a graph G has deep connections with topological, structural and extremal properties of G. One prominent example of such a connection, due to Bollobás and Thomason and independently Komlós and Szemerédi, asserts that the average degree of G being d ensures a subdivision of a clique on Ω(d^0.5) vertices in G. Although this square-root bound is best possible, various results showed that much larger clique subdivisions can be found in a graph for many natural classes. We investigate the connection between crux, a notion capturing the essential order of a graph, and the existence of large clique subdivisions. This reveals the unifying cause underpinning all those improvements for various classes of graphs studied. Roughly speaking, when embedding subdivisions, natural space constraints arise; and such space constraints can be measured via crux. The notion of crux was inspired by the development of sublinear expanders. Our result falls in a more general theme, which we call ``Replacing average degree by crux'' for sparse graphs embeddings. 

This is joint work with Seonghyuk Im, Jaehoon Kim and Younjin Kim.

Abstract: I will survey variants of expander hierarchies and their applications. 

The examples include the known result of how expander hierarchy in undirected graphs can be used for oblivious routing.

Recently, we have generalized the notion of expander hierarchy to the setting of vertex expanders, directed expanders, and/or length-constrained expanders.

These notions lead to new applications, including new graph approximation via shortcuts, new fault-tolerant labeling schemes, and new max-flow algorithms.

Abstract: We will discuss an interplay between the graph container method from combinatorics and the cluster expansion method from statistical physics, and some of its applications including sampling independent sets from bipartite expander graphs.

Abstract: A connected dominating set (CDS) in a graph is a dominating set of vertices that induces a connected subgraph. Having many disjoint CDSs in a graph can be considered as a measure of its connectivity, and has various graph-theoretic and algorithmic implications, ranging from connectivity-related algorithms through routing algorithms to graph rigidity.

We show that d-regular (weakly) pseudorandom graphs contain (1+o(1))d/ln d disjoint CDSs, which is asymptotically best possible. In particular, this implies that random d-regular graphs typically contain (1+o(1))d/ln d disjoint CDSs.

A joint work with Nemanja Draganić. 

Abstract: Consider shuffling a deck of n cards, labeled 1 through n, as follows: at each time step, pick one card uniformly with your right hand and another card, independently and uniformly with your left hand; then swap the cards. How long does it take until the deck is close to random?

Diaconis and Shahshahani showed that this process undergoes cutoff in total variation distance at time t=⌊n log n/2⌋. Confirming a conjecture of N. Berestycki, we prove the definitive "hitting time" version of this result: let τ denote the first time at which all cards have been touched. The total variation distance between the stopped distribution at τ and the uniform distribution on permutations is o_n(1); this is best possible, since at time τ−1, the total variation distance is at least (1+o_n(1))/e.

Joint work with V. Jain

Abstract: Various random graphs models satisfy that each edge appears independently of all other edges but those in a bounded degree graph. Examples include Erdős–Rényi random graphs, random Cayley graphs, random Latin square graphs, and random entangled graphs. We begin the systematic study of such random graphs under this weak independence hypothesis, focusing on the clique number. We prove that for 0<p<1 fixed, for any such N-vertex random graph with edge probabilities each p, the clique number is asymptotically almost surely at least (2-o(1))log_{1/p} N and at most O(log N loglog N). The lower bound is tight for the Erdős–Rényi random graph, and the upper bound is tight for random Cayley graphs in finite vector spaces over a fixed finite field. Using the trace method and some intricate counting , in case when the dependency graph is symmetric, we also obtain an upper bound on the second largest eigenvalue of these random graphs, and derive that they are Hamiltonian.  

Based on joint work with D. Conlon, J. Fox and  H. T. Pham.

Abstract: Fix d ≥ 2 and consider a uniformly random set P of n points in [0, 1]^d. Let G be the Hasse diagram of P (with respect to the coordinatewise partial order), or alternatively let G be the Delaunay graph of P with respect to axis-parallel boxes (where we put an edge between u, v ∈ P whenever there is an axis-parallel box containing u, v and no other points of P). In each of these two closely related settings, we show that the chromatic number of G is typically (log n) ^{d−1+o(1)} and the independence number of G is typically n/(log n) ^{d−1+o(1)}. When d = 2, we obtain bounds that are sharp up to constant factors: the chromatic number is typically of order log n/ log log n and the independence number is typically of order n log log n/ log n. These results extend and sharpen previous bounds by Chen, Pach, Szegedy and Tardos. In addition, they provide new bounds on the largest possible chromatic number (and lowest possible independence number) of a d-dimensional box-Delaunay graph or Hasse diagram, in particular resolving a conjecture of Tomon.

Joint work with Matthew Kwan and Lyuben Lichev.

Abstract: We use cycle decomposition as a playground to illustrate the interplay between graph theory and algorithm design, showcasing how insights from one can inspire advances in the other. We introduce algorithms for hybrid expander decomposition and use them to develop fast algorithms for cycle decomposition. Leveraging techniques from advanced graph algorithms, we not only achieve an efficient cycle decomposition but also simplify the proof of the cycle decomposition theorem of [BM’22], eliminating the need for the hypergraph matching lemma. Furthermore, we present a novel algorithm for deterministic expander routing based on perfect matchings in hypergraphs.