Seminars and Colloquia by Series

On the number of error correcting codes

Series
Combinatorics Seminar
Time
Friday, October 11, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Nitya Mani – MIT –

We show that for a fixed $q$, the number of $q$-ary $t$-error correcting codes of length $n$ is at most $2^{(1 + o(1)) H_q(n,t)}$ for all $t \leq (1 - q^{-1})n - 2\sqrt{n \log n}$, where $H_q(n, t) = q^n / V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner and makes progress towards a 2005 question of Sapozhenko. 

Efficient and optimal high-dimensional planar assignments

Series
Combinatorics Seminar
Time
Friday, September 27, 2024 - 15:15 for
Location
Skiles 005
Speaker
Michael Simkin – Massachusetts Institute of Technology –

The ($2$-dimensional) assignment problem is to find, in an edge weighted bipartite graph, an assignment (i.e., a perfect matching) of minimum total weight. Efficient algorithms for this problem have been known since the advent of modern algorithmic analysis. Moreover, if the edge weights are i.i.d. Exp(1) random variables and the host graph is complete bipartite, seminal results of Aldous state that the expected weight of the optimal assignment tends to $\zeta(2)$.

 

We consider high-dimensional versions of the random assignment problem. Here, we are given a cost array $M$, indexed by $[n]^k$, and with i.i.d. Exp(1) entries. The objective is to find a ${0,1}$-matrix A that minimizes $\sum_{x \in [n]^k} A_xM_x$, subject to the constraint that every axis-parallel line in A contains exactly one 1. This is the planar assignment problem, and when $k=2$ is equivalent to the usual random assignment problem. We prove that the expected cost of an optimal assignment is $\Theta(n^{k-2})$. Moreover, we describe a randomized algorithm that finds such an assignment with high probability. The main tool is iterative absorption, as developed by Glock, Kühn, Lo, and Osthus. The results answer questions of Frieze and Sorkin. The algorithmic result is in contrast to the axial assignment problem (in which A contains exactly one 1 in each axis-parallel co-dimension 1 hyperplane). For the latter, the best known bounds (which are due to Frankston, Kahn, Narayanan, and Park) exploit the connection between ``spread'' distributions and optimal assignments. Due to this reliance, no efficient algorithm is known.

 

Joint work with Ashwin Sah and Mehtaab Sawhney.

The Small Quasikernel Conjecture

Series
Combinatorics Seminar
Time
Friday, September 20, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sam Spiro – Rutgers University –

Given a digraph $D$, we say that a set of vertices $Q\subseteq V(D)$ is a quasikernel if $Q$ is an independent set and if every vertex of $D$ can be reached from $Q$ by a path of length at most 2.  The Small Quasikernel Conjecture of P.L. Erdős and Székely from 1976 states that every $n$-vertex source-free digraph $D$ contains a quasikernel of size at most $\frac{1}{2}n$.  Despite being posed nearly 50 years ago, very little is known about this conjecture, with the only non-trivial upper bound of $n-\frac{1}{4}\sqrt{n\log n}$ being proven recently by ourself.  We discuss this result together with a number of other related results and open problems around the Small Quasikernel Conjecture.

TRIANGLE RAMSEY NUMBERS OF COMPLETE GRAPHS

Series
Combinatorics Seminar
Time
Friday, September 6, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Shengtong Zhang – Stanford University –

A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that \[r_{K_3}(K_t)=\binom{r(K_t)}3\] for all sufficiently large $t$. 

Our proof employs many recent results on the chromatic number of locally sparse graphs. In particular, I will highlight a new result on the chromatic number of degenerate graphs, which leads to several intriguing open problems.

When do Latin squares have orthogonal mates?

Series
Combinatorics Seminar
Time
Friday, August 23, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Candy Bowtell

A Latin square is an nxn grid filled with n symbols such that each symbol appears exactly once in each row and column. A transversal in a Latin square is a collection of n cells such that each row, column and symbol appears exactly once in the collection.

Latin squares were introduced by Euler in the 1700s and he was interested in the question of when a Latin square decomposes fully into transversals. Equivalently, when does a Latin square have an 'orthogonal mate'?

We'll discuss the history of this question, and some upcoming joint work with Richard Montgomery.

Enumeration of interval graphs and d-representable complexes (Amzi Jeffs, CMU)

Series
Combinatorics Seminar
Time
Friday, April 12, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Speaker
Amzi Jeffs – Carnegie Mellon University –

How many different ways can we arrange n convex sets in R^d? One answer is provided by counting the number of d-representable complexes on vertex set [n]. We show that there are exp(Theta(n^d log n))-many such complexes, and provide bounds on the constants involved. As a consequence, we show that d-representable complexes comprise a vanishingly small fraction of the class of d-collapsible complexes. In the case d = 1 our results are more precise, and improve the previous best estimate for the number of interval graphs.

Erdős–Hajnal and VC-dimension (Tung Nguyen, Princeton)

Series
Combinatorics Seminar
Time
Friday, March 29, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 308
Speaker
Tung Nguyen – Princeton University –

A hereditary class $\mathcal C$ of graphs is said to have the Erdős–Hajnal property if every $n$-vertex graph in $\mathcal C$ has a clique or stable set of size at least $n^c$. We discuss a proof of a conjecture of Chernikov–Starchenko–Thomas and Fox–Pach–Suk that for every $d\ge1$, the class of graphs of VC-dimension at most $d$ has the Erdős–Hajnal property. Joint work with Alex Scott and Paul Seymour.

Colorful Borsuk--Ulam Theorems (Zoe Wellner, CMU)

Series
Combinatorics Seminar
Time
Friday, March 15, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Speaker
Zoe Wellner – Carnegie Mellon University –

 The classical Borsuk--Ulam theorem states that for any continuous map  from the sphere to Euclidean space, $f\colon S^d\to R^d$, there is a pair of antipodal points that are identified, so $f(x)=f(-x)$. We prove a colorful generalization of the Borsuk–Ulam theorem. The classical result has many applications and consequences for combinatorics and discrete geometry and we in turn prove colorful generalizations of these consequences such as the colorful ham sandwich theorem, which allows us to prove a recent result of B\'{a}r\'{a}ny, Hubard, and Jer\'{o}nimo on well-separated measures as a special case, and Brouwer's fixed point theorem, which allows us to prove an alternative between KKM-covering results and Radon partition results.  This is joint work with Florian Frick.

Pages