Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
From MaRDI portal
Publication:2422241
Abstract: We suggest a new method on coloring generalized Kneser graphs based on hypergraphs with high discrepancy and small number of edges. The main result is providing a proper coloring of K(n, n/2-t, s) in (4 + o(1))(s + t)^2 colors, which is produced by Hadamard matrices. Also, we show that for colorings by independent set of a natural type, this result is the best possible up to a multiplicative constant. Our method extends to Kneser hypergraphs as well.
Recommendations
- On generalized Kneser hypergraph colorings
- Hypergraphs with many Kneser colorings
- Kneser colorings of uniform hypergraphs
- On the chromatic number of generalized Kneser hypergraphs
- On the chromatic number of general Kneser hypergraphs
- A new coloring theorem of Kneser graphs
- On the chromatic number of Kneser hypergraphs
- On total and edge coloring some Kneser graphs
- Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
- Colorful subhypergraphs in Kneser hypergraphs
Cites work
- A combinatorical proof of Kneser's conjecture
- Clique chromatic numbers of intersection graphs
- Combinatorial algebraic topology
- Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
- Extremal problems concerning Kneser-graphs
- Families of vectors without antipodal pairs
- Generalized Kneser coloring theorems with combinatorial proofs
- Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
- Intersection theorems with geometric consequences
- Kneser's conjecture, chromatic number, and homotopy
- On chromatic numbers of close-to-Kneser distance graphs
- On the chromatic number of Kneser hypergraphs
- On the chromatic number of the general Kneser-graph
- On the diameter of generalized Kneser graphs
- On the girth and diameter of generalized Johnson graphs
- On the ratio of optimal integral and fractional covers
- Six Standard Deviations Suffice
- The Chromatic Number of Kneser Hypergraphs
- The complete intersection theorem for systems of finite sets
- The probabilistic method
- 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
Cited in
(33)- Lower bounds on the clique-chromatic numbers of some distance graphs
- New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\)
- Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
- Estimate of the number of edges in special subgraphs of a distance graph
- A generalization of Kneser graphs
- The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
- New bounds on clique-chromatic numbers of Johnson graphs
- 2-colorings of hypergraphs with large girth
- On the independence number and the chromatic number of generalized preferential attachment models
- Exact modularity of line graphs of complete graphs
- New lower bound on the modularity of Johnson graphs
- On stability of the independence number of a certain distance graph
- Modularity of some distance graphs
- New bounds for the clique-chromatic numbers of Johnson graphs
- On the chromatic number of generalized Kneser graphs and Hadamard matrices
- Exact distance graphs of product graphs
- Chromatic numbers of Kneser-type graphs
- On the independence numbers of distance graphs with vertices in \(\{-1, 0, 1\}^n\)
- On the chromatic number of generalized Kneser hypergraphs
- Geodetic convexity and Kneser graphs
- On two limit values of the chromatic number of a random hypergraph
- Extremal problems in hypergraph colourings
- Systems of representatives
- Large cycles in generalized Johnson graphs
- On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme
- Lower bound on the minimum number of edges in subgraphs of Johnson graphs
- Trivial colors in colorings of Kneser graphs
- Kneser graphs are Hamiltonian
- Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph
- Johnson graphs, their random subgraphs, and some of their extremal characteristics
- One property of the multiple Rademacher system and its applications to problems of graph discrepancy
- Kneser graphs are Hamiltonian
- Stability of the independence number of G(n,r,1) graphs
This page was built for publication: Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2422241)
