Loading…

On random sampling in uniform hypergraphs

A k‐graph \documentclass{article} \usepackage{amsmath,amsfonts,mathrsfs,amssymb}\pagestyle{empty}\begin{document} ${\mathcal{G}}^{(k)}$ \end{document} on vertex set [n] = {1,…,n} is said to be (ρ,ζ)‐uniform if every S ⊆ [n] of size s = |S| > ζn spans (ρ ± ζ)\documentclass{article} \usepackage{ams...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2011-07, Vol.38 (4), p.422-440
Main Authors: Czygrinow, Andrzej, Nagle, Brendan
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A k‐graph \documentclass{article} \usepackage{amsmath,amsfonts,mathrsfs,amssymb}\pagestyle{empty}\begin{document} ${\mathcal{G}}^{(k)}$ \end{document} on vertex set [n] = {1,…,n} is said to be (ρ,ζ)‐uniform if every S ⊆ [n] of size s = |S| > ζn spans (ρ ± ζ)\documentclass{article} \usepackage{amsmath,amsfonts,mathrsfs,amssymb}\pagestyle{empty}\begin{document} $\binom{s}{k}$ \end{document} edges. A ‘grabbing lemma’ of Mubayi and Rödl shows that this property is typically inherited locally: if \documentclass{article} \usepackage{amsmath,amsfonts,mathrsfs,amssymb}\pagestyle{empty}\begin{document} ${\mathcal{G}}^{(k)}$ \end{document} is (ρ,ζ)‐uniform, then all but exp{−s1/k/20}\documentclass{article} \usepackage{amsmath,amsfonts,mathrsfs,amssymb}\pagestyle{empty}\begin{document} $\binom{n}{s}$ \end{document} sets \documentclass{article} \usepackage{amsmath,amsfonts,mathrsfs,amssymb}\pagestyle{empty}\begin{document} $ S \in \binom{[n]}{s}$ \end{document} span (ρ,ζ′)‐uniform subhypergraphs \documentclass{article} \usepackage{amsmath,amsfonts,mathrsfs,amssymb}\pagestyle{empty}\begin{document} ${\mathcal{G}}^{(k)}\lbrack S\rbrack$ \end{document}, where ζ′→ 0 as ζ → 0, s ≥ s0(ζ′) and n is sufficiently large. In this article, we establish a grabbing lemma for a different concept of hypergraph uniformity, and infer the result above as a corollary. In particular, we improve, in the context above, the error exp{−s1/k/20} to exp{−cs}, for a constant c = c(k,ζ′) > 0. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 422–440, 2011
ISSN:1042-9832
1098-2418
1098-2418
DOI:10.1002/rsa.20326