Fact-checked by Grok 2 weeks ago

Kneser graph

In graph theory, the Kneser graph KG_{n,k} (also denoted K(n,k)) is defined for integers n \geq 2k \geq 2 as the graph whose vertex set consists of all k-element subsets of an n-element ground set \{1, 2, \dots, n\}, with two vertices adjacent if and only if the corresponding subsets are pairwise disjoint.^[1] This construction yields a regular graph of degree \binom{n-k}{k}, and the graphs are vertex-transitive, meaning there exists an automorphism mapping any vertex to any other. The family of Kneser graphs is named after the German mathematician Martin Kneser, who introduced it in 1955 while studying a problem on partitioning the k-subsets of an n-set into classes where no two disjoint subsets belong to the same class.^[2] These graphs rose to prominence through Kneser's conjecture, which posited that the chromatic number of KG_{n,k} (the minimum number of colors needed to color the vertices so that no adjacent vertices share the same color) is exactly n - 2k + 2.^[3] In 1978, László Lovász proved this conjecture using algebraic topology, specifically the Borsuk–Ulam theorem, thereby establishing the result and founding the field of topological combinatorics.^[3] A well-known example is KG_{5,2}, which is isomorphic to the Petersen graph, a 3-regular graph on 10 vertices that serves as a counterexample in many graph theory contexts.^[4] Kneser graphs have since been extensively studied for properties such as diameter (at most 2 for n > 2k)^[5], connectivity, and Hamiltonicity; notably, it was conjectured in the 1970s that all such graphs are Hamiltonian except the Petersen graph, a result recently confirmed in 2023.^[1]

Definition

Formal definition

The Kneser graph KG(n,k) is defined for positive integers n and k with n \geq 2k, where the vertex set consists of all k-element subsets of the ground set = \{1, 2, \dots, n\}. Two vertices are adjacent if and only if the corresponding subsets are pairwise disjoint. This construction yields a simple undirected graph, provided n > 2k - 1; otherwise, for n \leq 2k - 1, any two k-subsets must intersect (by the pigeonhole principle), resulting in the empty graph with no edges. The Kneser graph arises in the study of intersection theorems in extremal set theory, where edges encode non-intersecting pairs, complementing structures like intersecting families in the Erdős–Ko–Rado theorem. For instance, the case KG(5,2) is isomorphic to the Petersen graph.^[6]

Notation and parameters

The Kneser graph is standardly denoted KG_{n,k} or K(n,k), where n denotes the cardinality of the ground set and k the size of each subset, with the parameter restriction n \geq 2k to guarantee that disjoint pairs exist and the graph is nontrivial.^[7] The vertex set consists of all k-element subsets of the ground set = \{1, 2, \dots, n\}, so the order (number of vertices) is the binomial coefficient \binom{n}{k}.^[7] Two vertices, corresponding to subsets A and B, are adjacent if and only if A \cap B = \emptyset.^[7] Each vertex has degree \binom{n-k}{k}, equal to the number of ways to choose a k-subset from the remaining n-k elements outside a fixed k-subset.^[7] Consequently, the Kneser graph is regular of that degree, and its size (number of edges) is half the product of the order and degree:

\frac{1}{2} \binom{n}{k} \binom{n-k}{k}.

^[7]

History

Introduction and conjecture

The Kneser graph is a family of graphs introduced by the German mathematician Martin Kneser in 1955, as a problem in graph coloring.^[4] Kneser defined these graphs to model the intersection properties of k-element subsets of an n-element set, where vertices correspond to the subsets and edges connect pairs with empty intersection.^[4] This construction provided a combinatorial framework for exploring coloring problems motivated by finite set systems.^[8] Kneser conjectured that the chromatic number of the Kneser graph \mathrm{KG}_{n,k} satisfies \chi(\mathrm{KG}_{n,k}) = n - 2k + 2 for all integers n \geq 2k \geq 2.^[3] The conjecture drew from observations on the minimal number of colors needed to avoid monochromatic disjoint pairs, reflecting deeper patterns in extremal set theory.^[4] Similar intersection-based ideas in Kneser's work around the same period also inspired the geometric Kneser-Poulsen conjecture, which concerns the monotonicity of union volumes under contractions of ball centers.^[9] For the base case k=1, the Kneser graph \mathrm{KG}_{n,1} is the complete graph K_n, which has chromatic number n, aligning precisely with the conjectured formula n - 2 \cdot 1 + 2 = n.^[4] This verification provided initial support for the general claim, though broader partial results remained elusive until later developments. The full conjecture was established in 1978 by László Lovász using methods from algebraic topology.^[3]

Key proofs and developments

