Extremal Problems for Paths and Cycles in Graphs and Their Analogues Open Access

Abstract

We study several analogues of two classical questions in extremal graph theory:

(1) What lengths of paths (or cycles) can we guarantee in a given graph?

(2) What is the smallest number of paths (or cycles) needed in order to decompose the entire edge set of a given graph?

First, in the colored graph setting, we prove in the spirit of (1) that any properly edge-colored d-regular graph has a rainbow path of length d - o(d). Moreover, if d is on the order of the number of vertices, then we can find a rainbow cycle of the same length. We also consider this problem for directed graphs. We use these results to asymptotically resolve a conjecture of Graham from 1971 which says that for any prime p, any d distinct nonzero residues mod p can be ordered so that all d partial sums are distinct.

Second, we consider a GF(2)-variant of what it means to "decompose" the edge set of a graph in (2): we show that any Eulerian graph of maximum degree Δ is the symmetric difference of at most ceil(3Δ/4) paths (same for cycles), improving a previous best-known bound of Δ. 

Lastly, we consider both questions in the setting of binary matroids and vector spaces. In the spirit of (1), we prove that the maximum number of elements in a rank-n binary matroid with no circuit of length 2k is Θ(2^(n/k)). In the spirit of (2), we prove that any rank-n binary matroid can be decomposed into O(2^n/n) circuits. We use a supersaturation version of this former result to give improvements on off-diagonal vector space Ramsey numbers over GF(2). Specifically, we show that any red/blue coloring of the points of the projective space PG(n-1,2) must have either a red line or blue t-space whenever n = Ω(t1.57^t). Previously this was known only for n = Ω(t2^t).

Table of Contents

Introduction Notation and preliminaries Rainbow paths and cycles Path and cycle odd-covers Circuit decompositions in binary matroids Vector space Ramsey numbers Future work

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics
Keyword	Ramsey theory extremal combinatorics paths and cycles graph theory graph decompositions binary matroids
Committee Chair / Thesis Advisor	Yepremyan, Liana, Emory University
Committee Members	Pohoata, Cosmin, Emory University Rödl, Vojtěch, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Extremal Problems for Paths and Cycles in Graphs and Their Analogues ()	2026-04-01 16:42:51 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions