On random subgraphs of Kneser and Schrijver graphs

DOI10.1016/J.JCTA.2016.02.003MaRDI QIDQ272313zbMATH OpenOpenAlexFDO

Authors Andrey B. Kupavskii

Publication date 20 April 2016

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.00699

zbMATH Keywords

chromatic numberKneser graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: A Kneser graph $K{G}_{n,k}$ is a graph whose vertices are in one-to-one correspondence with $k$-element subsets of $[n],$ with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lov'asz states that the chromatic number of a Kneser graph $K{G}_{n,k}$ is equal to $n-2k+2$. In this paper we study the chromatic number of a random subgraph of a Kneser graph $K{G}_{n,k}$ as $n$ grows. A random subgraph $K{G}_{n,k}(p)$ is obtained by including each edge of $K{G}_{n,k}$ with probability $p$. For a wide range of parameters $k=k(n),p=p(n)$ we show that $chi(K{G}_{n,k}(p))$ is very close to $chi(K{G}_{n,k}),$ a.a.s. differing by at most 4 in many cases. Moreover, we obtain the same bounds on the chromatic numbers for the so-called Schrijver graphs, which are known to be vertex-critical induced subgraphs of Kneser graphs.

Recommendations

• Sharp bounds for the chromatic number of random Kneser graphs
• Random Kneser graphs and hypergraphs
• Chromatic numbers of Kneser-type graphs
• Chromatic number of random Kneser hypergraphs
• On the chromatic number of the general Kneser-graph

Cites work

• A New Short Proof of Kneser's Conjecture
• A short proof of Kneser's conjecture
• Extremal results in random graphs
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 3768498 (Why is no real title available?)
• 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 the stability of the Erdős-Ko-Rado theorem
• Random graphs.
• 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

(35)

• A generating function approach to random subgraphs of the \(n\)-cycle
• On a bound in extremal combinatorics
• Chromatic number of random Kneser hypergraphs
• Kneser ranks of random graphs and minimum difference representations
• On the stability of the independence number of a random subgraph
• On the random version of the Erdős matching conjecture
• Random subgraphs of certain graph powers
• Large cycles in random generalized Johnson graphs
• Choice number of Kneser graphs
• Sharp bounds for the chromatic number of random Kneser graphs
• Estimating the r-colorability threshold for a random hypergraph
• Independence numbers of random subgraphs of some distance graph
• A generalization of Kneser graphs
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)
• On the Hadwiger number of Kneser graphs and their random subgraphs
• On threshold probability for the stability of independent sets in distance graphs
• Clique numbers of random subgraphs of some distance graphs
• On the chromatic number of random subgraphs of a certain distance graph
• New upper bound for the chromatic number of a random subgraph of a distance graph
• On the sizes of large subgraphs of the binomial random graph
• scientific article; zbMATH DE number 4110728 (Why is no real title available?)
• Random subgraphs in Cartesian powers of regular graphs
• Kneser ranks of random graphs and minimum difference representations
• Kneser graphs are like Swiss cheese
• The distributions of the numbers of finite subgraphs in random nonhomogeneous hypergraphs
• scientific article; zbMATH DE number 6327467 (Why is no real title available?)
• scientific article; zbMATH DE number 3333197 (Why is no real title available?)
• On subgraphs with degrees of prescribed residues in the random graph
• Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
• Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
• Trivial colors in colorings of Kneser graphs
• Sharp bounds for the chromatic number of random Kneser graphs
• Random Kneser graphs and hypergraphs
• On the chromatic number of a random subgraph of the Kneser graph
• Johnson graphs, their random subgraphs, and some of their extremal characteristics

This page was built for publication: On random subgraphs of Kneser and Schrijver graphs

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