Edge-statistics on large graphs

DOI10.1017/S0963548319000294MaRDI QIDQ4993086zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon, Dan Hefetz, Michael Krivelevich, Mykhaylo Tyomkyn

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Brun's sieveinducibility of a graphSperner's theoremZykov's symmetrization

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The inducibility of a graph $H$ measures the maximum number of induced copies of $H$ a large graph $G$ can have. Generalizing this notion, we study how many induced subgraphs of fixed order $k$ and size $ell$ a large graph $G$ on $n$ vertices can have. Clearly, this number is $$ for every $n$, $k$ and $$. We conjecture that for every $n$, $k$ and $$ this number is at most $$. If true, this would be tight for $ellin1,k-1$. In support of our `Edge-statistics conjecture' we prove that the corresponding density is bounded away from $1$ by an absolute constant. Furthermore, for various ranges of the values of $ell$ we establish stronger bounds. In particular, we prove that for `almost all' pairs $(k,ell)$ only a polynomially small fraction of the $k$-subsets of $V(G)$ has exactly $ell$ edges, and prove an upper bound of $$ for $ell=1$. Our proof methods involve probabilistic tools, such as anti-concentration results relying on fourth moment estimates and Brun's sieve, as well as graph-theoretic and combinatorial arguments such as Zykov's symmetrization, Sperner's theorem and various counting techniques.

Recommendations

• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• A completion of the proof of the Edge-statistics Conjecture
• On the exact maximum induced density of almost all graphs and their inducibility
• Anticoncentration for subgraph statistics
• Sizes of graphs with induced subgraphs of large maximum degree

Cites work

• A bound on the inducibility of cycles
• A completion of the proof of the Edge-statistics Conjecture
• Algorithms with large domination ratio
• Anticoncentration for subgraph statistics
• Graphs with maximal number of adjacent pairs of edges
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On a lemma of Littlewood and Offord
• On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
• On the exact maximum induced density of almost all graphs and their inducibility
• On the inducibility of cycles
• The dual BKR inequality and Rudich's conjecture
• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• The inducibility of complete bipartite graphs
• The inducibility of graphs
• The probabilistic method

Cited in

(15)

• Maximum density of vertex-induced perfect cycles and paths in the hypercube
• The feasible region of induced graphs
• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• The inducibility of complete bipartite graphs
• scientific article; zbMATH DE number 1877027 (Why is no real title available?)
• Combinatorial anti-concentration inequalities, with applications
• Anticoncentration for subgraph statistics
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• Inducibility in the hypercube
• Inducibility in H-free graphs and inducibility of Turán graphs
• Unique subgraphs are rare
• The edge-statistics conjecture for hypergraphs
• Resolution of the quadratic Littlewood-Offord problem
• Some exact inducibility-type results for graphs via flag algebras

This page was built for publication: Edge-statistics on large graphs

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