Abstract:
Consider $\mathcal{E}(G, k)$ – the set of all sizes (numbers of edges) of induced subgraphs of size $k$ in a given graph $G$ with $n$ vertices. For the binomial random graph $G = G(n, p)$, we proved that, for each $\alpha> 0$ and $\varepsilon$ small enough, the set $\mathcal{E}(G, k)$ with high probability contains a large segment for all $k$ such that $(\ln n)^{1+\alpha}<k<\varepsilon n$. We also found the asymptotic length of this segment.
Keywords:binomial random graph, sizes of induced subgraphs of the random graph.
UDC:517.54
Presented:V. V. Kozlov Received: 14.02.2025 Revised: 06.04.2025 Accepted: 21.04.2025
