Abstract
In view of Tucker's lemma—an equivalent combinatorial version of the Borsuk-Ulam theorem—the present authors previously introduced the $k^{th}$ altermatic number of a graph $G$ as a tight lower bound for the chromatic number of $G$. In this note, we present a purely combinatorial proof for this result, moving away from continuous topological tools toward a discrete, path-following argument.
Introduction
In graph theory, determining the chromatic number $\chi(G)$—the minimum number of colors needed to color the vertices of a graph so no two adjacent vertices share a color—is a notoriously difficult (NP-hard) problem. To tackle this, mathematicians seek "lower bounds," or guaranteed minimum values that $\chi(G)$ must meet.
Historically, some of the strongest lower bounds were discovered using algebraic topology, specifically the Borsuk-Ulam theorem. While effective, these topological proofs often rely on continuous spaces to solve discrete problems. The authors previously introduced the altermatic number $\zeta(G, k)$ as a tight lower bound for the chromatic number, but the original proof relied on Tucker’s Lemma. This note addresses the challenge of proving this bound using only "pure" combinatorial methods—essentially counting and discrete structures—without invoking the machinery of topology.
Methodology
The authors employ a proof by contradiction centered on the properties of alternating subsequences and General Kneser Graphs. The proof is structured around several key discrete constructions:
- Vector Representations: Vertex sets are represented using vectors $X \in \{R, 0, B\}^n$ (where $R$ and $B$ can be thought of as "Red" and "Blue" or positive/negative signs). The value $alt(X)$ is defined as the length of the longest sequence in $X$ that alternates between $R$ and $B$.
- The Mapping $\lambda$: A specific mapping $\lambda$ is constructed to assign an integer to these vectors based on their alternating length and the coloring of the graph.
- Permissible Sequences: The core of the new proof involves defining "permissible sequences" of these colored sets.
- The Graph Construction: The authors build a secondary, abstract graph where the vertices are these permissible sequences. By analyzing the degrees of the vertices in this new graph, they show that if the theorem were false, the graph would have exactly one vertex of degree one and all others of degree two. Since the sum of degrees in any graph must be even (the Handshaking Lemma), this is a mathematical impossibility, thus proving the theorem.
Key Insights
Discrete vs. Continuous
The paper demonstrates that the "topological" strength of Tucker's Lemma can be captured entirely through discrete path-following arguments. This is part of a broader trend in combinatorics to find "elementary" proofs for results originally found via topology. The "aha moment" is the realization that the existence of a solution (the bound) can be proven by showing that a specific discrete path in a state-space of sequences must have an end-point, mirroring how fixed-point theorems work in continuous space.
Generalization and Tightness
The $k^{th}$ altermatic number is shown to be a flexible tool and an improvement over other famous bounds, such as the Dol’nikov-Kříž bound. The authors confirm that for certain parameters (specifically when $k = \chi(KG(\mathcal{H})) + 1$), the altermatic number exactly equals the chromatic number of the Kneser graph, making it a "tight" bound.
Results and Implications
The authors successfully provide a combinatorial proof for the inequality $\chi(G) \geq \zeta(G, k)$. This result provides a new way to look at the Lovász-Kneser theorem, a landmark result from the 1970s that first linked topology to graph coloring.
However, there are practical limitations to this theoretical strength. While the bound is mathematically tight, calculating the first altermatic number for an arbitrary hypergraph is an NP-hard problem. This means that while the bound is theoretically powerful, it remains difficult to compute for very large or complex graphs. Future work may involve identifying specific families of graphs where the altermatic number is easier to compute or provides significantly better results than simpler, traditional bounds.
Summary updated