The Lovász conjecture holds for moderately dense Cayley graphs

This paper proves that every large connected Cayley graph with degree at least $n^{1-c}$ for some absolute constant $c>0$ contains a Hamilton cycle, thereby advancing the Lovász conjecture by improving previous density thresholds through a proof that utilizes an arithmetic regularity lemma tailored to Cayley graphs instead of Szemerédi's regularity lemma.

The Gist

Imagine you have a massive, intricate maze. The goal is to find a single path that visits every single room in the maze exactly once and then returns to the start. In the world of mathematics, this is called a Hamiltonian cycle.

For decades, mathematicians have wondered: If a maze is built with perfect symmetry (where every room looks and feels the same from the inside), is it guaranteed that such a path exists? This is the famous Lovász Conjecture.

While we know this is true for very dense mazes (where every room is connected to almost every other room), it has been a mystery for "sparser" mazes—those where rooms have fewer connections. This paper, by Bedert, Draganić, Muyesser, and Pavez-Signe, solves the mystery for a huge new class of these sparse mazes.

Here is the story of how they did it, explained without the heavy math jargon.

1. The Problem: The "Sparse Maze" Dilemma

Think of a Cayley Graph as a maze built by a group of people (a mathematical "Group") following a specific set of rules (a "Generating Set").

• The Rooms: The people.
• The Doors: The rules that let you move from one person to another.

If the group is large and the rules are symmetric, the maze looks the same from every room. The conjecture says: No matter how you build this symmetric maze, as long as it's connected, you can always walk through every room once and come back home.

For a long time, this was only proven for "dense" mazes (where people have hundreds of doors). If the mazes were "sparse" (people only have a few doors), the old tools used to prove it didn't work. It was like trying to use a sledgehammer to fix a watch; the tools were too blunt.

2. The Old Tools vs. The New Tool

Previous attempts to solve this relied on a famous mathematical tool called the Regularity Lemma.

• The Analogy: Imagine trying to understand a city by dividing it into giant, blurry blocks. You ignore the small details and just look at the "average" traffic in each block.
• The Problem: This works great for big, crowded cities (dense graphs). But for a small village or a sparse network, this "blurry block" approach loses all the important details. It also requires so much computing power that it's practically useless for real-world efficiency.

The Breakthrough: The authors didn't use the sledgehammer. Instead, they used a specialized, high-precision laser called the Weak Arithmetic Regularity Lemma.

• The Analogy: Instead of looking at blurry blocks, they looked at the specific "neighborhoods" within the group structure. They realized that even in a sparse maze, you can always find a smaller, hidden sub-maze that is incredibly well-connected and has no "dead ends" or "bottlenecks."

3. The Strategy: The "Absorber" Method

To prove you can walk through the whole maze, the authors used a clever strategy called the Absorption Method. Think of it like packing a suitcase for a trip where you don't know exactly what you'll need until the last minute.

Here is their 4-step plan:

Step 1: Build a "Magic Trap" (The Absorber)

Before they start walking, they build a special gadget called an Absorber.

• The Metaphor: Imagine a special room in the maze that has a secret door. If you walk through the room normally, you just pass through. But if you have a "stray" person left over at the end of your trip, you can use the secret door to pull them into your path without breaking the flow.
• The Innovation: They built many of these magic traps scattered throughout the maze using random patterns. Because the maze is symmetric, these traps work everywhere.

Step 2: The "Sweep"

Next, they ignore the magic traps for a moment and try to walk through almost the entire maze, leaving only a few people behind.

• The Metaphor: It's like sweeping a floor. You get 99% of the dust (people) into a pile, but you leave a few specks behind.
• The Challenge: In sparse mazes, it's hard to sweep efficiently without getting stuck. The authors used a new technique to ensure they could sweep through the "well-connected" sub-mazes they found earlier, leaving very few people behind.

Step 3: The "Link-Up"

Now they have a long path covering most of the maze, plus a few scattered people and their magic traps.

• The Metaphor: They use the "magic traps" to stitch the long path together. They connect the ends of their swept path to the traps.
• The Trick: Because the traps are designed to be flexible, they can link the path segments together in a specific order that creates a giant, almost-complete loop.

