Independence complexes of generalized Mycielskian graphs

This paper establishes that the homotopy type of the independence complex of a generalized Mycielskian graph is determined by the homotopy types of the independence complexes of the original graph and its Kronecker double cover, and applies this result to compute these types for paths, cycles, and categorical products of complete graphs.

The Gist

Imagine you have a giant, complex Lego structure (a graph) made of blocks (vertices) connected by sticks (edges). In the world of math, there's a special rule: you can only build a "safe tower" if no two blocks in your tower are touching each other directly. This collection of all possible "safe towers" is called the Independence Complex.

Mathematicians love to ask: "What does this collection of safe towers look like if we squish, stretch, or bend it?" This is called its homotopy type. Is it a ball? A donut? A bunch of balloons tied together?

This paper is about a specific, tricky way of building new Lego structures called Mycielskians. Think of a Mycielskian as a "magic photocopier" that takes your original graph and creates a much larger, more complicated version of it, layer by layer. The author, Andrés Carnero Bravo, wants to know: If we know what the "safe tower collection" of the original graph looks like, can we predict what the "safe tower collection" of this new, giant version looks like?

Here is the breakdown of his discovery using simple analogies:

1. The Two Ingredients

To predict the shape of the new structure, you don't need to build the whole thing. You only need two pieces of information about the original graph:

• Ingredient A: The shape of the safe towers of the original graph itself.
• Ingredient B: The shape of the safe towers of a "double version" of the graph. Imagine taking your graph and making a perfect twin copy, then connecting every block in the original to its twin. This is called the Kronecker double cover.

2. The Magic Recipe (The Main Discovery)

The author found a universal recipe. When you apply the "Mycielskian magic" to a graph, the resulting shape is always a wedge of spaces.

• The "Wedge": Imagine taking several balloons (spheres) and tying them all together at a single point. That's a wedge.
• The Recipe: The final shape is made by taking your two ingredients (Ingredient A and Ingredient B), stretching them out (like inflating a balloon), and tying them together in specific patterns.

The pattern depends on how many layers you added (the number $l$):

• If you added 3 layers (or a multiple of 3): You get a mix of the original shape and the double shape, tied together.
• If you added 1 extra layer: You get the original shape, but stretched out (suspended) and tied to the double shape.
• If you added 2 extra layers: You get a giant version of just the double shape.

3. Real-World Examples

The author tested this recipe on common shapes to see if it worked:

• Paths and Cycles: Like a straight line of blocks or a ring of blocks. The paper shows that even for these, the complex shapes turn out to be just collections of spheres (balloons) of different sizes.
• Complete Graphs: Imagine a party where everyone knows everyone else. The "safe towers" here are very small (you can only pick one person). The paper shows that when you apply the Mycielskian magic to these, you get a massive bouquet of spheres.
• Trees and Forests: If your graph has no loops (like a family tree), the result is either a single point (contractible) or a bouquet of spheres.

4. The "Iterated" Twist

The paper also looks at what happens if you use the magic machine twice or three times in a row.

• The Pattern: It turns out there is a mathematical rhythm. If you keep applying the magic, the number of "balloons" and how "stretched" they are follows a predictable formula (like a musical scale).
• The Exception: If you stop exactly at a multiple of 3 layers, the formula gets a little messy (it's a sum of many different combinations), but the author proves that even then, the shape is still just a collection of stretched and tied-together versions of the original ingredients.

Why Does This Matter?

In the world of topology (the study of shapes), these graphs are famous because they can be used to create structures that are very hard to color (chromatic number) but have no small triangles. Understanding their "shape" (homotopy type) helps mathematicians understand the deep connections between how things are connected and how they can be colored or arranged.

In a nutshell:
This paper is like finding the instruction manual for a shape-shifting machine. Instead of having to build the giant, complicated machine every time to see what it looks like, the author says, "Just look at the original machine and its twin, and I can tell you exactly what the giant version will look like: it's just a bunch of balloons tied together in a specific, predictable pattern."

Technical Summary

Here is a detailed technical summary of the paper "Independence complexes of generalized Mycielskian graphs" by Andrés Carnero Bravo.

1. Problem Statement

The paper investigates the homotopy type of the independence complex ($I(G)$) associated with generalized Mycielskian graphs.

• Context: The independence complex of a graph $G$ is a simplicial complex where simplices correspond to independent sets of vertices. Understanding its topological structure (specifically its homotopy type) is a central problem in algebraic combinatorics and topological graph theory.
• The Construction: The Mycielskian construction ($\mu(G)$) is a classic method for generating triangle-free graphs with arbitrarily high chromatic numbers. The paper focuses on the $l$-Mycielskian ($\mu_l(G)$), a generalization involving a path of length $l+1$, and the $r$-iterated versions ($\mu_l^r(G)$).
• Gap: While previous work (e.g., [13]) established results for the standard Mycielskian ($l=1$) and complete graphs, a general formula for the homotopy type of $\mu_l(G)$ for arbitrary $l$ and $G$ was lacking. Furthermore, the behavior of iterated constructions was not fully characterized.

2. Methodology

The author employs tools from combinatorial topology and homotopy theory to decompose complex independence complexes into simpler components.

• Key Definitions:
  • Independence Complex $I(G)$: The simplicial complex of independent sets.
  • Kronecker Double Cover ($G \times P_2$): The categorical product of $G$ and the path $P_2$. This is central to the main theorem.
  • Join ($*$) and Suspension ($\Sigma$): Standard topological operations used to describe the resulting spaces.
• Core Techniques:
  • Vertex Deletion and Neighborhood Inclusion: The proof relies heavily on Lemma 2 (if $N(u) \subseteq N(v)$, then $I(G) \simeq I(G-v)$) and Proposition 3 (a generalization involving null-homotopic inclusions). These allow the author to systematically remove vertices from the graph to simplify the complex while preserving homotopy type.
  • Case Analysis based on Modulo Arithmetic: The structure of the Mycielskian depends critically on the parameter $l$. The author divides the analysis into three cases based on $l \pmod 3$ ($l=3k, 3k+1, 3k+2$).
  • Recursive Formulas: For iterated Mycielskians, the author defines counting functions $f(k,r)$ and $g(k,r)$ to track the number of suspensions and joins in the resulting homotopy type.

3. Key Contributions and Main Results

A. The Main Theorem (Theorem 5)

The paper establishes that the homotopy type of $I(\mu_l(G))$ is determined entirely by the homotopy types of $I(G)$ and $I(G \times P_2)$. Specifically, for any graph $G$:

• If $l = 3k$:
  $$I(\mu_{3k}(G)) \simeq I(G) * I(G \times P_2)^{*k} \vee \Sigma I(G \times P_2)^{*k}$$
• If $l = 3k + 1$:
  $$I(\mu_{3k+1}(G)) \simeq \Sigma I(G) * I(G \times P_2)^{*k}$$
• If $l = 3k + 2$:
  $$I(\mu_{3k+2}(G)) \simeq I(G \times P_2)^{*k+1}$$
  (Where $*$ denotes the join, $\vee$ the wedge sum, and $\Sigma$ the suspension.)

B. Iterated Mycielskians (Section 4)

The author extends the results to $r$-iterated constructions ($\mu_l^r(G)$).

• Theorem 16: Provides explicit formulas for the homotopy type of $\mu_{3k+1}^r(G)$ and $\mu_{3k+2}^r(G)$ using the functions $f(k,r)$ and $g(k,r)$. These formulas express the complex as a suspension of a join of copies of $I(G)$ and $I(G \times P_2)$.
• Theorem 17: For the case $l=3k$, while a single closed formula is not feasible, it is proven that the complex is homotopy equivalent to a wedge of spaces, each being an iterated suspension of joins of $I(G)$ and $I(G \times P_2)$.

C. Applications to Specific Graph Families

The paper applies the main theorems to derive concrete results for well-known graph families:

1. Complete Graphs ($K_n$):
   • Recovers and generalizes the result that $I(\mu_l(K_n))$ is a wedge of spheres.
   • Provides specific dimensions and counts of spheres based on $n$ and $l$ (Corollary 7).
2. Categorical Products of Complete Graphs ($K_n \times K_m$):
   • Derives the homotopy type for $I(\mu_l(K_n \times K_m))$ as a wedge of spheres (Corollary 8).
3. Paths ($P_n$) and Cycles ($C_n$):
   • Calculates the homotopy type for paths and cycles.
   • Corollary 9: Proves that for any cycle $C_n$ ($n \ge 3$), $I(\mu_l(C_n))$ is homotopy equivalent to a wedge of spheres. The specific dimensions and counts are tabulated in Table 1.
4. Bipartite Graphs and Forests:
   • Proposition 10: For bipartite graphs, $G \times P_2 \cong G \sqcup G$, simplifying the formula significantly.
   • Corollary 12: If $T$ is a forest, $I(\mu_l(T))$ is either contractible or a wedge of spheres.
   • Corollary 13: Extends this to rectangular lattices with at most 6 rows.

4. Significance

• Unification: The paper unifies previous scattered results (e.g., for $l=1$ or specific graphs) into a single, comprehensive framework based on the interaction between a graph and its Kronecker double cover.
• Topological Characterization: It demonstrates that for a vast class of graphs (including paths, cycles, and products of complete graphs), the independence complex of their generalized Mycielskians retains a "simple" topological structure: a wedge of spheres.
• Algorithmic Insight: The recursive formulas for iterated Mycielskians provide a method to compute the homotopy type of highly complex graphs without constructing the full simplicial complex, relying instead on the properties of the base graph.
• Foundational Tool: The techniques involving neighborhood inclusion and the specific decomposition of the Mycielskian structure offer a template for analyzing other graph operations in algebraic topology.

In summary, Carnero Bravo successfully determines the homotopy type of independence complexes for generalized Mycielskians, proving they are generally wedges of spheres or joins of suspensions of the base graph's complex and its double cover, and applies this to solve specific cases for paths, cycles, and grid-like structures.