Seminars and Colloquia by Series

Constructing minimally 3-connected graphs

Series
Graph Theory Seminar
Time
Tuesday, February 23, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Sandra KinganBrooklyn College, CUNY

A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex of degree at least 4. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of $G'$ from the cycles of $G$, where $G'$ is obtained from $G$ by one of the two operations above.  We eliminate isomorphic duplicates using certificates generated by McKay's isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with $n$ vertices and $m$ edges from the non-isomorphic minimally 3-connected graphs with $n-1$ vertices and $m-2$ edges, $n-1$ vertices and $m-3$ edges, and $n-2$ vertices and $m-3$ edges. In this talk I will focus primarily on the theorems behind the algorithm. This is joint work with Joao Costalonga and Robert Kingan.

Fractional chromatic number of graphs of bounded maximum degree

Series
Graph Theory Seminar
Time
Tuesday, February 16, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Zdeněk DvořákCharles University

By the well-known theorem of Brooks, every graph of maximum degree Δ ≥ 3 and clique number at most Δ has chromatic number at most Delta. It is natural to ask (and is the subject of a conjecture of Borodin and Kostochka) whether this bound can be improved for graphs of clique number at most Δ - 1. While there has been little progress on this conjecture, there is a number of interesting results on the analogous question for the fractional chromatic number. We will report on some of them, including a result by myself Bernard Lidický and Luke Postle that except for a finite number of counterexamples, every connected subcubic triangle-free graph has fractional chromatic number at most 11/4.

Progress towards Nash-Williams' conjecture on triangle decompositions

Series
Graph Theory Seminar
Time
Tuesday, February 9, 2021 - 12:30 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Michelle DelcourtRyerson University

Please Note: Note the unusual time!

Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large, triangle divisible graph on $n$ vertices with minimum degree at least $0.75 n$ admits a triangle decomposition. In the light of recent results, the fractional version of this problem is of central importance. A fractional triangle decomposition is an assignment of non-negative weights to each triangle in a graph such that the sum of the weights along each edge is precisely one.

We show that for any graph on n vertices with minimum degree at least $0.827327 n$ admits a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus, this implies that for every sufficiently large triangle divisible graph on $n$ vertices with minimum degree at least $0.82733 n$ admits a triangle decomposition. This is a significant improvement over the previous asymptotic result of Dross showing the existence of fractional triangle decompositions of sufficiently large graphs with minimum degree more than $0.9 n$. This is joint work with Luke Postle.

Prague dimension of random graphs

Series
Graph Theory Seminar
Time
Tuesday, January 26, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
He GuoGeorgia Institute of Technology

The Prague dimension of graphs was introduced by Nešetřil, Pultr and Rödl in the 1970s. Proving a conjecture of Füredi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order $n/\log n$ for constant edge-probabilities. The main new proof ingredient is a Pippenger–Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size $O(\log n)$. Based on joint work with Kalen Patton and Lutz Warnke.

Asymptotic dimension of minor-closed families and beyond

Series
Graph Theory Seminar
Time
Tuesday, December 8, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Chun-Hung LiuTexas A&M University

The asymptotic dimension of metric spaces is an important notion in geometric group theory. The metric spaces considered in this talk are the ones whose underlying spaces are the vertex-sets of (edge-)weighted graphs and whose metrics are the distance function in weighted graphs. A standard compactness argument shows that it suffices to consider the asymptotic dimension of classes of finite weighted graphs. We prove that the asymptotic dimension of any minor-closed family of weighted graphs, any class of weighted graphs of bounded tree-width, and any class of graphs of bounded layered tree-width are at most 2, 1,and 2, respectively. The first result solves a question of Fujiwara and Papasoglu; the second and third results solve a number of questions of Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. These bounds for asymptotic dimension are optimal and generalize and improve some results in the literature, including results for Riemannian surfaces and Cayley graphs of groups with a forbidden minor.

Embedding spanning structures into vertex-ordered graphs

Series
Graph Theory Seminar
Time
Tuesday, December 1, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Andrew TreglownUniversity of Birmingham

