On the sizes of large subgraphs of the binomial random graph |
| |
Affiliation: | 1. Department of Mathematical Sciences, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA;2. Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprodny, Moscow Region, 141701, Russian Federation;3. Adyghe State University, Caucasus Mathematical Center, ul. Pervomayskaya, 208, Maykop, Republic of Adygea, 385000, Russian Federation;4. The Russian Presidential Academy of National Economy and Public Administration, Prospect Vernadskogo, 84, bldg 2, Moscow, 119571, Russian Federation;5. Moscow Center for Fundamental and Applied Mathematics, Russian Federation |
| |
Abstract: | We consider the binomial random graph , where p is a constant, and answer the following two questions.First, given , what is the maximum k such that a.a.s. the binomial random graph has an induced subgraph with k vertices and edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small ). Moreover, for every constant , with probability bounded away from 0, the size of the concentration set is bigger than , and, for every , a.a.s. it is smaller than .Second, given , what is the maximum μ such that a.a.s. the set of sizes of k-vertex subgraphs of contains a full interval of length μ? The answer is . |
| |
Keywords: | Random graph Induced subgraphs Large subgraphs |
本文献已被 ScienceDirect 等数据库收录! |
|