One of the landmark results in the study of Kneser graphs is László Lovász's 1978 proof of Kneser's conjecture, which established that the chromatic number of the Kneser graph KG(n,k) is n - 2k + 2 for n \geq 2k. This proof employed topological methods, specifically leveraging the Borsuk-Ulam theorem and properties of simplicial complexes to demonstrate that any coloring with fewer colors leads to a contradiction via a continuous map without fixed points. Independently, Imre Bárány provided a shorter combinatorial proof in the same year, also relying on topological insights but emphasizing Gale's theorem on convex sets. These proofs not only resolved the conjecture but also initiated the application of algebraic topology to graph coloring problems. The independence number of Kneser graphs is determined by the Erdős–Ko–Rado theorem from 1961, which states that for n \geq 2k, the maximum size of an independent set in KG(n,k) is \binom{n-1}{k-1}, corresponding to the family of all k-subsets containing a fixed element. This bound holds with equality for the "star" families, and the theorem's proof uses the delta-system method and double counting. Extensions, such as stability versions by Frankl and others in the 1980s, characterize near-maximal independent sets and have implications for intersecting families beyond the classical case. In spectral graph theory, the eigenvalues of Kneser graphs were characterized in the 1980s and formalized in Chris Godsil and Gordon Royle's 2001 monograph, where the distinct eigenvalues are given by (-1)^j \binom{n-k-j}{k-j} for j = 0, 1, \dots, k, with multiplicities \binom{n}{j} - \binom{n}{j-1}. Godsil's contributions, including connections to association schemes and orthogonal polynomials, provided tools for analyzing connectivity and expansion properties, influencing subsequent work on distance-regular graphs. The Hamiltonian cycle conjecture for Kneser graphs, positing that KG(n,k) is Hamiltonian for all n > 2k except the Petersen graph KG(5,2), saw partial progress in 2003 when Ya-Chen Chen proved the existence of such cycles for n \geq \frac{3 + \sqrt{5}}{2} k + 1 \approx 2.618k + 1, using inductive constructions on subcubes. This was fully resolved in 2023 by Arturo I. Merino, Torsten Mütze, and Namrata, who established Hamiltonicity for all connected Kneser graphs except the Petersen graph, employing a kinetic framework of interacting gliders to construct explicit cycles.^[1] Recent developments include computational bounds on induced subgraphs, as in Chau et al.'s 2025 analysis of maximum degrees in subgraphs of KG(n,k), providing asymptotic stability results for extremal structures. Ongoing research also explores q-analogs of Kneser graphs over finite fields, with applications to quantum information theory and coding bounds, as seen in works on their chromatic numbers and symmetry groups since the early 2020s.

Examples

Small cases

The Kneser graph KG(n,1) consists of the n singletons as vertices, with two distinct singletons always disjoint, yielding the complete graph K_n on n vertices. For parameters n = 2k, the graph KG(2k,k) has \binom{2k}{k} vertices corresponding to all k-subsets of a $2k-element set. Any two such subsets must intersect in at least one element, except for pairs that form a partition of the ground set into complementary k-subsets; each vertex thus connects uniquely to its complement, resulting in a 1-regular graph that is a perfect matching consisting of \binom{2k}{k}/2 disjoint edges. In the case n = 2k+1, the Kneser graph KG(2k+1,k)—also known as the odd graph O_{k+1}—features \binom{2k+1}{k} vertices, each of degree k+1, since for any k-subset, its disjoint neighbors are the k-subsets of the complementary (k+1)-element set. This graph is connected and serves as a foundational example of a vertex-transitive graph with nontrivial structure. A prominent small instance is KG(5,2), which has 10 vertices and 15 edges and is isomorphic to the Petersen graph.^[10] For small parameters such as n \leq 10 and k \leq 3, the resulting Kneser graphs have at most \binom{10}{3} = 120 vertices, making them computationally tractable for explicit construction and analysis, including adjacency matrices, though larger instances grow rapidly in size.

Notable special cases

One prominent infinite family of Kneser graphs is the odd graphs, defined as O_m = \mathrm{KG}(2m-1, m-1) for integers m \geq 2. These graphs have been extensively studied for their symmetry and connectivity. A well-known example is the odd graph O_3 = \mathrm{KG}(5,2), which is the Petersen graph with 10 vertices and girth 5.^[11] The Kneser graphs \mathrm{KG}(n,2) for n \geq 5 form another notable family, isomorphic to the complement of the line graph of the complete graph K_n. This connection links Kneser graphs to edge-intersection properties in complete graphs, facilitating applications in domination and independence problems. For fixed k=2, the graphs \mathrm{KG}(n,2) are strongly regular with parameters \left( \binom{n}{2}, \binom{n-2}{2}, \binom{n-4}{2}, \binom{n-3}{2} \right). This structure underscores their role in extremal graph theory, with distinct \lambda and \mu highlighting neighborhood intersections for disjoint versus intersecting pairs.

Properties

Basic structural properties

The Kneser graph KG(n,k) is a regular graph of degree \binom{n-k}{k}, as each vertex corresponding to a k-subset connects to all k-subsets chosen from the remaining n-k elements, and this count is uniform across all vertices due to the symmetric structure of the subset lattice. The graph is vertex-transitive, since the symmetric group S_n acts on the ground set and induces automorphisms that map any k-subset to any other, preserving the disjointness condition for edges. Moreover, it is arc-transitive (equivalently, edge-transitive), as the same group action transitively maps any ordered pair of adjacent vertices to any other such pair.^[2] For k=2, the Kneser graph KG(n,2) is strongly regular with parameters \left( \binom{n}{2}, \binom{n-2}{2}, \binom{n-4}{2}, \binom{n-3}{2} \right), meaning any two adjacent vertices have \binom{n-4}{2} common neighbors and any two non-adjacent vertices have \binom{n-3}{2} common neighbors.^[12] The graph is connected precisely when n > 2k, as paths between intersecting subsets can be constructed by gradually adjusting elements while maintaining disjointness in intermediate steps. In this case, the vertex connectivity equals the degree \binom{n-k}{k}, a consequence of the graph being regular, vertex-transitive, and edge-transitive.^[2] The girth of KG(n,k) is 3 when n \geq 3k, since three pairwise disjoint k-subsets form a triangle; otherwise, the girth is greater than 3, as in the case of the Petersen graph KG(5,2) with girth 5.

