next up previous
Next: Steiner Triple Systems Up: Discrete Math, 5th day, Previous: Density versions of coloring

Hypergraphs

Definition 5.6  
(a)
A hypergraph is a pair $ \mathcal{H}=(V,E)$, where $ V$ is a set of vertices and $ E$ is a set of edges, an edge simply being a subset of $ V$.
(b)
A hypergraph is called $ t$-uniform, if every edge has $ t$ vertices.

Note:
(a)
A graph is a $ 2$-uniform hypergraph.
(b)
If a hypergraph on $ n$ vertices is $ t$-uniform, then $ \vert E\vert\leq\binom{n}{t}$.
(c)
Given a set $ V$ of vertices, $ \vert V\vert=n$, the number of $ t$-uniform hypergraphs on $ V$ is $ \displaystyle{2^{\binom{n}{t}}}$. The number of $ t$-uniform hypergraphs with $ m$-edges is $ \displaystyle{\binom{\binom{n}{t}}{m}}$.
(d)
The ``SET" game is based on a $ 3$-uniform hypergraph with 81 vertices, where the edges are the ``SETs."


\begin{exercise}
% latex2html id marker 799Count the total number of \lq\lq SETs'' ...
...1.) What number do
you get for $n=4$ (the actual \lq\lq SET'' game)?
\end{exercise}


Extremal set theory is concerned with problems of the following type: determine (or estimate) the maximum number of edges of a hypergraph satisfying certain conditions. We have seen some examples of this already in graph theory, for instance the Mandel-Turán Theorem and the Kovári-Sós-Turán Theorem. There are many more that deal with hypergraphs. Ruzsa and Szemerédi, in examining the combinatorial roots of Roth's Theorem on 3-term arithmetic progressions, were lead to the following natural problem in extremal set theorey:


Question: What is the maximum number of edges of a $ 3$-uniform hypergraph satisfying the following two conditions:

(C1)
No two edges share more than one point.
(C2)
There are no triangles, i.e., there is no set of three edges that intersect pairwise but have an empty intersection.

Note that the maximum possible number of edges in a 3-uniform hypergraph is $ \binom{n}{3}\sim\frac{n^3}{6}$, the total number of triples of vertices. Condition (C1) already forces a lower (uadratic) rate of growth:


\begin{exercise}
% latex2html id marker 801
Prove: if a 3-uniform hypergraph on ...
... satisfies
condition (C1) then it has at most $n(n-1)/6$ edges.
\end{exercise}

Hint. For every pair of vertices there is at most one edge containing them; and every edge contains 3 pairs of vertices.


When we add condition C2, the rate of growth of the number of edges drops even further, below quadratic:

Lemma 5.7 (Ruzsa-Szemerédi)   The maximum number $ m(n)$ of edges in a 3-uniform hypergraph satisfying conditions (C1) and (C2) is $ m(n)=o(n^2)$, i.e., $ \lim_{n\to\infty} m(n)/n^2=0$.

We will see next time that this implies Roth's theorem (i.e., Szemerédi's theorem for $ \ell=3$):


Roth's Theorem. Given $ \epsilon > 0$ there exists $ N_0$ such that for all $ N\ge N_0$, if $ \vert A\vert\subseteq[N]$ and $ \vert A\vert\geq \epsilon N$, then $ A$ contains a 3-term arithmetic progression.


\begin{exercise}
% latex2html id marker 803Assuming that we have proved Roth's...
...ting
only of odd numbers, and prove Roth's theorem for all sets.
\end{exercise}


next up previous
Next: Steiner Triple Systems Up: Discrete Math, 5th day, Previous: Density versions of coloring
Laszlo Babai 2004-06-27