Independence numbers and chromatic numbers of the random subgraphs of some distance graphs

DOI10.1070/SM2015v206n10ABEH004498zbMath1331.05191MaRDI QIDQ3466410

A. S. Gusev, L. I. Bogolubsky, M. M. Pyaderkin, Andrei M. Raigorodskii

Publication date: 1 February 2016

Published in: Sbornik: Mathematics (Search for Journal in Brave)

zbMATH Keywords

asymptotic behaviorEuclidean spaceindependence numberchromatic numberdistance graphrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10)

Related Items

On the chromatic numbers of low-dimensional spaces, On random subgraphs of Kneser and Schrijver graphs, Sharp bounds for the chromatic number of random Kneser graphs, Chromatic number of random Kneser hypergraphs, On the stability of the Erdős-Ko-Rado theorem, Diameters of random distance graphs, Sharp threshold for the Erdős–Ko–Rado theorem, Chromatic numbers of some distance graphs, Estimate of the number of edges in special subgraphs of a distance graph, On the stability of the independence number of a random subgraph, On the random version of the Erdős matching conjecture, Random Kneser graphs and hypergraphs, On the stability of some Erdős-Ko-Rado type results, On the chromatic number of a random subgraph of the Kneser graph, On random subgraphs of Kneser graphs and their generalizations, On the chromatic number of random subgraphs of a certain distance graph, Degree versions of theorems on intersecting families via stability, Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improvement of the Frankl-Wilson theorem on the number of edges in a hypergraph with forbidden intersections of edges
• On the chromatic numbers of spheres in \(\mathbb R^n\)
• Borsuk's problem for \((0,1)\)-polytopes and cross-polytopes
• The problem of Borsuk, Hadwiger,and Grünbaum for some classes of polytopes and graphs
• On a packing and covering problem
• Intersection theorems with geometric consequences
• A note on the realization of distances within sets in euclidean space
• New estimates in the problem of the number of edges in a hypergraph with forbidden intersections
• Counterexamples to Borsuk's conjecture on spheres of small radii
• On independence numbers of distance graphs with vertices in \(\{-1,0,1\}^n\): estimates, conjectures, and applications to the Nelson-Erdős-hadwiger problem and the borsuk problem
• Around Borsuk's hypothesis
• Coloring Distance Graphs and Graphs of Diameters
• Coloring some finite sets in {R}^{n}
• Erdös–Ko–Rado Theorem—22 Years Later
• Research Problems in Discrete Geometry
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The Mathematical Coloring Book
• Cliques in random graphs
• The realization of distances within sets in Euclidean space
• The chromatic number of random graphs
• The chromatic number of random graphs