Chromatic and independence numbers

The chromatic number of the Kneser graph KG_{n,k} is $1 when n < 2k, as there are no edges in this case, making the graph edgeless.^[3] For n \geq 2k, the chromatic number \chi(KG_{n,k}) is n - 2k + 2, proved by Lovász using topological methods.^[3] The fractional chromatic number \chi_f(KG_{n,k}) is n/k, obtained via the linear programming relaxation of the graph coloring problem, where the optimum equals the ratio of the number of vertices to the independence number.^[13] The independence number \alpha(KG_{n,k}) is \binom{n-1}{k-1} for n \geq 2k, by the Erdős–Ko–Rado theorem, which identifies the maximum intersecting family of k-subsets as those containing a fixed element. This yields the general lower bound \chi(G) \geq |V(G)| / \alpha(G) = n/k for any graph G, with equality in the Kneser case only when k=1, as KG_{n,1} is the complete graph K_n.^[13] Recent studies on quantum graph coloring provide intermediate bounds; for instance, the quantum chromatic number of KG_{p,2} is p-2.^[14]

Cliques, cycles, and diameter

In the Kneser graph \mathrm{KG}(n,k), a clique corresponds to a collection of k-subsets of an n-element set that are pairwise disjoint. The maximum size of such a collection is therefore \lfloor n/k \rfloor, as this is the maximum number of non-overlapping k-subsets that can be packed into an n-element set; this bound is achieved by partitioning the ground set into as many k-subsets as possible, with a possible remainder of fewer than k elements.^[15] Consequently, the clique number \omega(\mathrm{KG}(n,k)) = \lfloor n/k \rfloor. In particular, when n < 3k, no three k-subsets can be pairwise disjoint, so \omega(\mathrm{KG}(n,k)) = 2 and the graph is triangle-free.^[16] The presence or absence of short cycles in \mathrm{KG}(n,k) depends on the parameters n and k. The girth is 3 precisely when n \geq 3k, as the graph then contains triangles corresponding to three pairwise disjoint k-subsets. For $2k \leq n < 3k, the graph is triangle-free, but cycles of length 4 exist when n \geq 2k+2; for example, one can construct a 4-cycle using four k-subsets where alternating pairs are disjoint but the opposite pairs intersect. When n = 2k+1, the graph is an odd graph with girth 5 (for k=2, this is the Petersen graph). For n = 2k, the graph consists of \binom{2k}{k}/2 disjoint edges (each connecting complementary k-subsets) and thus has no cycles. The triangle-free cases with n < 3k yield high-chromatic graphs despite lacking K_3, providing combinatorial analogs to the Borsuk conjecture on partitioning sets into classes of smaller diameter; the proof of their chromatic number n-2k+2 relies on topological methods resolving the conjecture in this setting. The diameter of the connected Kneser graph \mathrm{KG}(n,k) for n > 2k is \left\lceil \frac{k-1}{n-2k} \right\rceil + 1, which equals 2 for sufficiently large n relative to k (specifically, when n \geq 3k - 1). This value arises from distances measured along chains of k-subsets where consecutive subsets are disjoint, effectively reducing the intersection size between the starting and ending subsets step by step; the formula bounds the minimum number of such steps needed between any two vertices. Recent algorithmic approaches confirm this for large n by computing shortest paths via intersection patterns, aligning with the closed-form expression without requiring case-by-case enumeration.^[5]^[17]

Spectrum and eigenvalues

The spectrum of the adjacency matrix of the Kneser graph KG(n,k) consists of the eigenvalues \theta_j = (-1)^j \binom{n - k - j}{k - j} for j = 0, 1, \dots, k, each with multiplicity f_j = \binom{n}{j} - \binom{n}{j-1}. These eigenvalues are derived using the association scheme structure of the Johnson graph, of which the Kneser graph is a subgraph, and the multiplicities ensure the total dimension matches the number of vertices \binom{n}{k}. The largest eigenvalue \theta_0 = \binom{n-k}{k} corresponds to the degree of the graph and has multiplicity 1, associated with the all-ones eigenvector. The second-largest eigenvalue \theta_1 = -\binom{n-k-1}{k-1} determines the algebraic connectivity in the context of spectral graph theory, providing bounds on mixing times and expansion properties. For fixed k and large n, the ratio |\theta_1| / \theta_0 \approx k/n is small, indicating that Kneser graphs exhibit expander-like behavior with a spectral gap that grows with n. This property has been leveraged in constructions requiring high connectivity relative to degree. For the special case k=2, the Kneser graph KG(n,2) is strongly regular with parameters (\binom{n}{2}, \binom{n-2}{2}, \binom{n-4}{2}, \binom{n-3}{2}), and its spectrum simplifies to \theta_0 = \binom{n-2}{2} (multiplicity 1), \theta_1 = -(n-3) (multiplicity n-1), and \theta_2 = 1 (multiplicity \binom{n}{2} - n). The multiplicities f and g for the restricted eigenvalues \theta and \tau follow from the general formula, confirming the strongly regular structure.

Hamiltonian properties

The Petersen graph, which is the Kneser graph KG(5,2), is non-Hamiltonian. Its non-Hamiltonicity follows from exhaustive structural analysis showing that no cycle can visit all 10 vertices exactly once, a result established through case-by-case enumeration of possible paths and the graph's high symmetry preventing closure. Early progress toward resolving the Hamiltonicity of Kneser graphs came in 2003, when Chen proved that KG(n,k) admits a Hamilton cycle whenever n \geq \frac{3k + 1 + \sqrt{5k^2 - 2k + 1}}{2}, approximately n \geq 2.618k.00040-6) This bound improved upon prior partial results and applied particularly to triangle-free cases, but left smaller parameters unresolved. A simpler proof for the regime n \geq 4k was later provided using degree conditions. The full conjecture—that all connected Kneser graphs KG(n,k) with n \geq 2k+1 are Hamiltonian except the Petersen graph—was resolved affirmatively in 2023 by Merino, Mütze, and Namrata. Their constructive proof generates an explicit Hamilton cycle via a recursive combinatorial encoding of the vertices as binary strings, resolving a problem open since the 1970s. For larger n, such as n \geq 4k, the minimum degree \binom{n-k}{k} exceeds half the number of vertices \binom{n}{k}/2, satisfying Dirac's theorem and guaranteeing a Hamilton cycle independently of the full proof. Adaptations of Ore's theorem, which consider sums of degrees for non-adjacent vertices, similarly confirm Hamiltonicity in these dense regimes by leveraging the uniform high connectivity of Kneser graphs. Kneser graphs KG(n,k) with n > 2k are Hamiltonian-connected, meaning there exists a Hamilton path between any pair of distinct vertices; this follows from extensions of the cycle constructions that allow starting and ending at specified points while covering all vertices. Recent extensions in 2025 have addressed directed and oriented variants, including proofs of Hamiltonicity for connected s-stable Kneser graphs, which delete certain cyclic-adjacent subsets and inherit the structure while maintaining the original's connectivity properties.^[18]^[19]

Odd graphs

The odd graphs constitute a prominent subclass of the Kneser graphs, arising from specific parameter choices that yield symmetric and highly structured graphs. The odd graph O_m is the Kneser graph \mathrm{KG}_{2m-1, m-1}, with vertices corresponding to the (m-1)-element subsets of a ground set with $2m-1 elements, and edges connecting pairs of vertices whose subsets are disjoint.^[20] This construction, introduced by Norman Biggs, emphasizes the combinatorial symmetry inherent in selecting subsets from an odd-sized universe, leading to graphs with notable regularity and transitivity properties.^[21] The order of O_m is \binom{2m-1}{m-1}, reflecting the total number of (m-1)-subsets, while each vertex has degree m, as a fixed (m-1)-subset is disjoint from exactly m others chosen from the remaining m elements.^[20] The diameter of O_m is m-1, which aligns with the minimal number of steps needed to connect subsets through chains of increasing intersections.^[20] These parameters ensure that odd graphs are distance-regular, and in fact distance-transitive, meaning the automorphism group acts transitively on pairs of vertices at any fixed distance.^[20] For instance, O_3 is the well-known Petersen graph, a 3-regular graph on 10 vertices with diameter 2, serving as a foundational example in graph theory.^[20] Similarly, O_4, on 35 vertices and 4-regular, appears as an induced subgraph of the Hoffman-Singleton graph. Odd graphs play a key role in the theory of association schemes, particularly as the graph corresponding to the disjointness relation (intersection size 0) within the Johnson association scheme J(2m-1, m-1), where relations are defined by subset intersection sizes.^[22] This positioning highlights their utility in algebraic combinatorics, enabling the study of eigenvalues, representations, and coherent configurations derived from the Bose-Mesner algebra of the scheme.^[22] The symmetric parameters of odd graphs distinguish them from more general Kneser graphs by producing balanced structures that facilitate applications in extremal set theory and coding.^[21]

Complements and line graphs

The complement of the Kneser graph KG_{n,k}, denoted \overline{KG_{n,k}}, retains the vertex set of all k-subsets of an n-element set, but connects two vertices by an edge precisely when their corresponding subsets have nonempty intersection.^[23] For the specific case k=2, the Kneser graph KG_{n,2} is the complement of the line graph L(K_n) of the complete graph K_n on n vertices.^[24] In L(K_n), the vertices represent the edges of K_n, and two vertices are adjacent if the edges they represent share a common vertex (i.e., are incident).^[25] This equivalence arises because the 2-subsets (edges) of the n-set are adjacent in L(K_n) when they intersect at a vertex, mirroring the intersection-based edges in the complement of KG_{n,2}; thus, KG_{n,2} connects non-incident edges.^[26] In this case, the complement is isomorphic to the Johnson graph J(n,2).^[27] Key properties of the complement relate directly to those of KG_{n,k}: the independence number \alpha(KG_{n,k}) equals the clique number \omega(\overline{KG_{n,k}}), as an independent set in KG_{n,k} (pairwise disjoint subsets) forms a clique in the complement (all pairwise intersecting).^[23] Conversely, the clique number \omega(KG_{n,k}) (mutually disjoint subsets) matches the independence number \alpha(\overline{KG_{n,k}}).^[28] These relations highlight how extremal set theory parameters, such as the maximum size of intersecting or disjoint families, translate between the graphs.^[27] In general, the Kneser graph KG_{n,k} serves as the complement of the intersection graph on the family of k-subsets, where the intersection graph edges denote nonempty intersections among subsets.^[23] This perspective positions KG_{n,k} as a disjointness graph, emphasizing its role in studying non-intersecting configurations within combinatorial designs.^[28]

Generalizations

Generalized Kneser graphs

The generalized Kneser graph KG(n,k,s) is defined as the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the corresponding subsets intersect in at most s elements, where 0 ≤ s < k and n ≥ 2k. This construction extends the standard Kneser graph by allowing adjacency for subsets with small intersections up to size s, rather than only disjoint pairs. The parameter s controls the "tolerance" for intersection in adjacency, leading to denser graphs as s increases.^[29] In the variant where adjacency is defined for exactly s intersection, the graph connects k-subsets that share precisely s elements. This variant includes the standard Kneser graph for s=0 and the Johnson graph J(n,k) for s=k-1, where edges connect subsets that differ by exactly one element (intersection k-1). The degree of a vertex in the at-most-s variant is \sum_{i=0}^s \binom{k}{i} \binom{n-k}{k-i}, counting the k-subsets intersecting a fixed k-subset in exactly i elements for i from 0 to s. For the exactly-s variant, the degree simplifies to \binom{k}{s} \binom{n-k}{k-s}.^[30] The chromatic number of KG(n,k,s) generalizes Kneser's conjecture, with Frankl and Füredi establishing that for fixed k and s, the chromatic number is n - 2(k - s) + 2 when n is sufficiently large, extending Lovász's topological proof to these denser graphs. Frankl's earlier work specifically addressed the case s=1, providing bounds and constructions for coloring subsets such that no two with intersection at most 1 share a color, corresponding to covering by 2-intersecting families. These results highlight how the chromatic number increases with s, reflecting the stricter condition for color classes to be (s+1)-intersecting families.^[31] Recent research has explored structural properties of these graphs for larger s. For example, in 2022, it was proved that the treewidth of KG(n,k,t) (where adjacency is for intersection at most t-1, so s = t-1) is exactly \binom{n-t}{k-t} - 1, providing a precise measure of the graph's decomposition complexity and aiding algorithmic applications. For s=2 (adjacency if intersection at most 2), this yields treewidth \binom{n-3}{k-3} - 1. Additionally, in 2023, it was shown that all generalized Kneser graphs KG(n,k,s) are Hamiltonian for n ≥ 2k - s (except the Petersen graph), resolving a long-standing question and confirming the existence of Hamilton cycles in these structures using combinatorial rotations. These advances underscore the ongoing interest in the connectivity and decomposition properties of generalized Kneser graphs for s ≥ 2.^[1]

Other variants

Oriented Kneser graphs arise from directing the edges of standard Kneser graphs KG(n,k) in specific ways to study properties like acyclicity and transitivity. One notable construction orients edges to form semi-transitive orientations, where the digraph is acyclic and any directed path implies a direct edge or comparability. Kneser graphs KG(n,k) and their complements admit semi-transitive orientations if and only if n \leq 2k+2 or k=1, with the exceptional case KG(5,2) (the Petersen graph) requiring special handling due to its non-Hamiltonian nature.^[32] Another approach uses lexicographic order on subsets to orient edges in auxiliary graphs derived from Kneser or Schrijver graphs, facilitating proofs of Hamiltonicity. In this setup, edges point from one cycle representative to another based on decreasing lexicographic labels of connecting subsets, ensuring the resulting digraph is acyclic and connected for constructing spanning trees. This orientation supports recursive decompositions for finding Hamilton cycles in stable Kneser graphs.^[33] Geometric Kneser graphs extend the combinatorial structure to points in the Euclidean plane. For a set S of n points in general position (no three collinear), the vertices are all k-subsets of S, with edges defined by geometric conditions on convex hulls. The segment disjointness graph D(S) connects two k-subsets if their convex hulls are disjoint, while the segment intersection graph I(S) connects them if the hulls intersect. For k=2, these reduce to graphs on line segments formed by pairs of points.^[34] When points are in convex position, the chromatic number of the disjointness graph D(n) satisfies $2 \lfloor (n+1)/3 \rfloor - 1 \leq \chi(D(n)) \leq \min(n-2, n - \lfloor \log n \rfloor / 2), providing tight bounds for large n. For the intersection graph I(n), \chi(I(n)) = n. In general position, looser bounds hold, such as $5 \lfloor n/7 \rfloor \leq \chi(D(n)) \leq \min(n-2, n + 1/2 - \lfloor \log \log n \rfloor / 2) and n \leq \chi(I(n)) \leq C n^{3/2} for some constant C > 0. These results highlight how geometric constraints alter coloring properties compared to combinatorial Kneser graphs.^[34] Circular Kneser graphs adapt the vertex set to a cyclic structure, considering n points arranged on a circle in clockwise order. Vertices are k-polygons, which are r-stable k-subsets (sets of k points where the minimum circular distance between any two points in the subset is at least r), with n \geq r k and r \geq 2. This variant, denoted IG(n,k), forms an induced subgraph of the standard Kneser graph but incorporates rotational symmetry. Two such polygons P and Q are adjacent if and only if their corresponding subsets are disjoint. Its chromatic number is \lceil n/k \rceil, matching the circular arrangement's periodicity, and the circular chromatic number equals n/k. These graphs have been analyzed using topological methods akin to Lovász's original proof, linking them to Borsuk-Ulam-type theorems in combinatorial topology.^[35] Quantum variants of Kneser graphs emerge in quantum graph theory, often as q-analogs where vertices represent k-dimensional subspaces of an n-dimensional vector space over the finite field \mathbb{F}_q, with edges between subspaces of trivial intersection. The chromatic number of the q-Kneser graph KG_q(n,k) is n - 2k + 2 for q \geq 2 and n \geq 2k, mirroring the classical case but with quantum-inspired proofs using finite geometry and representation theory. More advanced constructions explore quantum homomorphisms to Kneser graphs, where quantum colorings correspond to projective representations, providing bounds on quantum chromatic numbers that generalize fractional chromatic numbers. For instance, the quantum chromatic number of certain Kneser-like graphs relates to the dimension of Hilbert spaces encoding subset intersections.^[36]^[37]

