Seminars and Colloquia by Series

TBA by Fan Wei

Series
Graph Theory Seminar
Time
Tuesday, May 4, 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
Fan WeiPrinceton University

TBA

TBA by Bernard Lidický

Series
Graph Theory Seminar
Time
Tuesday, April 27, 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
Bernard LidickýIowa State University

TBA

TBA by David Wood

Series
Graph Theory Seminar
Time
Tuesday, April 20, 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
David WoodMonash University

TBA

Description:Chromatic index of dense quasirandom graphs

Series
Graph Theory Seminar
Time
Tuesday, April 13, 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
Songling ShanIllinois State University

Let $G$ be a simple graph with maximum degree $\Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>\Delta(G)\lfloor |V(H)|/2 \rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ on $n$ vertices with $\Delta(G)>n/3$ has chromatic index $\Delta(G)$ if and only if $G$ contains no overfull subgraph. Glock, Kühn and Osthus in 2016 showed that the conjecture is true for dense quasirandom graphs with even order, and they conjectured that the same should hold for such graphs with odd order. We show that the conjecture of Glock, Kühn and Osthus is affirmative.

Coloring graphs with forbidden bipartite subgraphs

Series
Graph Theory Seminar
Time
Tuesday, April 6, 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
James AndersonGeorgia Institute of Technology

A conjecture by Alon, Krivelevich, and Sudakov in 1999 states that for any graph $H$, there is a constant $c_H > 0$ such that if $G$ is $H$-free of maximum degree $\Delta$, then $\chi(G) \leq c_H \Delta / \log\Delta$. It follows from work by Davies et al. in 2020 that this conjecture holds for $H$ bipartite (specifically $H = K_{t, t}$), with the constant $c_H = (t+o(1))$. We improve this constant to $1 + o(1)$ so it does not depend on $H$, and extend our result to the DP-coloring (also known as correspondence coloring) case introduced by Dvořák and Postle. That is, we show for every bipartite graph $B$, if $G$ is $B$-free with maximum degree $\Delta$, then $\chi_{DP}(G) \leq (1+o(1))\Delta/\log(\Delta)$.

This is joint work with Anton Bernshteyn and Abhishek Dhawan.

Intersecting families of sets are typically trivial

Series
Graph Theory Seminar
Time
Tuesday, March 30, 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
Lina LiUniversity of Waterloo

A family of subsets of $[n]$ is intersecting if every pair of its members has a non-trivial intersection. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl-Kupavskii and Balogh-Das-Liu-Sharifzadeh-Tran independently showed that for $n \geq 2k + c\sqrt{k\ln k}$, almost all $k$-uniform intersecting families are stars. Significantly improving their results, we show that the same conclusion holds for $n \geq 2k + 100 \ln k$. Our proof uses the Sapozhenko’s graph container method and the Das-Tran removal lemma.

This is joint work with József Balogh, Ramon I. Garcia and Adam Zsolt Wagner.

Speeds of hereditary properties and mutual algebricity

Series
Graph Theory Seminar
Time
Tuesday, March 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
Caroline TerryOhio State University

A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete "jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollobás, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.

Degree conditions for Hamilton cycles

Series
Graph Theory Seminar
Time
Tuesday, March 9, 2021 - 23: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
Richard LangHeidelberg University

Please Note: Note the unusual time!

A classic theorem of Dirac (1952) states that a graph in which every vertex is connected to half of the other vertices contains a Hamilton cycle. Over the years this result has been generalized in many interesting ways. In this talk, I will give an overview of these efforts and then explore some of the more recent developments.

Induced Ramsey numbers for a star versus a fixed graph

Series
Graph Theory Seminar
Time
Tuesday, March 2, 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
Maria AxenovichKarlsruhe Institute of Technology

We write $F \rightarrow (H,G)$ for graphs $F$, $G$, and $H$, if for any coloring of the edges of $F$ in red and blue, there is either a red induced copy of $H$ or a blue induced copy of $G$. For graphs $G$ and $H$, let the induced Ramsey number $IR(H,G)$ be the smallest number of vertices in a graph $F$ such that $F \rightarrow (H,G)$. Deuber showed in 1975 that $IR(H,G)$ is well-defined for any graphs $H$ and $G$. Still, the determination of $IR(H,G)$ remains a challenge for most graphs. A striking contrast between induced and non-induced Ramsey numbers was demonstrated by Fox and Sudakov in 2008 by showing that $IR(H,G)$ is superlinear in $n$ when $H$ is a matching on $n$ edges and $G$ is a star on $n$ edges.

In this talk, I will address the case when $G= K_{1,n}$, a star on $n$ edges, for large $n$, and $H$ is a fixed graph. We prove that $$ (\chi(H)-1) n \leq IR(H, K_{1,n}) \leq (\chi(H)-1)^2n + \epsilon n,$$ for any $\epsilon>0$, sufficiently large $n$, and $\chi(H)$ denoting the chromatic number of $H$. The lower bound is asymptotically tight for any fixed bipartite $H$. The upper bound is attained up to a constant factor, for example when $H$ is a clique.

This is a joint work with Izolda Gorgol.

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.

Pages