Abstract:
The distance graph $G(n,2,1)$ is a graph where vertices are identified with twoelement subsets of $\{1,2,\dots,n\}$, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph $G_p(n,2,1)$ in the Erdős–Rényi model is obtained by selecting each edge of $G(n,2,1)$ with probability p independently of other edges. We find a lower bound on the independence number of the random subgraph $G_{1/2}(n,2,1)$.
Citation:
N. M. Derevyanko, S. G. Kiselev, “Independence numbers of random subgraphs of some distance graph”, Probl. Peredachi Inf., 53:4 (2017), 3–15; Problems Inform. Transmission, 53:4 (2017), 307–318
This publication is cited in the following 9 articles:
J. C. Buitrago Oropeza, “Maximum Induced Trees in Sparse Random Graphs”, Dokl. Math., 109:2 (2024), 167
A. M. Raigorodskii, V. S. Karas, “Asymptotics of the Independence Number of a Random Subgraph of the Graph $G(n,r,<s)$”, Math. Notes, 111:1 (2022), 124–131
V. S. Karas, P. A. Ogarok, A. M. Raigorodskii, “Asymptotics of the independence number of a random subgraph of the graph $G(n,r,<s)$”, Dokl. Math., 104:1 (2021), 173–174
Dmitry Kamaldinov, Arkadiy Skorkin, Maksim Zhukovskii, “Maximum sparse induced subgraphs of the binomial random graph with given number of edges”, Discrete Mathematics, 344:2 (2021), 112205
M. M. Pyaderkin, “On Threshold Probability for the Stability of Independent Sets in Distance Graphs”, Math. Notes, 106:2 (2019), 274–285
A. Kupayskii, “Degree versions of theorems on intersecting families via stability”, J. Comb. Theory Ser. A, 168 (2019), 272–287
N. M. Derevyanko, M. E. Zhukovskii, M. Rassias, A. Yu. Skorkin, “The size of a maximum subgraph of the random graph with a given number of edges”, Dokl. Math., 100:2 (2019), 478–479
M. M. Pyaderkin, “On the chromatic number of random subgraphs of a certain distance graph”, Discret Appl. Math., 267 (2019), 209–214
S. Kiselev, A. Kupavskii, “Sharp bounds for the chromatic number of random kneser graphs”, Acta Math. Univ. Comen., 88:3 (2019), 861–865