Applications

Combinatorial extremal problems

Kneser graphs play a central role in the Erdős–Ko–Rado theorem, which characterizes the maximum size of an intersecting family of k-subsets from an n-element set, where n \geq 2k. The vertices of the Kneser graph KG(n,k) correspond to these k-subsets, with edges connecting disjoint pairs, so independent sets in KG(n,k) precisely represent intersecting families. Thus, the independence number \alpha(KG(n,k)) provides the bound on the largest such family, given by \binom{n-1}{k-1}, achieved by taking all k-subsets containing a fixed element.^[38] Kneser's conjecture, proved by Lovász, establishes that the chromatic number \chi(KG(n,k)) = n - 2k + 2 for n \geq 2k, implying that the k-subsets can be partitioned into exactly n - 2k + 2 intersecting families, with each color class forming an independent set free of disjoint pairs. This minimal partitioning has implications for non-intersecting family colorings, as it sets the lower bound for covering all k-subsets with intersecting subfamilies, influencing problems on the minimum number of such classes needed to avoid monochromatic disjoint pairs in hypergraph colorings.^[39] In Turán-type problems, Kneser graphs model extremal questions about excluding complete subgraphs K_t as induced subgraphs, corresponding to avoiding certain t-wise disjoint configurations in uniform set families within the subset lattice. For a fixed graph G with q vertices, the maximum size of an induced G-free subgraph in KG(n,k) is at most \binom{n}{k}/q for sufficiently large n, with equality when the family is defined by all k-subsets intersecting a fixed (q-1)-set. When G = K_t, this yields bounds on t-union intersecting families, extending the Erdős–Ko–Rado setting to larger forbidden structures.^[40] Recent advancements since 2021 leverage the chromatic number of Kneser hypergraphs—generalizing Lovász's result via the Alon–Frankl–Lovász theorem—to derive shadow bounds in extremal set theory. Specifically, in q-colorings of r-uniform complete hypergraphs on n vertices, the theorem ensures large monochromatic matchings when n \geq (q-1)(k-1) + k r, and defect versions bound the shadow sizes of families avoiding such matchings, providing tighter inequalities for the (k-1)-shadows of k-uniform families. These results refine classical shadow partial order arguments, such as those in the LYM inequality, by incorporating hypergraph chromatic constraints.^[41]

Coding and design theory

Kneser graphs serve as models for constant weight codes in coding theory, where the vertices correspond to binary vectors of length n and constant weight k, representing the characteristic vectors of k-subsets of an n-element set. The Hamming distance between two such codewords is d(u,v) = 2(k - |u \cap v|), so edges in the Kneser graph KG(n,k) connect codewords at maximum distance $2k, corresponding to disjoint subsets.^[42] Subsets of vertices thus form constant weight codes with minimum distance determined by the maximum intersection size among any two codewords; for instance, a code with minimum distance at least $2\delta requires that no two codewords intersect in more than k - \delta positions.^[42] The structure of Kneser graphs arises from the Johnson association scheme, where relations are defined by intersection sizes, enabling constructions of block designs. Strongly regular Kneser graphs, such as odd graphs O_{k+1} = KG(2k+1, k), yield balanced incomplete block designs (BIBDs) through their distance-regular properties and automorphism groups; for example, neighbour-transitive codes in these graphs correspond to orbits under actions like those of Mathieu groups, producing designs with block sizes tied to intersection parameters.^[42] These schemes facilitate design construction by partitioning the vertex set into parallel classes based on fixed intersections, as seen in supports of codes derived from adjacency matrices that form 3-designs.^[43] A notable example is the Petersen graph KG(5,2), whose complement relates to the ternary Golay code via endecads—12-subsets of a 24-set intersecting in 6 or 7 points—forming a code whose automorphism group is the Mathieu group M_{23}, and whose supports yield a 5-(24,12,117) design linked to the extended Golay code.^[42] More generally, adjacency matrices of Kneser graphs KG(n,2) construct self-dual and linear complementary dual (LCD) codes; for binary self-dual codes, the pure construction using the adjacency matrix A of KG(n,2) yields a [ \binom{n}{2}, \frac{1}{2} \binom{n}{2}, d ] code with d depending on the graph's parameters, such as d=4 for n=7. Ternary variants, like those for n=9, produce self-dual codes with minimum distance 6, applicable to quantum stabilizer codes via the CSS construction.^[43] Spectral properties of Kneser graphs, particularly as strongly regular graphs, bound code rates in quantum error correction; the eigenvalues of KG(2k+1,k) include the degree \binom{k+1}{k} = k+1 with multiplicity 1, and others such as -k and intermediate values derived from the Johnson scheme, providing bounds on the dimension of quantum CSS codes from self-dual subcodes, as in post-2020 constructions where the second-largest eigenvalue limits entanglement rates.^[43]

