Results on path and cycle decompositions, disjoint representatives, routing, expanding pieces, folding and the linear bound, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Parity of end counts — Lemma 1.1. In a decomposition into paths and cycles, the number of paths ending at a vertex has the parity of its degree; every odd vertex is an end of a path. No hypothesis.
• Lovász's decomposition theorem — Theorem 2.1. Every graph decomposes into at most floor(sigma/2) paths and cycles, sigma the number of vertices of positive degree; so a graph with n vertices needs at most floor(n/2). No hypothesis.
• Paths with at most two ends at each vertex — Corollary 3.1. Every graph with n vertices decomposes into at most n paths, every vertex being an end of at most two of them. No hypothesis.
• Even graphs decompose into cycles — Lemma 4.1. A graph whose degrees are all even has a decomposition into cycles. No hypothesis.
• Haxell's condition — Theorem 1.1. If, for every nonempty set I of indices, the union of the hypergraphs indexed by I (edges of size at most s) has a matching with more than (2s-1)(|I|-1) edges, then the family has pairwise disjoint representatives. No hypothesis.
• Basic facts on cut expansion — Lemma 1.2. A graph of order r >= 2 with cut expansion h > 0 has minimum degree at least h, satisfies h < r, and is connected.
• Routing theorem — Theorem 2.1. If h >= 128(l^2(k+b)+z), demands with at most k ends at a vertex, teams of at most b demands and forbidden sets of at most z vertices are served by edge-disjoint paths of length at most l, with disjoint inner vertices within each team.
• Length of the routing paths — Corollary 2.2. The length bound of the routing theorem satisfies l <= 108 (r/h) (log r)^2.
• Vertex expansion gives a long cycle — Lemma 1.1. For large u: if every vertex set U with 0 < |U| <= u/2 has at least alpha |U| external neighbours, alpha = 1/(32 log^2 u), then the graph has a cycle longer than alpha^2 u/100.
• Splitting at a scale — Lemma 2.1. For large D, a graph of order N and average degree at most D splits into at most N/(2D^0.01) cycles of length at least D^1.01 and overlapping boxes of order at most D^1.02 and total order at most (1 + 2/log D)N; each box splits into pieces of cut expansion D^0.90 and a residual of average degree at most D^0.95.
• Chernoff bounds — Lemma 1.2. A binomial variable with mean mu is at most mu/2 with probability at most e^(-mu/8), and at least 2 mu with probability at most e^(-mu/3). No hypothesis.
• Edge splitting — Lemma 2.1. For large D, a graph of order between D^0.90 and D^1.02 with cut expansion h_0 >= c D^0.90 splits into l spanning subgraphs of cut expansion at least h_0/(2l).
• Vertex sampling — Lemma 3.1. In such a graph with cut expansion c' D^0.90, a p-random vertex set has at most 2pr vertices, gives every vertex at least ph/2 sampled neighbours and induces cut expansion at least D^0.74, with probability 1 - o(1).
• Small residue — Lemma 1.1. For large D, a graph of order r between D^0.90 and D^1.02 with a spanning subgraph of cut expansion c D^0.90 decomposes into at most 9r cycles and edges and at most three residual graphs on disjoint vertex sets of total order at most eta r.
• Pair folding — Lemma 1.1. If the folding sets have at least max(8, a^2) vertices of degree at most a and every vertex has at most a neighbours in each, pairings exist such that, after deleting at most 2 sum m_i edges, the quotient is simple with unique representatives.
• Batch resolution — Lemma 2.1. Batches with active sets in expanding routers have quotients of order |W| - sum floor(|X|/2); any cycle-and-edge partitions of the quotients lift to the batch edges and some router edges at an extra cost of 8 times the total active order.
• Choice of a prefix — Lemma 1.1. A nonnegative, finitely supported, nonzero sequence has a positive term S_i such that the sum of S_j over j <= i + K is at most 4(K+1) S_i. No hypothesis.
• The Erdős–Gallai cycle decomposition theorem (OpenAI) — Theorem 7.1. The edges of every graph with n vertices can be partitioned into at most Cn cycles and single edges, for an absolute constant C. No hypothesis.
• Eulerian graphs (second part under GGKO) — Corollary 7.2. Every Eulerian graph with n vertices decomposes into at most Cn cycles; under the named statement (GGKO), into at most Delta/2 + delta n cycles when all large cuts are dense.

Reading order

Read the first three lessons first: Lovász's theorem and the routing theorem are used throughout. The fourth to seventh lessons prove the tools of the induction, which is carried out in the last lesson.