Seminars and Colloquia by Series

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.

Constructions in combinatorics via neural networks

Series
Graph Theory Seminar
Time
Tuesday, November 30, 2021 - 12:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Adam Zsolt WagnerTel Aviv University

Please Note: Note the unusual time!

Recently, significant progress has been made in the area of machine learning algorithms, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular, recent advances in the field of reinforcement learning have led computers to reach superhuman level play in Atari games and Go, purely through self-play. In this talk I will give a basic introduction to neural networks and reinforcement learning algorithms. I will also indicate how these methods can be adapted to the "game" of trying to find a counterexample to a mathematical conjecture, and show some examples where this approach was successful.

Strong 4-colourings of graphs

Series
Graph Theory Seminar
Time
Tuesday, November 23, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Jessica McDonaldAuburn University

In this talk we’ll discuss strong 4-colourings of graphs and prove two new cases of the Strong Colouring Conjecture. Let H be a graph with maximum degree at most 2, and let G be obtained from H by gluing in vertex-disjoint copies of K_4. We’ll show that if H contains at most one odd cycle of length exceeding 3, or if H contains at most 3 triangles, then G is 4-colourable. This is joint work with Greg Puleo.

Irregular $\mathbf{d_n}$-Process is distinguishable from Uniform Random $\mathbf{d_n}$-graph

Series
Graph Theory Seminar
Time
Tuesday, November 16, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Erlang SuryaGeorgia Institute of Technology

For a graphic degree sequence $\mathbf{d_n}= (d_1 , . . . , d_n)$ of graphs with vertices $v_1 , . . . , v_n$, $\mathbf{d_n}$-process is the random graph process that inserts one edge at a time at random with the restriction that the degree of $v_i$ is at most $d_i$ . In 1999, N. Wormald asked whether the final graph of random $\mathbf{d_n}$-process is "similar" to the uniform random graph with degree sequence $\mathbf{d_n}$ when $\mathbf{d_n}=(d,\dots, d)$. We answer this question for the $\mathbf{d_n}$-process when the degree sequence $\mathbf{d_n}$ that is not close to being regular. We used the method of switching for stochastic processes; this allows us to track the edge statistics of the $\mathbf{d_n}$-process. Joint work with Mike Molloy and Lutz Warnke.

Pages