References

[1]
Kneser Graphs Are Hamiltonian | Proceedings of the 55th Annual ...
Jun 2, 2023 · Sparse Kneser graphs are Hamiltonian For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets ...
[2]
On the diameter of Kneser graphs - ScienceDirect.com
The Kneser graph K n 2 n + k is the graph with vertex set [ 2 n + k ] n and where two n-subsets A , B ∈ [ 2 n + k ] n are joined by an edge if A ∩ B = ∅ . Note ...
[3]
[PDF] The super-connectivity of Kneser graphs - Biblioteka Nauki
This family of graphs was introduced in 1955 by Kneser [11]. It is well-known that if n < 2k, then KG(n, k) is the empty graph (that is, the graph consisting of ...
[4]
Kneser's conjecture, chromatic number, and homotopy - ScienceDirect
Kneser's conjecture is proved, asserting that if all n-subsets of a (2n − k)-element set are divided into k + 1 classes, one of the classes contains two ...
[5]
[PDF] The chromatic number of Kneser graphs Chapter 38
In 1955 the number theorist Martin Kneser posed a seemingly innocuous problem that became one of the great challenges in graph theory until a bril-.
[6]
Kneser Graph -- from Wolfram MathWorld
The Kneser graphs are a class of graph introduced by Lovász (1978) to prove Kneser's conjecture. Given two positive integers n and k, the Kneser graph K(n,k), ...
[7]
[PDF] An introduction to graph theory - arXiv
Aug 2, 2023 · Let n and k be positive integers such that n ≥ k (k + 1) and k > 1. Recall (from Subsection 2.6.3) the Kneser graph KGn,k, whose vertices are ...
[8]
https://doi.org/10.1007/978-3-642-00856-6_38
[9]
Pushing disks apart - The Kneser-Poulsen conjecture in the plane
Aug 14, 2001 · We give a proof of the planar case of a longstanding conjecture of Kneser (1955) and Poulsen (1954).Missing: origin | Show results with:origin
[10]
[PDF] On the locating chromatic number of Kneser graphs - CORE
Aug 20, 2011 · KG(2k,k) is a matching and the smallest positive integer n for which KG(n,k) is connected, is n = 2k + 1. Kneser graphs. KG(2k + 1,k),k ≥ 3, are ...
[11]
[PDF] arXiv:0909.2770v2 [math.CO] 27 Sep 2010
Sep 27, 2010 · Note that KG(5, 2) is the famous Petersen graph. It was conjectured by Kneser in 1955 ( [7] ), and proved by Lovász in 1978 ( [8] ), that if ...
[12]
[PDF] Maximal degrees in subgraphs of Kneser graphs.
Apr 18, 2020 · Abstract. In this paper, we study the maximum degree in non-empty induced subgraphs of the. Kneser graph KG(n, k). One of the main results ...
[13]
[PDF] Hamiltonian Cycles in Kneser Graphs - UFRJ
On hamiltonian cycles in the prism over the odd graphs. J. Graph Theory (submitted). Chen, Y.-C. (2003). Triangle-free hamiltonian Kneser graphs. J. Combin ...
[14]
Self-Dual and LCD Codes from Kneser Graphs K(n, 2) and ... - MDPI
... the two corresponding subsets is empty. When k = 2 , the Kneser graph K(n, 2) is a strongly regular graph with parameters n 2 , n − 2 2 , n − 4 2 ...
[15]
[PDF] On the treewidth of generalized q-Kneser graphs - arXiv
May 19, 2024 · The Kneser graph Kq(n, k, k − 1) is the dual of the Grassmann graph ... Using projective geometry, the graph Kq(4, 2, 1) can be ...
[16]
Kneser graph | EPFL Graph Search
Kneser graphs are named after Martin Kneser, who first investigated them in 1956. The Kneser graph K(n, 1) is the complete graph on n vertices. The Kneser graph ...
[17]
[PDF] Fractional Graph Theory
The graph in Figure 4.1 (see exercise 5) is due to Isaacs [100]. The Kneser graphs show that the chromatic number and fractional chromatic number of a given.
[18]
Spectral Lower Bounds for the Quantum Chromatic Number of a Graph
Oct 16, 2019 · ... quantum chromatic number of various classes of graphs, which improves many known results. For example, we demonstrate that the Kneser graph ...
[19]
https://arxiv.org/abs/2511.12553
[20]
On the diameter of generalized Kneser graphs - ScienceDirect.com
Sep 28, 2008 · Recently, Valencia-Pabon and Vera [3] studied the diameter of Kneser graphs. ... Valencia-Pabon, J.-C. Vera. On the diameter of Kneser graphs.<|control11|><|separator|>
[21]
[2112.01884] On the diameter of Schrijver graphs - arXiv
Dec 3, 2021 · For k \geq 1 and n \geq 2k, the well known Kneser graph \operatorname{KG}(n,k) has all k-element subsets of an n-element set as vertices; two ...
[22]
Odd Graph -- from Wolfram MathWorld
The Kneser graph K(n,k) is a generalization of the odd graph, with O_n corresponding to K(2n-1,n-1) . The bipartite Kneser graph is a generalization of the ...
[23]
SOME ODD GRAPH THEORY - Biggs - 1979
SOME ODD GRAPH THEORY. Norman Biggs,. Norman Biggs. Royal Holloway College ... The Hamiltonian graphs O4 to O7. In Combinatorics. D. J. A. Welsh & D. R. ...
[24]
[PDF] Association Schemes - University of Waterloo
Jun 3, 2010 · These notes provide an introduction to association schemes, along with some related algebra. Their form and content has benefited from ...
[25]
[PDF] Resolving sets for Johnson and Kneser graphs - arXiv
Oct 24, 2012 · First, the Kneser graph K(n,2) is the complement of the correspond- ing Johnson graph J(n,2), and both graphs have diameter 2, so if dK(n,2) ...
[26]
[PDF] ON A PROBLEM BY SHAPOZENKO ON JOHNSON GRAPHS
Also, J(n, 2) is the complement of the Kneser graph K(n, 2), the graph which ... The graph J(n, m) is isomorphic (by com- plementation) to J(n, n − m) ...
[27]
[PDF] Products and Cayley Graphs - Clemson University
The complement of a Kneser graph is a Johnson graph. An example of a Johnson graph is the line graph L(Km), which for even m ≥ 6, is not Cayley. 9.3 ...
[28]
[PDF] Johnson graphs are panconnected - arXiv
Aug 18, 2019 · [3] Chartrand G, Hobbs A.M, Jung H.A, Kapoor S.F, Nash- Williams J.A, The square of a block is Hamiltonian-connected. J. Combin. Theory Ser ...<|separator|>
[29]
[PDF] Addressing Johnson graphs, complete multipartite ... - Princeton Math
the Johnson graph Jpn,1q is the complete graph Kn. When n “ 2, the Johnson graph. Jpn,2q is the line graph of Kn, also known as the triangular graph. Note ...
[30]
[PDF] A note on fall colorings of Kneser graphs
... [n], the Kneser graph KG(n,2) is exactly the complement graph of the line graph of Kn. Therefore, one can think of KG(n,2) as the graph whose vertex set is E ...Missing: K_n | Show results with:K_n
[31]
Treewidth of the Generalized Kneser Graphs
Mar 25, 2022 · The generalized Kneser graph K(n,k,t) K ( n , k , t ) is a graph whose vertices are the k k -subsets of a fixed n n -set, where two k k -subsets ...
[32]
Name for Kneser/Johnson-like graphs? - MathOverflow
Oct 26, 2013 · The special case s=0 gives the Kneser graphs, so the terminology generalized Kneser graphs is justified for G(n,k,≤s).
[33]
Extremal problems concerning Kneser graphs - ScienceDirect.com
Extremal problems concerning Kneser graphs. Author links open overlay panelP ... Lovasz, The chromatic number of Kneser hypergraphs, Transaction A.M.S., to appear ...
[34]
On semi-transitive orientability of Kneser graphs and their ...
A Kneser graph is vertex-transitive and edge-transitive, and these graphs are named after Martin Kneser, who first investigated them in 1955. There is a ...
[35]
[PDF] Hamiltonicity of Schrijver graphs and stable Kneser graphs
There is an algorithm for computing a Hamilton cycle in S(n, k, s) that takes time O(n) to compute the next vertex on the cycle. The initialization time and ...
[36]
On the chromatic number of some geometric type Kneser graphs
We estimate the chromatic number of graphs whose vertex set is the set of edges of a complete geometric graph on n points, and adjacency is defined in terms ...
[37]
The chromatic number of the Kneser graphs and the q-Kneser graphs
Jul 27, 2018 · ... chromatic number is $ n – 2k + 2$. This was shown by Lovasz in 1978. Nowadays many different proofs of the Kneser's conjecture are known.<|control11|><|separator|>
[38]
Quantum homomorphisms - ScienceDirect
Having defined quantum homomorphisms, it is natural to define quantum analogs of such graph ... . Quantum homomorphisms to Kneser graphs. Here we prove a ...
[39]
[1408.1288] On the stability of the Erdős-Ko-Rado theorem - arXiv
Aug 6, 2014 · Since an independent set in the Kneser graph is the same as a uniform intersecting family, this gives us a random analogue of the Erdős-Ko-Rado theorem.
[40]
[PDF] What is...Kneser's conjecture? Or: Coloring and topology
Kneser's conjecture (Aufgabe 360). χ(2k + d, k) = d + 2. Page 4. Proof that χ ... The first proof 23 years after Kneser stated the conjecture used the following.
[41]
Extremal G-free induced subgraphs of Kneser graphs - ScienceDirect
An extremal problem for two families of sets. European J. Combin., 3 (2) ... Stability results on vertex Turán problems in Kneser graphs. ArXiv preprints.
[42]
Machine learning and pure math, especially extremal combinatorics
Jul 22, 2025 · Machine learning and pure math, especially extremal combinatorics Presented by Jordan Ellenberg, University of Wisconsin-Madison ABSTRACT: ...Missing: set Kneser
[43]
[2307.09752] Neighbour-transitive codes in Kneser graphs - arXiv
Jul 19, 2023 · View a PDF of the paper titled Neighbour-transitive codes in Kneser graphs, by Dean Crnkovi\'c and 2 other authors. View PDF. Abstract:A code ...
[44]
https://doi.org/10.3390/math12233795
[45]
https://doi.org/10.1515/cmb-2022-0142