Georgia Institute of Technology College of Sciences

An order-n Latin square is an $n \times n$ matrix with entries from a set of $n$ symbols, such that each row and each column contains each symbol exactly once.  Suppose that $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k \in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,j\in[n]$.  How likely does there exist an order-$n$ Latin square where the entry in the $i$th row and $j$th column lies in $L_{i,j}$?  This question was initially raised by Johansson in 2006, and later Casselgren and H{\"a}ggkvist and independently Luria and Simkin conjectured that $\log n / n$ is the threshold for this property.  In joint work with Dong-yeap Kang, Daniela K\"{u}hn, Abhishek Methuku, and Deryk Osthus, we proved that for some absolute constant $C$, if $p > C \log^2 n / n$, then asymptotically almost surely there exists such a Latin square.  We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs.  

For given graphs $G$ and $H$ and a graph $F$, we say that $F$ is Ramsey for $(G, H)$ and we write $F \longrightarrow (G,H)$, if for every $2$-edge coloring of $F$, with colors red and blue, the graph $F$ contains either a red copy of $G$ or a blue copy of $H$. A natural question is how few vertices can a graph $F$ have, such that $F \longrightarrow (G,H)$? Frank P. Ramsey studied this question and proved that for given graphs $G$ and $H$, there exists a positive integer $n$ such that for the complete graph $K_n$ we have $K_n \longrightarrow (G,H)$. The smallest such $n$ is known as the Ramsey number of $G$, $H$ and is denoted by $R(G, H)$. Instead of minimizing the number of vertices, one can ask for the minimum number of  edges of such a graph, i.e. can we find a graph which possibly has more vertices than $R(G, H)$, but has fewer edges and still is Ramsey for $(G,H)$? How many edges suffice to construct a graph which is Ramsey for $(G,H)$? The attempts at answering the last question give rise to the notion of size-Ramsey number of graphs. In 1978, Erdős, Faudree, Rousseau and Schelp pioneered the study of the size-Ramsey number to be the minimum number of edges in a graph $F$, such that $F$ is Ramsey for $(G,H)$. In this talk, first I will give a short history about the size Ramsey number of graphs with a special focus on sparse graphs. Moreover, I will talk about the multicolor case of the size Ramsey number of cycles with more details.

Vizing's Theorem states that simple graphs can be edge-colored using $\Delta+1$ colors. The problem of developing efficient $(\Delta+1)$-edge-coloring algorithms has been a major challenge. The algorithms involve iteratively finding small subgraphs $H$ such that one can extend a partial coloring by modifying the colors of the edges in $H$. In a recent paper, Bernshteyn showed one can find $H$ such that $e(H) = \mathrm{poly}(\Delta)(\log n)^2$.  With this result, he defines a $(\Delta+1)$-edge-coloring algorithm which runs in $\mathrm{poly}(\Delta, \log n)$ rounds. We improve on this by showing we can find $H$ such that $e(H) = \mathrm{poly}(\Delta)\log n$. As a result, we define a distributed algorithm that improves on Bernshteyn's by a factor of $\mathrm{poly}(\log n)$. We further apply the idea to define a randomized sequential algorithm which computes a proper $(\Delta+1)$-edge-coloring in $\mathrm{poly}(\Delta)n$ time. Under the assumption that $\Delta$ is a constant, the previous best bound is $O(n\log n)$ due to Sinnamon.

Suppose you have a subset $S$ of the vertices of a polytope which contains at least one vertex from every face. How large must $S$ be? We believe, in the worst case, about half of the number of vertices of the polytope. But we don’t really know why. We have found some situational evidence, but also some situational counter-evidence. This is based on joint work with Michael Dobbins and Seunghun Lee.