We show that Erdős-Renyi random graph with constant density has correspondence chromatic number O(n/√(log n)); this matches a prediction from linear Hadwiger’s conjecture for correspondence colouring. The proof follows from a sufficient condition for correspondence colourability in terms of the numbers of independent sets. We conjecture the truth to be of order O(n/log n) as suggested by the random correspondence assignment.
In 1947, Paul Erdos famously gave a construction of graphs with no large cliques and independent sets via the probabilistic method. Since then, Erdos’ ingenious probabilistic insight and the emergence of structures in random graphs have motivated fundamental developments in combinatorics and probability. In this talk, I highlight several recent results in random graph studies with interesting connections to additive combinatorics, theoretical computer science and probability.
In joint work with David Conlon, Jacob Fox and Liana Yepremyan, we study structures in random Cayley graphs of general groups. Given a fixed finite group, random Cayley graphs are constructed by choosing the generating set at random. These graphs thus reflect interesting symmetries and properties of the group, at the cost of inducing complex dependencies. We will discuss results on clique and independence numbers in random Cayley graphs of general groups, as well as progress towards a conjecture of Alon on Cayley graphs with small clique and independence number. These questions are naturally connected with some fundamental problems in additive combinatorics, where we surprisingly discover that in some of them the group structure is superfluous.
Certain important aspects in the study of structures in random graphs can be phrased in terms of thresholds. In joint work with Jinyoung Park, building on insights in our resolution of Talagrand’s selector process conjecture, we prove the Kahn-Kalai conjecture, that thresholds of general monotone properties are closely predicted by expectation obstructions. The Kahn-Kalai conjecture is a beautiful milestone towards the understanding of emergence of general structures, and yet to complete the quest, it remains to study these expectation obstructions. This latter task can prove to be highly challenging in several cases and bring in interesting connections. As an illustration, I will discuss joint work with Vishesh Jain that determines the threshold for edge-colorings of complete bipartite graphs by exploiting connections to the Lovasz Local Lemma and local uniformity properties, which have played an important role in sampling solutions to constraint satisfaction problems.
A graph is said to be a (1-dimensional) expander if the second eigenvalue of its adjacency matrix is bounded away from 1, or almost-equivalently, if it has no sparse vertex cuts. There are several natural ways to generalize the notion of expansion to hypergraphs/simplicial complexes, but one such way is 2-dimensional spectral expansion, in which the local expansion of vertex links/neighborhoods (remarkably) witnesses global expansion. While 1-dimensional expansion is known to be achieved by, e.g., random regular graphs, very few examples of sparse 2-dimensional expanders are known, and at present all are algebraic. It is an open question whether sparse 2-dimensional expanders are natural and "abundant" or "rare." In this talk, we'll give some evidence towards abundance: we show that the set of triangles in a random geometric graph on a high-dimensional sphere yields an expanding simplicial complex of arbitrarily small polynomial degree.
In the random geometric graph model, we identify each of our n vertices with an independently and uniformly sampled vector from the d-dimensional unit sphere, and we connect pairs of vertices whose vectors are 'sufficiently close' such that the marginal probability of an edge is p.
We investigate the problem of distinguishing an Erdős-Rényi graph from a random geometric graph. When p = c/n for a constant c, we prove that if d ≥ poly log n, the total variation distance between the two distributions is close to 0; this improves upon the best previous bound of Brennan, Bresler, and Nagaraj (2020), which required d ≫ n3/2, and further our result is nearly tight, resolving a conjecture of Bubeck, Ding, Eldan, and Rácz (2016) up to logarithmic factors. We also obtain improved upper bounds on the statistical indistinguishability thresholds in d for the full range of p satisfying 1/n ≤ p ≤ 1/2, improving upon the previous bounds by polynomial factors.
In this talk, we will discuss the key ideas in our proof, which include:
• Analyzing the Belief Propagation algorithm to characterize the distributions of (subsets of) the random vectors conditioned on producing a particular graph.
• Sharp estimates for the area of the intersection of a random sphere cap with an arbitrary subset of the sphere, which are proved using optimal transport maps and entropy-transport inequalities on the unit sphere.
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any non-trivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold.
Given a finite simplicial graph, we can generate a right-angled Coxeter group (RACG): each vertex corresponds to a generator and two generators commute if and only if the corresponding vertices are adjacent. This assignment is unique up to isomorphism, which allows us to characterize geometric and algebraic properties of the RACG using combinatorial properties of its generating graph. This also allows us to use a model of random graphs to study random RACGs.
In this talk we will focus on the divergence of a RACG. Using the Erdös-Renyi random graph model, we show that at a wide range of densities a random RACG asymptotically almost surely has quadratic divergence. We will also give a sharp threshold, below which a random RACG has (almost surely) at least cubic divergence, and above which its divergence is (almost surely) at most quadratic. This is joint work with Jason Behrstock, Victor Falgas-Ravry and Mark Hagen.
We present an approach to show the existence of large expanders in locally sparse graphs and in sparse (including super-critical) random graphs, as well as its consequences for extremal questions and positional games.
This talk will give a high level overview of (deterministic/seedless) extractors for random sources that are defined algebraically. These include sources distributed uniformly over an affine subspace or variety and sources sampled by polynomial maps. I will attempt to survey the various techniques that go into known constructions and the many open problems.
The breakthrough result of Chattopadhyay and Zuckerman gives a reduction from the construction of explicit non-malleable extractors to the construction of explicit two-source extractors and bipartite Ramsey graphs. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for poly(log n) entropy, rather than the optimal O(log n). In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size 2k, for k=O(log n log log n). Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor. Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object - a somewhere-random condenser with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the Raz et al. error reduction technique, and the constant degree dispersers of Zuckerman that also work against extremely small tests.
Pivotal to recent exciting progress in randomness extractors is a pair of new pseudo-random objects - correlation breakers, and independence-preserving mergers. In this talk, we discuss these objects, their constructions, and applications.
You must be logged in to post a comment.