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

DOI10.1016/J.DAM.2024.04.025MaRDI QIDQ6433968zbMATH OpenFDO

Authors Nicola Apollonio

Publication date 22 April 2023

Mathematics Subject Classification ID

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

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

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)