Georgia Institute of Technology School of Mathematics | Georgia Institute of Technology | Atlanta, GA

TBA

A conjecture by Alon, Krivelevich, and Sudakov in 1999 states that for any graph $H$, there is a constant $c_H > 0$ such that if $G$ is $H$-free of maximum degree $\Delta$, then $\chi(G) \leq c_H \Delta / \log\Delta$. It follows from work by Davies et al. in 2020 that this conjecture holds for $H$ bipartite (specifically $H = K_{t, t}$), with the constant $c_H = (t+o(1))$. We improve this constant to $1 + o(1)$ so it does not depend on $H$, and extend our result to the DP-coloring (also known as correspondence coloring) case introduced by Dvořák and Postle. That is, we show for every bipartite graph $B$, if $G$ is $B$-free with maximum degree $\Delta$, then $\chi_{DP}(G) \leq (1+o(1))\Delta/\log(\Delta)$.

This is joint work with Anton Bernshteyn and Abhishek Dhawan.

A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete "jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollobás, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.

We write $F \rightarrow (H,G)$ for graphs $F$, $G$, and $H$, if for any coloring of the edges of $F$ in red and blue, there is either a red induced copy of $H$ or a blue induced copy of $G$. For graphs $G$ and $H$, let the induced Ramsey number $IR(H,G)$ be the smallest number of vertices in a graph $F$ such that $F \rightarrow (H,G)$. Deuber showed in 1975 that $IR(H,G)$ is well-defined for any graphs $H$ and $G$. Still, the determination of $IR(H,G)$ remains a challenge for most graphs. A striking contrast between induced and non-induced Ramsey numbers was demonstrated by Fox and Sudakov in 2008 by showing that $IR(H,G)$ is superlinear in $n$ when $H$ is a matching on $n$ edges and $G$ is a star on $n$ edges.

In this talk, I will address the case when $G= K_{1,n}$, a star on $n$ edges, for large $n$, and $H$ is a fixed graph. We prove that $$ (\chi(H)-1) n \leq IR(H, K_{1,n}) \leq (\chi(H)-1)^2n + \epsilon n,$$ for any $\epsilon>0$, sufficiently large $n$, and $\chi(H)$ denoting the chromatic number of $H$. The lower bound is asymptotically tight for any fixed bipartite $H$. The upper bound is attained up to a constant factor, for example when $H$ is a clique.

This is a joint work with Izolda Gorgol.