### TBA by Michael Simkin

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

- You are here:
- Home
- News & Events

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

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

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\H{o}s and Sz\'ekely 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.

- Series
- Combinatorics Seminar
- Time
- Friday, September 13, 2024 - 15:15 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Sam van der Poel, Matt Baker, Logan Post – Georgia Tech

Three fifteen-minute talks by local speakers.

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

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.

- Series
- Combinatorics Seminar
- Time
- Friday, August 30, 2024 - 15:15 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Cheng Mao, Josephine Yu, Tantan Dai – Georgia Tech

Three fifteen-minute talks by local speakers.

- 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.

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

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.

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

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.

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

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.

- Series
- Combinatorics Seminar
- Time
- Friday, March 1, 2024 - 15:15 for 1 hour (actually 50 minutes)
- Location
- Skiles 308
- Speaker
- Matija Bucic – Princeton University – mb5225@princeton.edu

An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of (log n)^(2+o(1)) for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the o(1) term in Tomon's bound. We show that the answer to the question is equal to (log n)^(1+o(1)).

Joint work with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.