Arts & Sciences Events
[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Alexandr Kostochka (UIUC)
Access & Features
- Open to the public
Speaker: Alexandr Kostochka (University of Illinois at Urbana-Champaign)
Title: On disjoint and longest cycles in graphs
Abstract: The aim of the talk is to present some recent refinements of results on cycle structure of graphs from the sixties.
Let $V_{\geq t}(G)$ (respectively, $V_{\leq t}(G)$) denote the set of vertices in $G$ with degree at least (respectively, at most) $t$. Dirac and Erd\H os in 1963 extended the Corr\'{a}di-Hajnal Theorem as follows: If $k\geq 3$ and $G$ is a graph with $|V_{\geq 2k}(G)| - |V_{\leq 2k-2}(G)| \geq k^{2} + 2k - 4$, then $G$ has $k$ disjoint cycles. They also showed a series of examples of graphs $G$ with $|V_{\geq 2k}(G)| - |V_{\leq 2k-2}(G)|=2k-1$ that do not have $k$ disjoint cycles.
We show that each graph $G$ with $|V_{\geq 2k}(G)| - |V_{\leq 2k-2}(G)| \geq 3k$ has $k$ disjoint cycles. This is sharp if we do not impose restrictions on $|V(G)|$. We also show that if $|V(G)|\geq 19k$, then the result holds with $2k$ instead of $3k$. This is joint work with Kierstead and McConvey.
The theorems of Erd\H{o}s and Gallai from 1959 on the most edges in $n$-vertex graphs that do not have paths/cycles with at least $k$ vertices were sharpened later by Faudree and Schelp, Woodall, and Kopylov. Let $h(n,k,a) = {k-a \choose 2} + a(n -k+ a)$. The strongest result (by Kopylov) was: if $t\geq 2$, $k\in \{2t+1,2t+2\}$, $n \geq k$, and $G$ is an $n$-vertex $2$-connected graph with at least $\max\{h(n,k,2),h(n,k,t)\} $ edges, then $G$ contains a cycle of length at least $k$, unless $G = H_{n,k,t} := K_n - E(K_{n - t})$. We prove stability versions of these results. In particular, if $k\geq 3$ is odd, $n \geq k$ and the number of edges in an $n$-vertex $2$-connected graph $G$ with no cycle of length at least $k$ is greater than $\max\{h(n,k,3),h(n,k,t-1)\}$, then $G$ is a subgraph of $H_{n,k,t}$ or of $H_{n,k,2}$. This is joint work with F\" uredi, Luo and Verstra\" ete.
Contact
Gexin Yu