Random Kneser graphs and hypergraphs

zbMATH Open1409.05184arXiv1612.03868MaRDI QIDQ668022FDOQ668022

Authors: Andrey B. Kupavskii 

Publication date: 5 March 2019

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

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.

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

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

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

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)

Cites Work

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

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
• Sharp bounds for the chromatic number of random Kneser graphs
• Large cycles in random generalized Johnson 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)