OctoInformBeta

The Erdős–Gallai cycle-decomposition conjecture

All graphs are finite, simple and undirected. A cycle is simple and has length at least three. A cycle-and-edge partition of a graph GG is a partition of its edge set E(G)E(G) into parts, each of which is the edge set of a cycle of GG or a single edge of GG. The decomposition cost of GG is the least number of parts in a cycle-and-edge partition of GG. A tree on nn vertices has decomposition cost n−1n-1. The Erdős-Gallai cycle decomposition conjecture asserts that there is an absolute constant C>0C>0 such that every graph on nn vertices has decomposition cost at most CnCn.

The conjecture appears in the 1966 paper of Erdős, Goodman and Pósa. That paper records the upper bound O(nlog⁡n)O(n\log n) on the decomposition cost of a graph on nn vertices. In 2014 Conlon, Fox and Sudakov improved this bound to O(nlog⁡log⁡n)O(n\log\log n). Write log⁡*n\log^* n for the number of iterations of the logarithm needed to bring nn to at most 11. Bucić and Montgomery then proved the bound O(nlog⁡*n)O(n\log^* n). There are complete bipartite graphs on nn vertices with decomposition cost at least (3/2−o(1))n(3/2-o(1))n. Conlon, Fox and Sudakov proved a linear bound, with high probability, for binomial random graphs. For fixed α,δ>0\alpha,\delta>0, Girão, Granet, Kühn and Osthus proved that every sufficiently large graph on nn vertices with minimum degree at least αn\alpha n has decomposition cost at most (3/2+δ)n(3/2+\delta)n. Akbari, Aloni, Beikmohammadi and Clow proved the bound n−1n-1 for graphs on n≥1n\ge 1 vertices of maximum degree at most four. When the cycles and edges may overlap, Pyber proved that n−1n-1 of them suffice to cover the edges of every graph on n≥1n\ge 1 vertices.

The preprint proves the Erdős-Gallai cycle decomposition conjecture, as its Theorem 1.1. The preprint derives from it that every graph on nn vertices whose degrees are all even has an edge partition into at most CnCn cycles, with CC the constant of Theorem 1.1, a consequence that the Lean library does not contain.

The Lean library CycleDecomposition proves Theorem 1.1. The Lean library takes no result as a hypothesis. Lean has checked every result of the Lean library, and the Lean library is therefore the reference. Each result on these pages is stated as the Lean library states it and is linked to the Lean declaration behind it. Where the preprint states a result differently, the preprint’s statement is given beside the Lean library’s. The preprint is a guide only: it gives the results their order and their names.

The Lean library: CycleDecomposition

CycleDecomposition is a Lean library: 22 items, in eight groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. Cycle-and-edge partitions Cycle-and-edge partitions and the decomposition cost of a graph. §1
  2. Theorem 1.1 Every graph splits into linearly many cycles and single edges. §1
§2. Conventions and preliminary results 5 items
  1. Cut expansion Cut expansion of a graph and within a vertex set. §2
  2. Pieces carrying assigned edges, and graph partitions Pieces on vertex sets and edge partitions of a graph. §2
  3. Theorem 2.1 The edges of any graph split into few paths and cycles. §2
  4. Corollary 2.2 Every graph splits into paths with endpoint load two. §2
  5. Lemma 2.4 Chernoff bounds below half and above twice the mean. §2
§3. Routing with team constraints 1 item
  1. Lemma 3.1 Short edge-disjoint routing in an expander under team constraints. §3
§4. Expansion in small reservoirs 3 items
  1. Lemma 4.1 Splitting a strong expander into a fixed number of expanders. §4
  2. Lemma 4.2 Random vertex samples of large expanders are likely expanders. §4
  3. Lemma 4.3 Cycles and single edges up to a small residue. §4
§5. Splitting at a scale 2 items
  1. Lemma 5.1 Splitting a graph into long cycles, expanders and sparser residuals. §5
  2. Lemma 5.2 Vertex expansion forces a long cycle and a long path. §5
§6. Pair folding and resolving batches 2 items
  1. Lemma 6.1 Folding vertex pairs in low-degree sets costs few edges. §6
  2. Lemma 6.2 Folding paired vertices and resolving the batches. §6
§7. The induction 3 items
  1. Lemma 7.1 Some positive term controls the prefix sum reaching past it. §7
  2. The potential φ, the scales and the layers The potential, the scales and the layers of the induction. §7
  3. Proposition 7.2 A linear bound on the decomposition cost of graphs. §7
Steps of the proof with no numbered result 4 items
  1. Reservoir preparation and the reservoir remainder Three expanding colour classes with reservoirs, and what remains. §4
  2. Lifting a cycle of the quotient When a cycle of a quotient graph lifts to GG.
  3. Grouping graphs into batches A graph split into small pieces splits into few batches.
  4. The layers of the induction and their costs Layers of a piece and bounds on its decomposition cost. §7

No item matches.