The chromatic number of almost stable Kneser hypergraphs (Q543913): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
The Kneser hypergraph \(K^{r}(n,k)\) is an \(r\)-uniform hypergraph whose vertex set comprises all \(k\)-subsets of \([n]\), and hyperedges are \(r\)-tuples of disjoint subsets. \textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] answered in the affirmative a long-standing Kneser conjecture that \(\chi (K^{2}(n,k))=n-2k+2.\) Later, this result was generalized by showing \(\chi (K^{r}(n,k))=\left\lceil \frac{ n-k(-1)r}{r-1}\right\rceil \). A subset \(S\subset [ n]\) is called \(2\)-stable if for any \(i,j\in S\), \(\left| i-j\right| \geq 2.\) It is proved in the paper that for \(p\) prime and \(n\geq kp,\) the chromatic number of the subgraph of \(K^{p}(n,k)\) induced by \(2\)-stable sets equals \(\chi (K^{r}(n,k)).\) | |||
Property / review text: The Kneser hypergraph \(K^{r}(n,k)\) is an \(r\)-uniform hypergraph whose vertex set comprises all \(k\)-subsets of \([n]\), and hyperedges are \(r\)-tuples of disjoint subsets. \textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] answered in the affirmative a long-standing Kneser conjecture that \(\chi (K^{2}(n,k))=n-2k+2.\) Later, this result was generalized by showing \(\chi (K^{r}(n,k))=\left\lceil \frac{ n-k(-1)r}{r-1}\right\rceil \). A subset \(S\subset [ n]\) is called \(2\)-stable if for any \(i,j\in S\), \(\left| i-j\right| \geq 2.\) It is proved in the paper that for \(p\) prime and \(n\geq kp,\) the chromatic number of the subgraph of \(K^{p}(n,k)\) induced by \(2\)-stable sets equals \(\chi (K^{r}(n,k)).\) / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C65 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5909625 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
chromatic number | |||
Property / zbMATH Keywords: chromatic number / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
combinatorial topology | |||
Property / zbMATH Keywords: combinatorial topology / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
stable Kneser hypergraphs | |||
Property / zbMATH Keywords: stable Kneser hypergraphs / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(Z_{p}\)-Tucker lemma | |||
Property / zbMATH Keywords: \(Z_{p}\)-Tucker lemma / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Peter Horák / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2046584470 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0912.4748 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Stable Kneser hypergraphs and ideals in $\mathbb {N}$ with the Nikodým property / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Chromatic Number of Kneser Hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Neighborhood complexes of stable Kneser graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Simple proofs of some Borsuk-Ulam results / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4134005 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial Stokes formulas via minimal resolutions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Kneser's conjecture, chromatic number, and homotopy / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A combinatorical proof of Kneser's conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial Stokes formulae / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3869375 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5837940 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalized Kneser coloring theorems with combinatorial proofs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 05:11, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The chromatic number of almost stable Kneser hypergraphs |
scientific article |
Statements
The chromatic number of almost stable Kneser hypergraphs (English)
0 references
17 June 2011
0 references
The Kneser hypergraph \(K^{r}(n,k)\) is an \(r\)-uniform hypergraph whose vertex set comprises all \(k\)-subsets of \([n]\), and hyperedges are \(r\)-tuples of disjoint subsets. \textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] answered in the affirmative a long-standing Kneser conjecture that \(\chi (K^{2}(n,k))=n-2k+2.\) Later, this result was generalized by showing \(\chi (K^{r}(n,k))=\left\lceil \frac{ n-k(-1)r}{r-1}\right\rceil \). A subset \(S\subset [ n]\) is called \(2\)-stable if for any \(i,j\in S\), \(\left| i-j\right| \geq 2.\) It is proved in the paper that for \(p\) prime and \(n\geq kp,\) the chromatic number of the subgraph of \(K^{p}(n,k)\) induced by \(2\)-stable sets equals \(\chi (K^{r}(n,k)).\)
0 references
chromatic number
0 references
combinatorial topology
0 references
stable Kneser hypergraphs
0 references
\(Z_{p}\)-Tucker lemma
0 references