TBA

TBA

TBA

TBA

We study the minimum size of a maximal independent set in a regular graph, that is, the smallest sets which are both independent and dominating. In a balanced complete bipartite graph, every maximal independent set contains exactly half of the vertices, so large degree alone does not guarantee a small maximal independent set. 

In this talk I will show that regular graphs with bounded codegrees admit much smaller maximal independent sets. Specifically, we show that every $d$-regular graph on $n$ vertices with a moderate codegree bound contains a maximal independent set of size at most $(1+o(1))n (\log d)/d$, as $d$ goes to infinity, and this bound is sharp. The proof is based on a nibble method where, in each step, we sample from the hard-core model. I will also discuss applications.

This is joint work with Matthew Jenssen and Andrey Shapiro.

In this talk I will present and explain some recent results motivated by the fundamental conjecture of Erdős and Hajnal (1969) on the existence of high-girth high-chromatic subgraphs. Formally, their conjecture was that for every positive integer g there is a (smallest) function f_g such that every graph of chromatic number at least f_g(k) has a subgraph of girth at least g and chromatic number at least k. This has only been proved for the smallest case g=4 by Rödl, whose proof yields a bound on f_4(k) which is a tower of height Θ(k^2\log k). In this talk I will present a surprising connection between the problem of finding subgraphs of large odd girth and multicolor Ramsey numbers of odd cycles. Using this connection and at the same time extending the recent first superexponential lower bound on the multicolor Ramey numbers of triangles due to OpenAI to fixed odd cycles, we prove that for every odd g\ge 5 there exists a function h_g growing as a power-tower of height (g-3)/2 such that every graph of chromatic number at least h_g(k) contains a subgraph of odd girth at least g and chromatic number at least k. This proves a conjecture of Mohar and Wu (2018), addresses a problem of Erdős and Hajnal (1975) and in the g=5 case reduces the tower-type bound for f_4(k) to a single exponential. 
We then present a much more general meta theorem, which establishes that for a rich family of graph parameters f, including the fractional chromatic number, the Hall ratio and the strict vector chromatic number (a.k.a. Lovász Theta function of the complement), every graph G with f(G) sufficiently large has a subgraph G' of large odd girth with f(G') still large. 
Along the way, I will also explain OpenAI's construction for the multicolor Ramsey lower bound for triangles. 
Comment: The conjecture of Erdős and Hajnal has recently been disproved using AI, but the first paper with this result was not put on arXiv and appeared on a problem-bounty website. Recently, Nguyen and Walczak wrote the first readable exposition of this disproof. I will not present the disproof in my talk and just briefly mention it along the way.

to follow

to follow

to follow