Anticoncentration for subgraph statistics

DOI10.1112/JLMS.12192MaRDI QIDQ4967964zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 11 July 2019

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey-type arguments

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Consider integers $k,ell$ such that $$. Given a large graph $G$, what is the fraction of $k$-vertex subsets of $G$ which span exactly $ell$ edges? When $G$ is empty or complete, and $ell$ is zero or $$, this fraction can be exactly 1. On the other hand, if $ell$ is far from these extreme values, one might expect that this fraction is substantially smaller than 1. This was recently proved by Alon, Hefetz, Krivelevich and Tyomkyn who intiated the systematic study of this question and proposed several natural conjectures. Let $$. Our main result is that for any $k$ and $ell$, the fraction of $k$-vertex subsets that span $ell$ edges is at most $lo{g}^{Oleft(1ight)}left(el{l}^{\ast }/kight)sqrtk/el{l}^{\ast }$, which is best-possible up to the logarithmic factor. This improves on multiple results of Alon, Hefetz, Krivelevich and Tyomkyn, and resolves one of their conjectures. In addition, we also make some first steps towards some analogous questions for hypergraphs. Our proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anticoncentration inequalities, hypercontractivity, and a coupling trick for random variables defined on a "slice" of the Boolean hypercube.

Recommendations

• A completion of the proof of the Edge-statistics Conjecture
• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• Anti-concentration for subgraph counts in random graphs
• Edge-statistics on large graphs
• Combinatorial anti-concentration inequalities, with applications

Cites work

• scientific article; zbMATH DE number 3510705 (Why is no real title available?)
• scientific article; zbMATH DE number 3627409 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A Combinatorial Central Limit Theorem
• A bound on the inducibility of cycles
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Algorithms with large domination ratio
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Analysis of Boolean Functions
• Anti-concentration for polynomials of independent random variables
• Bilinear and quadratic variants on the Littlewood-Offord problem
• Generalizations of the removal lemma
• Graphs Having Small Number of Sizes on Induced k‐Subgraphs
• Graphs with a small number of distinct induced subgraphs
• Harmonicity and invariance on slices of the Boolean cube
• Induced subgraphs with distinct sizes
• Invariance principle on the slice
• Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
• Logarithmic Sobolev inequalities for finite Markov chains
• Logarithmic Sobolev inequality for some models of random walks
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On a problem of K. Zarankiewicz
• On extremal problems of graphs and generalized graphs
• On the exact maximum induced density of almost all graphs and their inducibility
• On the inducibility of cycles
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Ramsey graphs induce subgraphs of many different sizes
• Ramsey graphs induce subgraphs of quadratically many sizes
• Ramsey theory for discrete structures
• Random symmetric matrices are almost surely nonsingular.
• Real advantage
• Sizes of induced subgraphs of Ramsey graphs
• Small ball probability, inverse theorems, and applications
• Spectral properties of threshold functions
• The Gotsman-Linial Conjecture is False
• The average number of spanning trees in sparse graphs with given degrees
• The correct exponent for the Gotsman-Linial conjecture
• The inducibility of graphs
• Unavoidable patterns

Cited in

(16)

• Combinatorial anti-concentration inequalities, with applications
• Singularity of the \(k\)-core of a random graph
• Majority dynamics on sparse random graphs
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• The feasible region of induced graphs
• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• Friendly bisections of random graphs
• Anti-concentration for subgraph counts in random graphs
• Local limit theorems for subgraph counts
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• A concentration result with application to subgraph count
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Edge-statistics on large graphs
• Finding unavoidable colorful patterns in multicolored graphs
• Anticoncentration and Berry-Esseen bounds for random tensors

This page was built for publication: Anticoncentration for subgraph statistics

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