Seminars and Colloquia by Series

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.

A min-max theorem for circuit decompositions of group-labelled graphs

Series
Graph Theory Seminar
Time
Tuesday, April 19, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCartyUniversity of Warsaw

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.

Fast algorithms for $(\Delta+1)$-edge-coloring

Series
Graph Theory Seminar
Time
Tuesday, April 12, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Abhishek DhawanGeorgia Institute of Technology

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.

Recent advances in Ramsey theory

Series
Graph Theory Seminar
Time
Tuesday, March 29, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Dhruv MubayiUniversity of Illinois at Chicago

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.

A transversal of polytope facets

Series
Graph Theory Seminar
Time
Tuesday, March 15, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Joseph BriggsAuburn University

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.

New and improved bounds on the burning number of a graph

Series
Graph Theory Seminar
Time
Tuesday, February 22, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Zoom
Speaker
Anthony BonatoRyerson University

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.

Approximating TSP walks in sub cubic graphs

Series
Graph Theory Seminar
Time
Tuesday, February 15, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho YooGeorgia Institute of Technology

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}$.

A proof of the Erdős–Faber–Lovász conjecture and related problems

Series
Graph Theory Seminar
Time
Tuesday, December 14, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Abhishek MethukuUniversity of Birmingham

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.

Density and graph edge coloring

Series
Graph Theory Seminar
Time
Tuesday, December 7, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Guangming JingAugusta University

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.

Pages