Abstract: TBA

Abstract: The Hajnal-Szemer\'edi theorem says that every graph $G$ has an equitable $(\Delta(G)+1)$-coloring.  This is one of the cornerstone results in graph theory and has been applied in a wide variety of settings.  In particular, it is a key ingredient in Koml\'os, S\'ark\"ozy, and Szemer\'edi's proof of the P\'osa-Seymour conjecture on powers of Hamiltonian cycles.  

If we attempt to generalize the Hajnal-Szemer\'edi theorem to the setting of digraphs, we suddenly face many choices.  Should we replace maximum degree with maximum out-degree, or maximum total-degree, or maximum semi-degree, or something else?  Should we replace equitable coloring with equitable acyclic coloring, or something more restrictive?  What happens when we restrict our attention to oriented graphs?  Which of these versions would be useful for proving an analogue of the P\'osa-Seymour conjecture for directed/oriented graphs?  For that matter, what is the correct analogue of the P\'osa-Seymour conjecture for directed/oriented graphs?

I will discuss our attempts to answer these questions and highlight what remains to be done.  

This is based on a body of joint work with Andrzej Czygrinow, Jie Han, Hal Kierstead, Allan Lo, Theo Molla, Sim\'on Piga, and Andrew Treglown.

Abstract: In 1967, Gerencsér and Gyárfás asked: what is the largest number f(n,r) such that every r-edge-coloring of the complete graph on n vertices contains a monochromatic component with at least f(n,r) vertices? In 1989, Füredi showed that f(n,r) = n/(r-1)+O_r(1) when an affine plane of order r-1 exists, but that otherwise f(n,r) is significantly larger. We improve on Füredi's bound for all r such that an affine plane of order r-1 does not exist, and we go further for the first open case, r=7. We also supply an improved upper bound on f(n,r) for such r. This is joint work with Dan Kral and Sammy Luo.

Abstract: We study the codegree Turán density of C_l^r, the r-uniform hypergraph tight cycle of length l. A result of Han, Lo, and Sanhueza-Matamala states that if l is sufficiently large and r/gcd(r,l) is even, then the codegree Turán density of C_l^r is 1/2. We prove that whenever the latter assumption is not satisfied, there is a significant drop in the codegree Turán density. That is, if l is sufficiently large and r/gcd(r,l) is odd, then the codegree Turán density of C_l^r can be at most 1/3. Moreover, this bound is tight for infinitely many uniformities r and all sufficiently large l in the corresponding residue classes modulo r. Our proof makes use of a connection between Turán-type theorems and group theory.

This is a joint work with József Balogh and Maya Sankar.

Abstract: Schrijver proved in 1978 that for all $n\ge 2k$, the subgraph of the Kneser graph KG(n,k) induced on the 2-stable subsets has chromatic number $n-2k+2$. Generalizing this result, Meunier conjectured in 2011 that for $n\ge sk$, the chromatic number of the $k$-uniform $s$-stable Kneser graphs over $[n]$ is $n-sk+s$. The conjecture was previously proved for all $s \ge 4$ when $n$ is large enough. We prove the conjecture for $s=3$ and $n$ large enough, or when $k=s=3$. To this end, we prove a version of the Hilton-Milner theorem for stable sets. Joint with Wei-Chia Chen and Alex Parker.

Abstract: Given a bipartite graph $H$ and a natural number $s$, let $\ex^*(n,H,s)$ denote the maximum number of edges in an $n$-vertex graph that contains neither $K_{s,s}$ nor an induced copy of $H$. Hunter, Milojevi\'c, Sudakov, and Tomon conjectured that $\ex^*(n,H,s)=O_{H,s}(\ex(n,H))$ whenever $H$ is connected. Motivated by this conjecture and the rational exponents conjecture, Dong, Gao, Li, and Liu conjectured that for every rational $r\in (1,2)$ there is a bipartite graph $H$ and an $s_0$ such that $\ex^*(n,H,s)=\Theta(n^r)$ for all $s\geq s_0$.

