Random Kneser graphs and hypergraphs

MaRDI QIDQ668022zbMATH OpenFDO

Authors Andrey B. Kupavskii

Publication date 5 March 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.03868, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p52

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic numbertransferencerandom Kneser graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The Kneser graph $K{G}_{n,k}$ is the graph whose vertices are the $k$-element subsets of $[n],$ with two vertices adjacent if and only if the corresponding sets are disjoint. A famous result due to Lov'asz states that the chromatic number of $K{G}_{n,k}$ is equal to $n-2k+2$. In this paper we discuss the chromatic number of random Kneser graphs and hypergraphs. It was studied in two recent papers, one due to Kupavskii, who proposed the problem and studied the graph case, and the more recent one due to Alishahi and Hajiabolhassan. The authors of the latter paper had extended the result of Kupavskii to the case of general Kneser hypergraphs. Moreover, they have improved the bounds of Kupavskii in the graph case for many values of parameters. In the present paper we present a purely combinatorial approach to the problem based on blow-ups of graphs, which gives much better bounds on the chromatic number of random Kneser and Schrijver graphs and Kneser hypergraphs. This allows us to improve all known results on the topic. The most interesting improvements are obtained in the case of $r$-uniform Kneser hypergraphs with $rge3$, where we managed to replace certain polynomial dependencies of the parameters by the logarithmic ones.

Recommendations

• Chromatic number of random Kneser hypergraphs
• Sharp bounds for the chromatic number of random Kneser graphs
• On random subgraphs of Kneser and Schrijver graphs
• On the chromatic number of a random subgraph of the Kneser graph
• Estimating the \(r\)-colorability threshold for a random hypergraph
• On the chromatic number of a random hypergraph
• On the random version of the Erdős matching conjecture
• The chromatic number of almost stable Kneser hypergraphs
• scientific article; zbMATH DE number 1380583

Cites work

• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• A short proof of Kneser's conjecture
• Chromatic number of random Kneser hypergraphs
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Families with no matchings of size s
• Families with no s pairwise disjoint sets
• Generalized Kneser coloring theorems with combinatorial proofs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Improved bounds for Erdős' matching conjecture
• Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Kneser's conjecture, chromatic number, and homotopy
• On ``stability in the Erdős-Ko-Rado theorem
• On chromatic numbers of nearly Kneser distance graphs
• On random subgraphs of Kneser and Schrijver graphs
• On random subgraphs of Kneser graphs and their generalizations
• On the chromatic number of Kneser hypergraphs
• On the stability of some Erdős-Ko-Rado type results
• On the stability of the Erdős-Ko-Rado theorem
• On the stability of the independence number of a random subgraph
• Random graphs.
• Removal and stability for Erdős-Ko-Rado
• Sharp bounds for the chromatic number of random Kneser graphs
• Stable Kneser hypergraphs and ideals in $\mathbb {N}$ with the Nikodým property
• The Chromatic Number of Kneser Hypergraphs
• The chromatic number of almost stable Kneser hypergraphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Transference for the Erdős-Ko-Rado theorem
• 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

(18)

• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• On random subgraphs of Kneser and Schrijver graphs
• Chromatic numbers of Kneser-type graphs
• Exact modularity of line graphs of complete graphs
• On the chromatic number of random subgraphs of a certain distance graph
• On the chromatic numbers of random hypergraphs
• Characterization of randomly \(k\)-dimensional graphs.
• Sharp bounds for the chromatic number of random Kneser graphs
• Estimating the \(r\)-colorability threshold for a random hypergraph
• A generalization of Kneser graphs
• On two limit values of the chromatic number of a random hypergraph
• On the independence number and the chromatic number of generalized preferential attachment models
• Two values of the chromatic number of a sparse random graph
• Choice number of Kneser graphs
• Large cycles in random generalized Johnson graphs
• Sharp bounds for the chromatic number of random Kneser graphs
• New lower bound on the modularity of Johnson graphs
• A new lower bound for the chromatic number of general Kneser hypergraphs

This page was built for publication: Random Kneser graphs and hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q668022)