Small subgraphs and their extensions in a random distance graph

DOI10.1070/SM8674MaRDI QIDQ4568577zbMATH OpenOpenAlexFDO

Authors A. V. Burkin, M. E. Zhukovskii

Publication date 22 June 2018

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

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

zbMATH Keywords

random graphthreshold functiondistance graphsmall subgraphsextension properties

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Distance in graphs (05C12)

Abstract: In previous papers, threshold probabilities for the properties of a random distance graph to contain strictly balanced graphs were found. We extend this result to arbitrary graphs and prove that the number of copies of a strictly balanced graph has asymptotically Poisson distribution at the threshold.

Recommendations

• Small subgraphs in random distance graphs
• On the probability of the occurrence of a copy of a fixed graph in a random distance graph
• scientific article; zbMATH DE number 747034
• scientific article; zbMATH DE number 3168330
• scientific article; zbMATH DE number 3865331

Cites work

• scientific article; zbMATH DE number 5935733 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4041966 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A counterexample to Borsuk’s conjecture
• A weak zero-one law for sequences of random distance graphs
• Borsuk's problem and the chromatic numbers of some metric spaces
• Intersection theorems with geometric consequences
• On a sequence of random distance graphs subject to the zero-one law
• On the probability of the occurrence of a copy of a fixed graph in a random distance graph
• Random graphs.
• Random graphs.
• Random graphs: models and asymptotic characteristics
• Research Problems in Discrete Geometry
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Threshold functions for extension statements
• Threshold functions for small subgraphs
• Zero-one law for random distance graphs with vertices in \(\{-1,0,1\}^n\)
• Гигантская компонента в случайных дистанционных графах специального вида

Cited in

(7)

• Zero-one laws for sentences with \(k\) variables
• Large cycles in generalized Johnson graphs
• On the probability of the occurrence of a copy of a fixed graph in a random distance graph
• Small subgraphs in random distance graphs
• Large cycles in random generalized Johnson graphs
• The median of the number of simple paths on three vertices in the random graph
• Small Submatroids in Random Matroids

This page was built for publication: Small subgraphs and their extensions in a random distance graph

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