MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a somewhat technical question regarding the distribution of small hypergraphs in randomly chosen hypergraphs. (My hope is that this is something that can be done using standard ideas about random hypergraphs, and that I'm just not comfortable enough with the area to see how.)

I begin with some large vertex set $G$, $|G|=n$, and choose a random $k$-uniform hypergraph $\Gamma$ by independently placing each edge from ${G\choose k}$ in $\Gamma$ with probability $p$. (I expect the relevant case to be of the form $p\approx n^{-1/c}$ for some $c$.) I fix some $d$.

Now I fix some small $k$-uniform hypergraph $H$ on $n'$ vertices with at most $d$ edges, and I'm interested in those tuples $\vec x\in G^{n'}$ such that $H$ is a sub-hypergraph (not necessarily induced) of the restriction of $\Gamma$ to $\vec x$. (I think of $H$ as defining which edges I care about, and then I'm interested in those tuples in which all the edges mandated by $H$ are actually present in $\Gamma$.) I'll write $\Gamma_H\subseteq G^{n'}$ for the set of such tuples.

Now suppose I have some set $A\subseteq G^{n'}$, and I want to estimate its probability as a fraction of $\Gamma_H$. One way to do so would be to define $$\mu_H(A)=\frac{|A\cap\Gamma_H|}{|\Gamma_H|}.$$

But another way to do so would be to partition $H$ into two sub-hypergraphs, $H_0,H_1$, and ask about $$\mu'_H(A)=\frac{1}{|\Gamma_{H_0}|}\sum_{\vec x\in \Gamma_{H_0}}\frac{|\{\vec y\mid (\vec x,\vec y)\in A\cap\Gamma_H\}|}{|\{\vec y\mid (\vec x,\vec y)\in\Gamma_H\}|}.$$

Let's say $\Gamma$ is $\delta$-good if for every set $A$, $$|\mu_H(A)-\mu'_H(A)|<\delta.$$ It seems like to show that this holds, one could show that for "most" choices of $\vec x\in\Gamma_{H_0}$, $|\{\vec y\mid(\vec x,\vec y)\in\Gamma_H\}|$ is close to the value it ought to have.

I would like to show that for an appropriate choice of $p$, and with fixed values $k,d,n',\delta$, the probability that $\Gamma$ is $\delta$-good approaches $1$ as $n\rightarrow\infty$. (I'd be particularly happy to 1) know what good choices of $p$ would be, or 2) show that this follows from an established notion of pseudo-randomness.)

(I actually need a more complicated case in which one partitions $H$ into three pieces $H_0,H_1,H_2$, and looks at the measures $\mu_H$ and $\mu'_H$ relative to "almost every" fixed tuple $\vec z\in\Gamma_{H_2}$, but perhaps I'll be able to derive that easily from an answer, or perhaps I'll end up asking a follow-up question.)

share|cite|improve this question
I can't give a proof of this offhand, but I know exactly where I'd look: Alon and Spencer (using large deviations) – Anthony Quas Apr 4 '12 at 18:28
$H$ and $\Gamma$ have the same vertex set? – vzn Oct 2 '12 at 19:02
@vzn: No. I corrected a typo: it should say that H is a graph on n' vertices. I expect to find many copies of H in $(G,\Gamma)$. – Henry Towsner Oct 3 '12 at 14:50
You might want to look up Russ Lyons -- this reminds me somewhat of some questions he considered maybe 5 years ago. – Patricia Hersh Oct 3 '12 at 15:01
found this question because am looking for "large" impossible configurations in "structured" hypergraphs whereas you are looking for small configurations in random hypergraphs. maybe some of the theory might meet up in the middle eventually...? =) – vzn Oct 19 '12 at 5:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.