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 Warnke – UCSD – lwarnke@ucsd.edu
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.
This talk focuses on Eulerian graphs whose arcs are directed and labelled in a group. Each circuit yields a word over the group, and we say that a circuit is non-zero if this word does not evaluate to 0. We give a precise min-max theorem for the following problem. Given a vertex $v$, what is the maximum number of non-zero circuits in a circuit decomposition where each circuit begins and ends at $v$? This is joint work with Jim Geelen and Paul Wollan. Our main motivation is a surprising connection with vertex-minors which is due to Bouchet and Kotzig.
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.
Ramsey theory studies the paradigm that every sufficiently large system contains a well-structured subsystem. Within graph theory, this translates to the following statement: for every positive integer $s$, there exists a positive integer $n$ such that for every partition of the edges of the complete graph on $n$ vertices into two classes, one of the classes must contain a complete subgraph on $s$ vertices. Beginning with the foundational work of Ramsey in 1928, the main question in the area is to determine the smallest $n$ that satisfies this property.
For many decades, randomness has proved to be the central idea used to address this question. Very recently, we proved a theorem which suggests that "pseudo-randomness" and not complete randomness may in fact be a more important concept in this area. This new connection opens the possibility to use tools from algebra, geometry, and number theory to address the most fundamental questions in Ramsey theory. This is joint work with Jacques Verstraete.
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.
Graph burning is a simplified model for the spread of influence in a network. Associated with the process is the burning number, which quantifies the speed at which the influence spreads to every vertex. The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil$. While the conjecture remains open, we prove the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1$, improving on the previously known $\sqrt{3n/2}+O(1)$ bound.
We prove that every simple 2-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree 2 has a TSP walk of length at most $\frac{5n+n_2}{4}-1$, confirming a conjecture of Dvořák, Král', and Mohar. This bound is best possible; there are infinitely many subcubic and cubic graphs whose minimum TSP walks have lengths $\frac{5n+n_2}{4}-1$ and $\frac{5n}{4} - 2$ respectively. We characterize the extremal subcubic examples meeting this bound. We also give a quadratic-time combinatorial algorithm for finding such a TSP walk. In particular, we obtain a $\frac{5}{4}$-approximation algorithm for the graphic TSP on simple cubic graphs, improving on the previously best known approximation ratio of $\frac{9}{7}$.
Please Note: Note the unusual time!
The famous Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will briefly sketch a proof of this conjecture for every large n. If time permits, I will also talk about our solution to a problem of Erdős from 1977 about chromatic index of hypergraphs with bounded codegree. Joint work with D. Kang, T. Kelly, D.Kuhn and D. Osthus.
Given a multigraph $G=(V,E)$, the chromatic index $\chi'(G)$ is the minimum number of colors needed to color the edges of $G$ such that no two incident edges receive the same color. Let $\Delta(G)$ be the maximum degree of $G$ and let $\Gamma(G):=\max \big\{\frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hskip 2mm
{\rm and \hskip 2mm odd} \big\}$. $\Gamma(G)$ is called the density of $G$. Clearly, the density is a lower bound for the chromatic index $\chi'(G)$. Moreover, this value can be computed in polynomial time. Goldberg and Seymour in the 1970s conjectured that $\chi'(G)=\lceil\Gamma(G)\rceil$ for any multigraph $G$ with $\chi'(G)\geq\Delta(G)+2$, known as the Goldberg-Seymour conjecture. In this talk we will discuss this conjecture and some related open problems. This is joint work with Guantao Chen and Wenan Zang.