Diameters of random distance graphs
The theme of this paper is the diameter of a random subgraph of a certain class of disctance graphs. In the class that is considered, the vertices are \(n\)-tuples of 0,1 with \(r_n\) 1s and any two of them are joined by an edge if they have exactly \(s_n\) 1s in common. So when \(s_n=0\), such a graph represents a Kneser graph. Then a random subgraph is considered by retaining each edge independently with probability \(p_n\). The first theorem considers the property that the diameter of this random graph is at most 2. It turns out that there is a critical probability for this property. In fact, this is a sharp threshold. This holds under the assumption that \(r_n \ll n^{1/3}\) and also \(r_n >2s_n\). For \(s_n=r_n/2\) and \(r_n \geq f(n) + f_n\) for a certain function \(f(n)\) that is explicitly given in the paper and \(f_n\to \infty\), they show the existence of such a critical probability for having diameter at most 2. For \(r_n \leq f(n) - f_n\), then no such non-trivial threshold exists. For any \(p_n < c<1\), where \(c\) is a constant, the diameter is with high probability (as \(n\) grows) greater than 2.
- Around Borsuk's hypothesis
- Borsuk's problem and the chromatic numbers of some metric spaces
- Codes with forbidden distances
- Coloring distance graphs and graphs of diameters
- Coloring some finite sets in R^n
- Excursions into combinatorial geometry
- 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 51916 (Why is no real title available?)
- scientific article; zbMATH DE number 3458659 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1017008 (Why is no real title available?)
- scientific article; zbMATH DE number 1943977 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (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
- On the chromatic numbers of spheres in \(\mathbb R^n\)
- On the chromatic numbers of spheres in Euclidean spaces
- On the Ramsey numbers for complete distance graphs with vertices in \( \{0,1\}^n\)
- On the stability of the Erdős-Ko-Rado theorem
- Pseudo-random graphs
- Random graphs.
- Random graphs: models and asymptotic characteristics
- The Mathematical Coloring Book
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Three lectures on the Borsuk partition problem
- 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
- Stretch and diameter in random geometric graphs
- Clustering coefficient of a spatial preferential attachment model
- Diameter, connectivity, and phase transition of the uniform random intersection graph
- Distance distribution of nodes in star graphs
- Graph diameter in long-range percolation
- The diameter of a random subgraph of the hypercube
- On the diameter of a class of random graphs
- Almost Every Randomly Near-Traceable Graph has Diameter at Most Two
- Metric dimension for random graphs
- On distribution function of the diameter in uncertain graph
- Distances in random graphs with finite variance degrees
- The diameter of sparse random graphs
- Diameters of uniform subset graphs
This page was built for publication: Diameters of random distance graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1687985)
