Seminars and Colloquia by Series

Anticoncentration in Ramsey graphs and a proof of the Erdos-McKay conjecture

Series
Graph Theory Seminar
Time
Tuesday, November 29, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Mehtaab SawhneyMassachusetts Institute of Technology

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)

On the coequal values of total chromatic number and chromatic index.

Series
Graph Theory Seminar
Time
Tuesday, November 15, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yanli HaoGeorgia State University

The chromatic index $\chi'(G)$ of a graph $G$ is the least number of colors assigned to the edges of $G$ such that no two adjacent edges receive the same color. The total chromatic number $\chi''(G)$ of a graph $G$ is the least number of colors assigned to the edges and vertices of $G$ such that no two adjacent edges receive the same color, no two adjacent vertices receive the same color and no edge has the same color as its two endpoints. The chromatic index and the total chromatic number are two of few fundamental graph parameters, and their correlation has always been a subject of intensive study in graph theory.

By definition, $\chi'(G) \le \chi''(G)$ for every graph $G$. In 1984,  Goldberg conjectured that for any multigraph $G$, if $\chi'(G) \ge \Delta(G) +3$ then $\chi''(G) = \chi'(G)$. We show that Goldberg's conjecture is asymptotically true. More specifically,  we prove that for a multigraph $G$ with maximum degree $\Delta$ sufficiently large, $\chi''(G) = \chi'(G)$ provided $\chi'(G) \ge \Delta + 10\Delta^{35/36}$.  When $\chi'(G) \ge \Delta(G) +2$, the chromatic index $\chi'(G)$ is completely determined by the fractional chromatic index. Consequently,   the total chromatic number $\chi''(G)$ can be computed in polynomial-time in this case.

Dyadic Matroids with Spanning Cliques

Series
Graph Theory Seminar
Time
Tuesday, October 25, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Kevin GraceVanderbilt University

The Matroid Minors Project of Geelen, Gerards, and Whittle describes the structure of minor-closed classes of matroids representable by a matrix over a fixed finite field. To use these results to study specific classes, it is important to study the matroids in the class containing spanning cliques. A spanning clique of a matroid M is a complete-graphic restriction of M with the same rank as M.

 

In this talk, we will describe the structure of dyadic matroids with spanning cliques. The dyadic matroids are those matroids that can be represented by a real matrix each of whose nonzero subdeterminants is a power of 2, up to a sign. A subclass of the dyadic matroids is the signed-graphic matroids. In the class of signed-graphic matroids, the entries of the matrix are determined by a signed graph. Our result is that dyadic matroids with spanning cliques are signed-graphic matroids and a few exceptional cases.

 

The main results in this talk will come from joint work with Ben Clark, James Oxley, and Stefan van Zwam. This talk will include a brief introduction to matroids.

Progress towards the Burning Number Conjecture

Series
Graph Theory Seminar
Time
Tuesday, October 11, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Jérémie TurcotteMcGill University

The burning number $b(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ can be covered by $k$ balls of radii respectively $0,\dots,k-1$, and was introduced independently by Brandenburg and Scott at Intel as a transmission problem on processors \cite{alon} and Bonato, Janssen and Roshanbin as a model for the spread of information in social networks.

The Burning Number Conjecture \cite{bonato} claims that $b(G)\leq \left\lceil\sqrt{n}\right\rceil$, where $n$ is the number of vertices of $G$. This bound tight for paths. The previous best bound for this problem, by Bastide et al. \cite{bastide}, was $b(G)\leq \sqrt{\frac{4n}{3}}+1$.

We prove that the Burning Number Conjecture holds asymptotically, that is $b(G)\leq (1+o(1))\sqrt{n}$.

Following a brief introduction to graph burning, this talk will focus on the general ideas behind the proof.

The complexity of list-5-coloring with forbidden induced substructures

Series
Graph Theory Seminar
Time
Tuesday, October 4, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Yanjia LiGeorgia Tech

The list-$k$-coloring problem is to decide, given a graph $G$ and a list assignment $L$ of $G$ from $V(G)$ to subsets of $\{1,...,k\}$, whether $G$ has a coloring $f$ such that $f(v)$ in $L(v)$ for all $v$ in $V(G)$. The list-$k$-coloring problem is a generalization of the $k$-coloring problem. Thus for $k\geq 3$, both the $k$-coloring problem and the list-$k$-coloring problem are NP-Hard. This motivates studying the complexity of these problems restricted to graphs with a fixed forbidden induced subgraph $H$, which are called $H$-free graphs.

In this talk, I will present a polynomial-time algorithm to solve the list-5-coloring $H$-free graphs with $H$ being the union of $r$ copies of mutually disjoint 3-vertex paths. Together with known results, it gives a complete complexity dichotomy of the list-5-coloring problem restricted to $H$-free graphs. This is joint work with Sepehr Hajebi and Sophie Spirkl.

New lift matroids for gain graphs

Series
Graph Theory Seminar
Time
Tuesday, September 20, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zach WalshGeorgia Tech

Given a graph G with edges labeled by a group, a construction of Zaslavsky gives a rank-1 lift of the graphic matroid M(G) that respects the group-labeling. For which finite groups can we construct a rank-t lift of M(G) with t > 1 that respects the group-labeling? We show that this is possible if and only if the group is the additive subgroup of a non-prime finite field. We assume no knowledge of matroid theory.

Unifying and localizing two planar list colouring results of Thomassen

Series
Graph Theory Seminar
Time
Tuesday, September 6, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Evelyne Smith-RobergeGeorgia Tech

Thomassen famously showed that every planar graph is 5-choosable, and that every planar graph of girth at least five is 3-choosable.  These theorems are best possible for uniform list assignments: Voigt gave a construction of a planar graph that is not 4-choosable, and of a planar graph of girth four that is not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex is contained. I will present a local list colouring theorem that unifies the two theorems of Thomassen mentioned above and discuss some of the highlights and difficulties of the proof. This is joint work with Luke Postle.

Thresholds for Latin squares and Steiner triple systems

Series
Graph Theory Seminar
Time
Tuesday, August 30, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tom KellyGeorgia Tech

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.  

Concentration of the Chromatic Number of Random Graphs

Series
Graph Theory Seminar
Time
Tuesday, May 17, 2022 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Lutz WarnkeUCSD
What can we say about the chromatic number \chi(G_{n,p}) of an n-vertex binomial random graph G_{n,p}? From a combinatorial perspective, it is natural to ask about the typical value of \chi(G_{n,p}), i.e., upper and lower bounds that are close to each other. From a probabilistic combinatorics perspective, it is also natural to ask about the concentration of \chi(G_{n,p}), i.e., how much this random variable varies. Among these two fundamental questions, significantly less is known about the concentration question that we shall discuss in this talk. In terms of previous work, in the 1980s Shamir and Spencer proved that the chromatic number of the binomial random graph G_{n,p} is concentrated in an interval of length at most \omega\sqrt{n}, and in the 1990s Alon showed that an interval of length \omega\sqrt{n}/\log n suffices for constant edge-probabilities p\in (0,1). In this talk, we prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case p=p(n) \to 0, and also discuss several intriguing questions about the chromatic number \chi(G_{n,p}) that remain open. Based on joint work with Erlang Surya; see https://arxiv.org/abs/2201.00906

On the size Ramsey number of graphs

Series
Graph Theory Seminar
Time
Tuesday, April 26, 2022 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005/Zoom (hybrid)
Speaker
Meysam MiralaeiInstitute for Research in Fundamental Sciences, Iran

Please Note: Note the unusual time!

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.

Pages