Georgia Institute of Technology College of Sciences

Ramsey proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either a complete graph on r vertices or an independent set with r vertices.  It is well known that every sufficiently large, connected graph contains an induced subgraph isomorphic to one of a large complete graph, a large star, and a long path.  We prove an analogous result for 2-connected graphs.  Similarly, for infinite graphs, every infinite connected graph contains an induced subgraph isomorphic to one of the following: an infinite complete graph, an infinite star, and a ray.  We also prove an analogous result for infinite 2-connected graphs.

Many results in extremal graph theory build on supersaturation of subgraphs. In other words, when a graph is dense enough, it contains many copies of a certain subgraph and these copies are then used as building blocks to force another subgraph of interest. Recently more success is found within this approach where one utilizes not only the large number of copies of a certain subgraph but a well-distributed collection of them to force the desired subgraph. We discuss some recent progress of this nature. The talk is built on joint work with Sean Longbrake, and with Sean Longbrake and Jie Ma.

The edge-coloring problem (ECP) for a multigraph $G=(V, E)$ is to color its edges with minimum number of colors such that no two adjacent vertices receive the same color. ECP can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) of $G$, denoted by $\chi^{\prime}(G)$ (resp. $\chi^*(G)$). Let $\Delta(G)$ be the maximum degree of $G$ and let $ \mathcal{W}^*(G) $ be the fractional density of $G$, defined by $$ \mathcal{W}^*(G) = \max _{U \subseteq V,|U| \geq 2}\frac{|E(U)|}{\lfloor|U|/2\rfloor}. $$ Seymour showed that $\chi^*(G)=\max \{\Delta(G), \mathcal{W}^*(G)\}$. Moreover, the Goldberg-Seymour Conjecture is confirmed Chen, Jing, and Zang states that $\chi^{\prime}(G) \leq \max \{\Delta(G)+1,\lceil\mathcal{W}^*(G)\rceil\}$. Chen, Zang and Zhao developed an algorithm that calculates $ \mathcal{W}^*(G) $ in strongly polynomial time. Inspired by their results, we consider the fractional $ f $-edge-coloring problem ($ f $-FECP) for a given function $ f:V\to \mathbb N_+ $, which is a generalization of FECP: each spanning subgraph induced by a color class has degree at most $ f(v) $ at each vertex $ v\in V $. We give a strongly polynomial-time algorithm for calculating the corresponding fractional $ f $-density $$ \mathcal{W}^*_{f}(G)=\max _{U \subseteq V,|U| \geq 2}\frac{|E(U)|}{\lfloor f(U) / 2\rfloor}. $$

An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clog n (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a C-Ramsey graph. This brings together two ongoing lines of research: the study of "random-like’’ properties of Ramsey graphs and the study of small-ball probability for low-degree polynomials of independent random variables.

The proof proceeds via an "additive structure’’ dichotomy on the degree sequence, and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation. One of the consequences of our result is the resolution of an old conjecture of Erdos and McKay, for which he offered one of his notorious monetary prizes.
(Joint work with Matthew Kwan, Ashwin Sah and Lisa Sauermann)