Anticoncentration for subgraph statistics

DOI10.1112/JLMS.12192zbMATH Open1415.05089arXiv1807.05202OpenAlexW2883840497WikidataQ128984309 ScholiaQ128984309MaRDI QIDQ4967964FDOQ4967964

Authors:

Publication date: 11 July 2019

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

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.

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

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

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)

Cites Work

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

Cited In (16)

• Singularity of the \(k\)-core of a random graph
• Majority dynamics on sparse random graphs
• Combinatorial anti-concentration inequalities, with applications
• 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)