Seminars and Colloquia by Series

Half-integral Erdős-Pósa property for non-null S–T paths (Meike Hatzel)

Series
Graph Theory Seminar
Time
Tuesday, October 22, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Meike HatzelInstitute for Basic Science (IBS)

For a group Γ, a Γ-labelled graph is an undirected graph G where every orientation of an edge is assigned an element of Γ so that opposite orientations of the same edge are assigned inverse elements. A path in G is non-null if the product of the labels along the path is not the neutral element of Γ. We prove that for every finite group Γ, non-null S–T paths in Γ-labelled graphs exhibit the half- integral Erdős-Pósa property. More precisely, there is a function f , depending on Γ, such that for every Γ-labelled graph G, subsets of vertices S and T , and integer k, one of the following objects exists:
• a family F consisting of k non-null S–T paths in G such that every vertex of G participates in at most two paths of F; or
• a set X consisting of at most f (k) vertices that meets every non-null S–T path in G.
This in particular proves that in undirected graphs S–T paths of odd length have the half-integral Erdős-Pósa property.
This is joint work with Vera Chekan, Colin Geniet, Marek Sokołowski, Michał T. Seweryn, Michał Pilipczuk, and Marcin Witkowski.

Non-measurable colourings avoiding large distances (James Davies)

Series
Graph Theory Seminar
Time
Tuesday, October 8, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
James DaviesCambridge University

 In 1983, Furstenberg, Katznelson, and Weiss proved that for every finite measurable colouring of the plane, there exists a $d_0$ such that for every $d\geq d_0$ there is a monochromatic pair of points at distance $d$. In contrast to this, we show that there is a finite colouring avoiding arbitrarily large distances. Joint work with Rutger Campbell.

CANCELLED - Tight minimum colored degree condition for rainbow connectivity

Series
Graph Theory Seminar
Time
Friday, October 4, 2024 - 15:15 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xiaofan YuanArizona State University

Let $G = (V,E)$ be a graph on $n$ vertices, and let $c : E \to P$, where $P$ is a set of colors. Let $\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}$ where $d^c(v)$ is the number of colors on edges incident to a vertex $v$ of $G$.  In 2011, Fujita and Magnant showed that if $G$ is a graph on $n$ vertices that satisfies $\delta^c(G)\geq n/2$, then for every two vertices $u, v$ there is a properly-colored $u,v$-path in $G$.
In this paper, we show that the same bound for $\delta^c(G)$ implies that any two vertices are connected by a rainbow path. This is joint work with Andrzej Czygrinow.


This is to note that the graph theory seminar for Friday the 4th has been CANCELLED. This is due to the cancellation of the AMS sectional meeting due to Hurricane Helene. I apologize for any inconvenience. We intend to reschedule the talk for next semester.

Proof of the Goldberg-Seymour conjecture (Guantao Chen)

Series
Graph Theory Seminar
Time
Tuesday, October 1, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Guantao ChenGeorgia State University

The Goldberg-Seymour Conjecture asserts that if the chromatic index $\chi'(G)$ of a loopless multigraph $G$ exceeds its maximum degree $\Delta(G) +1$, then it must be equal to another well known lower bound $\Gamma(G)$, defined as

$\Gamma(G) = \max\left\{\biggl\lceil  \frac{ 2|E(H)|}{(|V (H)|-1)}\biggr\rceil \ : \  H \subseteq G \mbox{ and } |V(H)| \mbox{ odd }\right\}.$

 

In this talk, we will outline a short proof,  obtained recently with  Hao, Yu, and Zang. 

Degree-boundedness (Xiying Du)

Series
Graph Theory Seminar
Time
Tuesday, September 24, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xiying DuGeorgia Tech

We say a class of graphs $\mathcal{F}$ is degree-bounded if there exists a function $f$ such that $\delta(G)\le f(\tau(G))$ for every $G\in\mathcal{F}$, where $\delta(G)$ denotes the minimum degree of $G$ and $\tau(G)$ is the biclique number of $G$, that is, the largest integer $t$ such that $G$ contains $K_{t,t}$ as a subgraph. Such a function $f$ is called a degree-bounding function for $\mathcal{F}$.

In joint work with Ant\'onio Gir\~ao, Zach Hunter, Rose McCarty and Alex Scott, we proved that every hereditary degree-bounded class $\mathcal{F}$ has a degree-bounding function that is singly exponential in the biclique number $\tau$. A more recent result by Ant\'onio Gir\~ao and Zach Hunter improved this bound to a polynomial function in $\tau$. In this talk, I will discuss examples and the recent results on degree-boundedness. 

 On orientations of graphs with forbidden out-degrees (Owen Henderschedt, Auburn)

Series
Graph Theory Seminar
Time
Tuesday, September 17, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Owen HenderschedtAuburn University

 When does a graph admit an orientation with some desired properties? This question has been studied extensively for many years and across many different properties. Specifically, I will talk about properties having to do with degree restrictions, and progress towards a conjecture of Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati dealing with a list-type of degree restriction. This is all joint work with my PhD advisor Jessica McDonald.

The logic of graphs (Rose McCarty)

Series
Graph Theory Seminar
Time
Tuesday, August 27, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCartyGeorgia Tech

We give an overview of the interplay between structural graph theory, first-order logic, and parameterized complexity. We focus on introducing the subject. Time permitting, one particular topic will be the neighborhood complexity of monadically stable graph classes. 

Induction for 4-connected Matroids and Graphs (Xiangqian Joseph Zhou, Wright State University)

Series
Graph Theory Seminar
Time
Tuesday, July 23, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Xiangqian Joseph ZhouWright State University

A matroid $M$ is a pair $(E, \mathcal{I})$ where $E$ is a finite set, called the {\em ground set} of $M$, and $\mathcal{I}$ is a non-empty collection of subsets of $E$, called {\em independent sets} of $M$, such that (1) a subset of an independent set is independent; and (2) if $I$ and $J$ are independent sets with $|I| < |J|$, then exists $x \in J \backslash I$ such that $I \cup \{x\}$ is independent. 

A graph $G$ gives rise to a matroid $M(G)$ where the ground set is $E(G)$ and a subset of $E(G)$ is independent if it spans a forest. Another example is a matroid that comes from a matrix over a field $F$: the ground set $E$ is the set of all columns and a subset of $E$ is independent if it is linearly independent over $F$. 

Tutte's Wheel and Whirl Theorem and Seymour's Splitter Theorem are two well-known inductive tools for proving results for 3-connected graphs and matroids. In this talk, we will give a survey on induction theorems for various versions of 4-connected matroids and graphs.   
 

Conflict-free hypergraph matchings and generalized Ramsey numbers (Emily Heath, Iowa State University)

Series
Graph Theory Seminar
Time
Tuesday, April 16, 2024 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Emily HeathIowa State University

Given graphs G and H and a positive integer q, an (H,q)-coloring of G is an edge-coloring in which each copy of H receives at least q colors. Erdős and Shelah raised the question of determining the minimum number of colors, f(G,H,q), which are required for an (H,q)-coloring of G. Determining f(K_n,K_p,2) for all n and p is equivalent to determining the classical multicolor Ramsey numbers. Recently, Mubayi and Joos introduced the use of a new method for proving upper bounds on these generalized Ramsey numbers; by finding a “conflict-free" matching in an appropriate auxiliary hypergraph, they determined the values of f(K_{n,n},C_4,3) and f(K_n,K_4,5). In this talk, we will show how to generalize their approach to give bounds on the generalized Ramsey numbers for several families of graphs. This is joint work with Deepak Bal, Patrick Bennett, and Shira Zerbib.

Pages