Over recent years there has been much interest in both Turán and Ramsey properties of vertex ordered graphs (i.e., graphs equipped with an ordering of their vertex set). In a recent paper, József Balogh, Lina Li and I initiated the study of embedding spanning structures into vertex ordered graphs. In particular, we introduced a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect $H$-tiling in an ordered graph. In this talk I will discuss this work, in particular emphasizing how we adapt the regularity and absorbing methods to be applicable in the ordered setting.

Weak saturation numbers of complete bipartite graphs

Series
Graph Theory Seminar
Time
Tuesday, November 24, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Taísa MartinsUniversidade Federal Fluminense

The notion of weak saturation was introduced by Bollobás in 1968. A graph $G$ on $n$ vertices is weakly $F$-saturated if the edges of $E(K_n) \setminus  E(G)$ can be added to $G$, one edge at a time, in such a way that every added edge creates a new copy of $F$. The minimum size of a weakly $F$-saturated graph $G$ of order $n$ is denoted by $\mathrm{wsat}(n, F)$. In this talk, we discuss the weak saturation number of complete bipartite graphs and determine $\mathrm{wsat}(n, K_{t,t})$ whenever $n > 3t-4$. For fixed $1

Transversal $C_k$-factors in subgraphs of the balanced blowup of $C_k$

Series
Graph Theory Seminar
Time
Tuesday, November 17, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Theo MollaUniversity of South Florida

Call a blowup of a graph $F$ an $n$-blowup if each part has size $n$. For a subgraph $G$ of a blowup of $F$, we define the minimum partial degree of $G$ to be the smallest minimum degree over the bipartite subgraphs of $G$ that correspond to edges of $F$. Johannson proved that if the minimum partial degree of a spanning subgraph of the $n$-blowup of a triangle is $2n/3 + n^{1/2}$, then it contains a collection of $n$ vertex disjoint triangles. Fischer's Conjecture, which was proved by Keevash and Mycroft in 2015, is a generalization of this result to complete graphs larger than the triangle. Another generalization, conjectured independently by Fischer and Häggkvist, is the following: If $G$ is a spanning subgraph of the $n$-blowup of $C_k$ with minimum partial degree $(1 + 1/k)n/2 + 1$, then $G$ contains $n$ vertex disjoint copies of $C_k$ that each intersect each of the $k$ parts. In this talk, we will show that this conjecture holds asymptotically. We will also discuss related conjectures and results. 

This is joint work with Beka Ergemlidze.

Universal graphs and planarity

Series
Graph Theory Seminar
Time
Tuesday, November 10, 2020 - 12:30 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Louis EsperetUniversité Grenoble Alpes

Please Note: Note the unusual time!

The following are two classical questions in the area of universal graphs.

1. What is the minimum number of vertices in a graph that contains all $n$-vertex planar graphs as induced subgraphs?

2. What is the minimum number of edges in a graph that contains all $n$-vertex planar graphs as subgraphs?

We give nearly optimal constructions for each problem, i.e. with $n^{1+o(1)}$ vertices for Question 1 and $n^{1+o(1)}$ edges for Question 2. The proofs combine a recent structure theorem for planar graphs (of independent interest) with techniques from data structures.

Joint work with V. Dujmovic, C. Gavoille, G. Joret, P. Micek, and P. Morin.

Forbidden traces in hypergraphs

Series
Graph Theory Seminar
Time
Tuesday, November 3, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Ruth LuoUniversity of California, San Diego

Let $F$ be a graph. We say a hypergraph $H$ is a trace of $F$ if there exists a bijection $\phi$ from the edges of $F$ to the hyperedges of $H$ such that for all $xy \in E(F)$, $\phi(xy) \cap V(F) = \{x,y\}$. In this talk, we show asymptotics for the maximum number of edges in an $r$-uniform hypergraph that does not contain a trace of $F$. We also obtain better bounds in the case $F = K_{2,t}$. This is joint work with Zoltán Füredi and Sam Spiro. 

Pages