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 numberrandom Kneser graphstransference

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) 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

• 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
• 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?)
• 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
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• 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 almost stable Kneser hypergraphs
• The Chromatic Number of 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

(20)

• A new lower bound for the chromatic number of general Kneser hypergraphs
• Large cycles in random generalized Johnson graphs
• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• Choice number of Kneser 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 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 the chromatic numbers of random hypergraphs
• Chromatic numbers of Kneser-type graphs
• On the chromatic number of random subgraphs of a certain distance graph
• On random subgraphs of Kneser and Schrijver graphs
• Characterization of randomly k-dimensional graphs.
• On two limit values of the chromatic number of a random hypergraph
• Two values of the chromatic number of a sparse random graph
• Sharp bounds for the chromatic number of random Kneser graphs
• Johnson graphs, their random subgraphs, and some of their extremal characteristics
• Stability of the independence number of G(n,r,1) graphs

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)