Step 4: The "Grand Finale" (Absorption)

Finally, they deal with the few people left behind (the "stray" people from Step 2).

• The Metaphor: They walk into the magic traps. Because of the trap's design, they can "absorb" the stray people into the loop. The path expands to include them, and suddenly, the loop is perfect. Every single person in the maze has been visited exactly once.

4. Why This Matters

• It's a Big Deal: They proved that for any large, symmetric maze where the number of doors per room is at least roughly the square root of the total number of rooms (a "moderately dense" graph), a perfect path always exists.
• Better Tools: They showed that you don't need the heavy, clumsy "Regularity Lemma" to solve these problems. Their new "laser" approach is more efficient and works for much sparser structures.
• Future Doors: While they didn't solve the conjecture for every possible sparse maze (the very thinnest ones), they broke the biggest barrier. They proved that symmetry is powerful enough to force a solution in a much wider range of scenarios than we thought.

Summary

The authors took a 60-year-old puzzle about symmetric mazes. They realized that even in sparse mazes, there are hidden, well-connected neighborhoods. By building "magic traps" (absorbers) and using a new, precise way to map these neighborhoods, they proved that you can always find a path that visits every room exactly once. They didn't just solve a math problem; they built a better map for exploring the hidden structures of symmetry.

Technical Summary

Here is a detailed technical summary of the paper "The Lovász conjecture holds for moderately dense Cayley graphs" by Benjamin Bedert, Nemanja Draganić, Alp Müyesser, and Matías Pavez-Signé.

1. Problem Statement

The paper addresses the Lovász Conjecture (1969), which posits that every connected vertex-transitive graph contains a Hamilton cycle. A specific and older version of this problem, proposed by Rappaport-Strasser (1959), focuses on Cayley graphs.

• Conjecture: Every connected Cayley graph on a finite group with at least 3 elements is Hamiltonian.
• Current State: While verified for abelian groups and specific families (like $p$-groups), the conjecture remains wide open for arbitrary groups.
• Density Barrier: Previous results established the conjecture for dense Cayley graphs (degree $d \ge \varepsilon n$) using Szemerédi's Regularity Lemma. However, this lemma is ineffective for sparse graphs (degree $o(n^2)$) and introduces tower-type dependencies that hinder efficiency. The challenge was to prove Hamiltonicity for graphs with degree $d = n^{1-c}$ (polynomially sparse) without relying on the Regularity Lemma.

2. Main Result

The authors prove the Lovász conjecture for moderately dense (polynomially sparse) Cayley graphs.

Theorem 1.2: There exists a constant $c \ge 1/200$ such that for all sufficiently large $n$, every connected $n$-vertex Cayley graph with degree $d > n^{1-c}$ contains a Hamilton cycle.

3. Methodology and Key Techniques

The proof avoids Szemerédi's Regularity Lemma, which is standard for dense graphs but fails for sparse ones. Instead, the authors employ a combination of spectral expansion, a weak arithmetic regularity lemma, and an efficient absorption method tailored for sparse structures.

A. Weak Arithmetic Regularity Lemma (The Structural Decomposition)

The core structural tool is Theorem 2.2 (from Bedert et al., 2019), a weak arithmetic regularity lemma for Cayley graphs.

• Mechanism: For a Cayley graph $\text{Cay}_G(S)$ with density $\sigma$, the lemma guarantees the existence of a subgroup $H \le G$ such that:
  1. $S$ has significant intersection with $H$ ($|S \cap H| \ge (1-\varepsilon)|S|$).
  2. The induced subgraph $\text{Cay}_H(S \cap H)$ has no sparse cuts (it is a robust expander).
• Implication: The original graph $\text{Cay}_G(S)$ can be viewed as a collection of cosets of $H$, where the internal structure of each coset is highly connected (no sparse cuts), and the connections between cosets form an auxiliary graph.

B. Reduction to a Spanning Path Forest

The problem is reduced from finding a single Hamilton cycle in the whole graph to finding a specific structure within the subgroup cosets:

