On the sizes of large subgraphs of the binomial random graph

DOI10.1016/J.DISC.2021.112675MaRDI QIDQ2666567zbMATH OpenOpenAlexFDO

Authors József Balogh, M. E. Zhukovskii

Publication date 23 November 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphslarge subgraphsrandom graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Abstract: We consider the binomial random graph $G(n,p)$, where $p$ is a constant, and answer the following two questions. First, given $e(k)=pkchoose2+O(k)$, what is the maximum $k$ such that a.a.s.~the binomial random graph $G(n,p)$ has an induced subgraph with $k$ vertices and $e(k)$ edges? We prove that this maximum is not concentrated in any finite set (in contrast to the case of a small $e(k)$). Moreover, for every constant $C>0$ and every $omeg{a}_{n}oinfty$, a.a.s.~the size of the concentration set belongs to $(Csqrtn/lnn,omeg{a}_{n}sqrtn/lnn)$. Second, given $k>varepsilonn$, what is the maximum $mu$ such that a.a.s.~the set of sizes of $k$-vertex subgraphs of $G(n,p)$ contains a full interval of length $mu$? The answer is $mu=Thetaleft(sqrt(n-k)nlnnchoosekight)$.

Recommendations

• On Subgraph Sizes in Random Graphs
• A large deviation result on the number of small subgraphs of a random graph
• On random k-out subgraphs of large graphs
• On extremal subgraphs of random graphs
• scientific article; zbMATH DE number 3333197
• On random subgraphs of Kneser and Schrijver graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• On the number of subgraphs of the Barabási-Albert random graph
• The size of a maximum subgraph of the random graph with a given number of edges

Cites work

• Asymptotic enumeration of graphs with given degree sequence
• Cliques in random graphs
• Degree sequences of random graphs
• scientific article; zbMATH DE number 3943864 (Why is no real title available?)
• scientific article; zbMATH DE number 4087713 (Why is no real title available?)
• scientific article; zbMATH DE number 125455 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• Induced subgraphs with distinct sizes
• Largest sparse subgraphs of random graphs
• On induced paths, holes and trees in random graphs
• On the probability of independent sets in random graphs
• On the stability of the independence number of a random subgraph
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Some recent problems and results in graph theory
• The distribution of the maximum degree of a random graph
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Trees in random graphs

Cited in

(11)

• Towards the distribution of the size of a largest planar matching and largest planar subgraph in random bipartite graphs
• The size of the largest bipartite subgraphs
• Maximum sparse induced subgraphs of the binomial random graph with given number of edges
• The size of a maximum subgraph of the random graph with a given number of edges
• On Subgraph Sizes in Random Graphs
• scientific article; zbMATH DE number 867706 (Why is no real title available?)
• Second-order moments of the size of randomly induced subgraphs of given order
• Maximum induced trees in sparse random graphs
• Maximum induced subgraphs of the binomial random graph
• On the sizes of k-subgraphs of the binomial random graph
• Maximum induced trees and forests of bounded degree in random graphs

This page was built for publication: On the sizes of large subgraphs of the binomial random graph

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