Second-order moments of the size of randomly induced subgraphs of given order

DOI10.1016/J.DAM.2024.04.025arXiv2304.11423MaRDI QIDQ6433968FDOQ6433968

Authors: Nicola Apollonio 

Publication date: 22 April 2023

Abstract: For a graph $G$ and a positive integer $c$, let $M_c(G)$ be the size of a subgraph of $G$ induced by a randomly sampled subset of $c$ vertices. Second-order moments of $M_c(G)$ encode part of the structure of $G$. We use this fact, coupled to classical moment inequalities, to prove graph theoretical results, to give combinatorial identities, to bound the size of the $c$-densest subgraph from below and the size of the $c$-sparsest subgraph from above, and to provide bounds for approximate enumeration of trivial subgraphs.

Recommendations

• scientific article; zbMATH DE number 850234
• On Subgraph Sizes in Random Graphs
• Largest sparse subgraphs of random graphs
• On the sizes of large subgraphs of the binomial random graph
• Maximum sparse induced subgraphs of the binomial random graph with given number of edges

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12)

This page was built for publication: Second-order moments of the size of randomly induced subgraphs of given order

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