On stability of the independence number of a certain distance graph

DOI10.1134/S0032946020040055MaRDI QIDQ2229578zbMATH OpenOpenAlexFDO

Authors P. A. Ogarok, Andrei M. Raigorodskii

Publication date 18 February 2021

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0032946020040055

zbMATH Keywords

distance graphindependence numberrandom graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Independence numbers of random subgraphs of a distance graph
• Independence numbers of random subgraphs of distance graphs
• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• On threshold probability for the stability of independent sets in distance graphs
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)

Cites work

• A generalization of Kneser graphs
• A remark on lower bounds for the chromatic numbers of spaces of small dimension with metrics _1 and _2
• A simple removal lemma for large nearly-intersecting families
• Chromatic number of random Kneser hypergraphs
• Clique chromatic numbers of intersection graphs
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• Counterexamples to Borsuk's conjecture with large girth
• Degree versions of theorems on intersecting families via stability
• Estimate of the number of edges in special subgraphs of a distance graph
• Excursions into combinatorial geometry
• Extremal problems in hypergraph colourings
• scientific article; zbMATH DE number 6536189 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 1943977 (Why is no real title available?)
• Modularity of some distance graphs
• New bounds on clique-chromatic numbers of Johnson graphs
• On ``stability in the Erdős-Ko-Rado theorem
• On a Frankl-Wilson theorem
• On random subgraphs of Kneser graphs and their generalizations
• On the chromatic number of random subgraphs of a certain distance graph
• On the independence numbers of distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• On the size of K-cross-free families
• On the stability of the Erdős-Ko-Rado theorem
• On threshold probability for the stability of independent sets in distance graphs
• Partition-free families of sets
• Ramsey theory in the \(n\)-space with Chebyshev metric
• Regular intersecting families
• Removal and stability for Erdős-Ko-Rado
• The number of edges in induced subgraphs of some distance graphs
• Transference for the Erdős-Ko-Rado theorem
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman

Cited in

(10)

• On the stability of the independence number of a random subgraph
• Large cycles in random generalized Johnson graphs
• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• On the minimal number of edges in induced subgraphs of special distance graphs
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)
• On threshold probability for the stability of independent sets in distance graphs
• On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• Phase transition in random distance graphs on the torus
• Lower bound on the minimum number of edges in subgraphs of Johnson graphs
• Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph

This page was built for publication: On stability of the independence number of a certain distance graph

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