Probabilistic Combinatorics Abstracts

Determining the satisfiability threshold lies at the center of research in random constraint satisfaction problems. When adding random constraints one at a time to a set of n variables, the system transitions from being satisfiable (SAT) to unsatisfiable (UNSAT) when the number of constraints is around some critical value αn. Famous random CSP instances include k-SAT, k-XORSAT, graph and hypergraph coloring and independent-set problems, and linear equations over fields. Some of these lie in the class of uniquely extendable CSPs, such as k-XORSAT and linear equations over fields, whereas k-SAT, graph coloring, and independent-set problems are extendable but not uniquely extendable.

It has been observed that the satisfiability thresholds α* of k-XORSAT and linear equations over finite fields coincide regardless of the order of the field. Moreover, unique extendability governs the solution geometry and motivated a conjecture of Connamacher and Molloy that the SAT threshold of a random uniquely extendable CSP coincides with α*. We explore this conjecture and give a partial confirmation. We then explore what happens for non-uniquely extendable CSPs, and in particular the SAT thresholds for equations over finite rings. Equations over rings differ from the above-mentioned CSPs in that they are not even extendable, providing a unique perspective on what governs the behavior of SAT thresholds.

This talk is based on joint work with Theodore Morrison.

Given a natural number r, let p_r be the threshold at which every edge in G(n,p) is contained in a copy of K_r. Clearly, p_r is a lower bound for the threshold at which G(n,p) admits a (fractional) K_r-decomposition. We present progress on constructing fractional K_r-decompositions of G(n,p) close to p_r.

This is joint work with Zak Smith.

We present a random construction proving that the extreme off-diagonal Ramsey numbers satisfy R(3,k) ≥ (½ + o(1))k²/log k (conjectured to be asymptotically tight), improving the previously best bound R(3,k) ≥ (⅓ + o(1))k²/log k. In contrast to all previous constructions achieving the correct order of magnitude, we do not use a nibble argument.

Beyond the paper, we will explore a bit further how the approach can be used for other problems.

This is joint work with Zion Hefty, Paul Horn, and Dylan King.

The Rödl nibble is a fundamental probabilistic approach for finding large matchings in hypergraphs. Classical results of Pippenger and Frankl–Rödl show that the nibble produces almost-perfect matchings in nearly D-regular hypergraphs when the maximum 2-degree is much smaller than D, and later work of Vu sharpened the quantitative dependence by incorporating higher codegrees. In this talk, I will discuss joint work with Stephen Gould that pushes this line further: we show that the nibble can essentially exhaust the full codegree sequence, up to natural bottlenecks, even when codegrees exhibit significant “clustering.” I will explain the main idea behind the improvement, some generalizations to matchings in “partite” settings, and some applications to Latin squares and designs.

The (old) question considered here is, roughly: given D (possibly growing) and large n, for what p = p(n,D) is G(n,p) likely to contain a copy of any particular n-vertex tree with maximum degree at most D?

Here G(n,p) is the usual Erdős–Rényi random graph.

The question is settled (more or less, and not easily) for fixed D, but for growing D less is known, though the answer is not hard to guess. We remain unable to prove this guess is correct, but report some interesting progress.

Joint work with Caleb Fong and Jinyoung Park.

Suppose we choose N points uniformly at random from a convex body in d dimensions. How large must N be, asymptotically with respect to d, so that the convex hull of the points is nearly as large as the convex body itself? It was shown by Dyer–Füredi–McDiarmid that exponentially many samples suffice when the convex body is the hypercube, and by Pivovarov that the Euclidean ball demands roughly d^d/2 samples. We show that when the convex body is the simplex, exponentially many samples suffice; this then implies the same result for any convex simplicial polytope with at most exponentially many faces.

Joint work with Alan Frieze and Tomasz Tkocz.

We study a classic model for forming a random graph of maximum degree d. Begin with n vertices and repeatedly add an edge between a uniformly chosen pair of vertices satisfying: (i) both have degree less than d, and (ii) they are not already adjacent. Ruciński and Wormald analyzed the short-cycle distribution for the case d = 2. We study the case of constant d > 2. We show that for any fixed t > 2, the number of t-cycles has a Poisson distribution with constant mean. The proof combines a switching argument and a differential-equations argument.

Joint work with Lora Hreish and Lutz Warnke.

Many real-world networks possess the so-called small-world phenomenon, where every node is relatively close to every other node, and have a large clustering coefficient—that is, friends of friends are likely to be friends. We investigate the clustering effect in sparse clustering graphs by examining the eigenvalues, as well as quasirandom classes for strongly regular clustering graphs.

We discuss a new combinatorial large-sieve method that uses algebraic splitting modulo many small primes to turn local congruence restrictions into global constraints on repeated values. This has various applications: (i) every Sidon subset of {1², 2², …, N²} has size at most N · exp(−c log N/log log N), the first super-polylogarithmic saving for a classical problem of Alon and Erdős; (ii) a new upper bound on the largest subset of [N]² with no repeated distances, a problem of Erdős and Guy; and (iii) a new upper bound on the largest subset of [N]² with no isosceles triangle, a problem recently popularized by Charton, Ellenberg, Wagner, and Williamson.

This is based on recent joint work with Ernie Croot, Junzhe Mao, Adam Sheffer, and Kyle Yip. We will also discuss how these ideas recently led to a counterexample for the Elekes–Rónyai problem, and to a few other constructions.

We consider the question of what structure can be guaranteed “robustly” in the intersection of two random graphs. For a graph property 𝓕, one may ask for which values of (p,q) we have π(G) ∩ H ∈ 𝓕 for all bijective functions π: V(G) → V(H), where G ∼ G(n,p) and H ∼ G(n,q) are independent random graphs. We consider thresholds for properties such as containing an edge, containing a certain fixed subgraph, containing a giant component, and containing spanning subgraphs. Many open problems remain.

Based on joint work with Gautier Audhuy and Bruno Baldissera.