1. Auxiliary Graph: The cosets of $H$ form a graph $\text{Aux}_{G/H}(S)$. The authors show this auxiliary graph contains a "tree skeleton" (a spanning tree with specific connectivity properties).
2. Reduction: If the auxiliary graph is connected, the problem reduces to finding a spanning linear forest (a collection of disjoint paths) in the subgroup $\text{Cay}_H(S \cap H)$ with specific endpoints, which can then be stitched together.
3. Target Theorem (Theorem 2.4): Prove that in a graph with "no sparse cuts," one can find a spanning linear forest with $O(\log n)$ components and fixed endpoints.

C. The Absorption Method in Sparse Graphs

To construct the spanning linear forest, the authors adapt the absorption method (typically used for dense graphs) to the sparse setting. This involves four steps:

1. Absorber Construction: Construct a "random-like" absorbing structure. By taking random translates of a small gadget (an odd cycle with specific paths), they create a set of absorbers that can absorb any small set of leftover vertices.
   • Innovation: They use the translation invariance of Cayley graphs to ensure these random translates behave like a random subset, maintaining degree regularity.
2. Path Forest Partition: Partition the remaining vertices (excluding the absorbers) into a linear forest with few paths.
   • Tool: They utilize results related to the Magnant–Martin conjecture, adapted for "almost-regular" graphs (graphs where degrees deviate slightly from the mean).
3. Linking: Connect the path forest and the absorbers.
   • Mechanism: They use the robust expansion property (guaranteed by the "no sparse cuts" condition) to link endpoints via short paths that avoid previously used vertices.
4. Absorption: Use the absorbers to incorporate the remaining vertices into the paths, completing the Hamilton cycle (or the required spanning forest).

D. Robust Expansion

A critical technical component is establishing that "no sparse cuts" implies robust expansion.

• Definition: A graph is a robust $(\nu, \tau)$-expander if every set $U$ of intermediate size has a large "robust neighborhood" (vertices connected to many elements of $U$).
• Application: This property ensures that even after removing a small set of vertices (used for linking), the graph remains highly connected, allowing the construction of paths between arbitrary endpoints.

4. Key Contributions

1. Breaking the Density Barrier: The paper confirms the Lovász conjecture for graphs with degree $d = n^{1-c}$, significantly improving upon the previous best result of $d \ge \varepsilon n$ (Christofides, Hladký, Máté, 2014).
2. Avoiding Regularity Lemma: The proof successfully bypasses Szemerédi's Regularity Lemma, which was previously thought necessary for such structural decompositions. This eliminates tower-type dependencies and makes the result applicable to sparse graphs.
3. Efficient Arithmetic Regularity: The authors leverage a specialized, quantitative weak arithmetic regularity lemma that provides better structural decomposition for Cayley graphs than general graph regularity lemmas.
4. Adaptation of Absorption: They develop a novel implementation of the absorption method that works in sparse, non-random-like graphs by exploiting the group structure (translation invariance) to create "random-like" absorbers.

5. Significance and Future Directions

• Theoretical Impact: This is a major step toward resolving the Lovász conjecture for all Cayley graphs. It demonstrates that high symmetry (Cayley structure) combined with moderate density is sufficient to force Hamiltonicity.
• Methodological Shift: The shift from Regularity Lemma to Arithmetic Regularity and Spectral Expansion opens new avenues for solving problems in sparse Cayley graphs and other algebraic structures.
• Limitations: The current methods rely on the weak arithmetic regularity lemma, which ceases to provide useful information when the degree drops below $\sqrt{n}$.
• Future Work: The authors conjecture that the result holds for degrees $d = n^{o(1)}$ (polylogarithmic degree) and propose a generalization involving random subgraphs of Cayley graphs (Conjecture 1.3), linking the Lovász conjecture to the Hamiltonicity of random graphs $G(n,p)$.

In summary, this paper resolves a long-standing open problem for a significant class of sparse graphs by combining algebraic structure, spectral graph theory, and refined combinatorial techniques, marking a substantial advancement in the field of extremal graph theory.