Tag - Combinatorics

Alexander Yong: Newell-Littlewood numbers

28th November, 2023

The Newell-Littlewood numbers are defined in terms of the Littlewood-Richardson coefficients from algebraic combinatorics. Both appear in representation theory as tensor product multiplicities for a classical Lie group. This talk concerns the question: Which multiplicities are non-zero? In 1998, Klyachko established common linear inequalities defining both the eigencone for sums of Hermitian matrices and the saturated Littlewood-Richardson cone. We prove some analogues of Klyachko's non-vanishing results for the Newell-Littlewood numbers.

Jason Miller: Conformal Removability of SLE

6th October, 2023

We consider the Schramm-Loewner evolution (SLEκ) with κ = 4, the critical value of κ > 0 at or below which SLEκ is a simple curve and above which it is self-intersecting. We show that the range of an SLE4 curve is a.s. conformally removable. Such curves arise as the conformal welding of a pair of independent critical (γ = 2) Liouville quantum gravity (LQG) surfaces along their boundaries and our result implies that this conformal welding is unique. In order to establish this result, we give a new sufficient condition for a set X ⊆ ℂ to be conformally removable which applies in the case that X is not necessarily the boundary of a simply connected domain. We will also describe how this theorem can be applied to obtain the conformal removability of the SLEκ curves for κ ∈ (4,8) in the case that the adjacency graph of connected components of the complement is a.s. connected. This talk will assume no prior knowledge of SLE or LQG.

Ola Svensson: Polyhedral Techniques in Combinatorial Optimization: Matchings and Tours

5th October, 2023

We overview recent progress on two of the most classic problems in combinatorial optimization: the matching problem and the travelling salesman problem. We focus on deterministic parallel algorithms for the perfect matching problem and the first constant-factor approximation algorithm for the asymmetric travelling salesman problem. While these questions pose seemingly different challenges, recent progress has been achieved using similar polyhedral techniques. In particular, for both problems, we will explain the use linear programming formulations, even exponential-sized ones, to extract structure from problem instances to guide the design of better algorithms.

Yuval Filmus: Structure of Boolean Almost Low Degree Functions on the Biased Cube

28th July, 2023

The FKN theorem states that if a Boolean function on the Boolean cube is close to degree 1, then it is close to a dictator. Similarly, the Kindler-Safra theorem states that if a Boolean function on the Boolean cube is close to degree d, then it is close to a junta.

The picture becomes more interesting when we study functions on the p-biased Boolean cube. If a Boolean function is 𝜀-close to degree 1, then (up to negation) it is O(𝜀)-close to a maximum of O(√𝜀/p+1) coordinates, and so O(√𝜀+p)-close to a constant function. A similar statement holds for functions close to degree d, but the corresponding structure is more complicated.Another setting we might discuss is functions on the symmetric group. If a Boolean function is 𝜀-close to degree 1, then it is O(√𝜀)-close to a dictator (suitably defined), and O(𝜀)-close (up to negation) to a union of “mostly disjoint” cosets. A similar statement should hold for degree d, where the function ought to be close to a (suitably defined) decision tree of depth poly(d).

Liana Yepremyan: Correspondence Colouring of Random Graphs

28th July, 2023

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.

Huy Tuan Pham: Structures in Random Graphs: New Connections

28th July, 2023

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.

Guy Kindler: A Polynomial Bogolyubov type Result for the Special Linear Group

26th July, 2023

For a subset A of a finite-dimensional vector space over a finite field, It is known that 2A-2A must contain a subgroup of density that is quasi-polynomial in the density of A. We show an analogue result for the special linear group over a finite field, except we achieve a polynomial density for the subgroup. The main tool used is a new hyper-contractive estimate for the special linear group, that has origins in the study of 2-to-2 games.

Tselil Schramm: Higher-dimensional Expansion of Random Geometric Complexes

25th July, 2023

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.

Siqi Liu: Testing Thresholds for High-dimensional Sparse Random Geometric Graphs

25th July, 2023

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.

Caroline Terry: An Improved Bound for Regular Partitions of Hypergraph of Bounded VC2 Dimension

25th July, 2023

A regular partition 𝒫 of a 3-uniform hypergraph H=(V,E) consists of a partition V=V1 ∪ ... ∪ Vt and for each ij ∈ [t] choose 2, a partition Vi × Vj = Pij1 ∪ ... ∪ Pij𝓁 so that certain quasirandomness properties hold. The complexity of 𝒫 is the pair (t,𝓁). In this talk, we present results which show that if a 3-uniform hypergraph H has VC2-dimension at most k, then there is a regular partition for H of complexity (t,𝓁), where 𝓁 is bounded by a polynomial in the degree of regularity. This is a vast improvement on the bound arising from the proof of this regularity lemma in general, in which the bound generated for 𝓁 is of Wowzer type. This result can be seen as a higher arity analogue of the efficient regularity lemmas for graphs and hypergraphs of bounded VC-dimension due to Alon-Fischer-Newman, Lovász-Szegedy, and Fox-Pach-Suk.