We prove that the latter conjecture holds for all rationals $r=2-a/b$, where $a,b\in\mathbb{N}$ satisfy $b\geq \max\{a,(a-1)^2\}$. Our result extends a well-known result of Conlon and Janzer to the induced setting and adds more evidence to support the former conjecture.

This is joint work with Sean Longbrake.

Abstract: Basic Tur\'an theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Tur\'an question asks how many copies of a fixed subgraph $H$ the graph can have, given certain restrictions. There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of ${\bf N}_{\mathcal P}(n,H)$, which denotes the maximum number of copies of $H$ in an $n$-vertex planar graph. In particular, we will focus on the case where $H$ is a cycle.

It was determined that ${\bf N}_{\mathcal P}(n,C_{2m})=(n/m)^m+o(n^m)$ for small values of $m$ by Cox and Martin and resolved for all $m$ by Lv, Gy\H{o}ri, He, Salia, Tompkins, and Zhu.

The case of $H=C_{2m+1}$ is more difficult and it is conjectured that ${\bf N}_{\mathcal P}(n,C_{2m+1})=2m(n/m)^m+o(n^m)$. 

We will discuss recent progress on this problem, including verification of the conjecture in the case where $m=3$ and $m=4$ and a lemma which reduces the solution of this problem for any $m$ to a so-called ``maximum likelihood'' problem. The maximum likelihood problem is, in and of itself, an interesting question in random graph theory.

Abstract: TBA

Abstract: Given integers r>d and an r-partite graph, an independent (r-d)-transversal or (r-d)-IT is an independent set of size r-d that intersects each part in at most one vertex. We show that every r-partite graph with maximum degree \Delta and parts of size n contains an (r-d)-IT if n> 2\Delta (1- 1/q), provided q= [ r/(d+1) ] \ge 4r/(4d+5). This is tight when q is even and extends a classical result of Haxell for the d=0 case. When q= [ r/ (d+1) ] \ge (6r+6d+7)/(6d+7) is odd, we show that n> 2\Delta(1- 1/(q-1}) guarantees an (r-d)-IT in any r-partite graph. This is also tight and extends a result of Haxell and Szab\'o for the d=0 case. In addition, we show that n> 5\Delta/4 guarantees a 5-IT in any 6-partite graph and this bound is tight, answering a question of Lo, Treglown and Zhao.

Joint work with Penny Haxell and Arpit Mittal.

Abstract: In the 1970s, Erdos and Sos asked for the maximum size of a family of k-element subsets of an n-set which does not contain two sets with intersection size 1. Frankl showed that the maximum size is $\binom{n-2}{k-2}$ for $k\ge 4$ and $n$ very large. Using Schrijver's variant of the Lov\'asz number, we show that the maximum size is also $\binom{n-2}{k-2}$ when $n$ is very small. As a consequence, we can show that for sufficiently large $k$, the maximum size of a set family containing no singleton intersection is $\binom{n-2}{k-2}$ when $n\ge 3k-3$, which is the best possible threshold. 

Abstract: In this talk we will describe a practical approach for solving large flag algebras problems. A typical application of flag algebras requires to enumerate all (hyper) graphs on n vertices up to isomorphism for some fixed value of n. Larger n typically yields better result. However, increasing n increases demand on hardware resources. Our approach is significantly more RAM efficient than typical methods. This is particularly important in these days when AI data centers are causing RAM shortages and price spikes of RAM. We will describe improvements obtained using this approach.

The main results mentioned in this talk are joint work with Jan Volec.

Abstract: The Acyclic Edge Coloring Conjecture, posed independently by Fiam\v{c}ik in 1978 and Alon, Sudakov and Zaks in 2001, asserts that every graph can be properly edge colored with $\Delta + 2$ colors such that there is no bicolored cycle. Over the years, this conjecture has attracted much attention. We prove that the conjecture holds asymptotically, that is $(1 + o(1))\Delta$ colors suffice. This is joint work with Michelle Delcourt and Luke Postle.