2
$\begingroup$

The algebraic proof of the following problem is very nice: assume $H$ is a 3-uniform hypergraph on $n$ vertices. What is the maximum number of edges of $H$ such that there does not exist two edges sharing exactly one vertex.

Then the problem can be transformed to: assume $F$ is a 3-uniform hypergraph on $[n]$ and the intersection of every two edges has even size. What is the maximum size of $F$. This is so called Oddtown problem. And if any two edges share an odd number of vertices, their intersection must have size one.

While for the original question, what if $H$ is not 3-uniform, but 5-uniform? Is there any simple proof show $H$ can have at most $O(n)$ edges? (After transformation, if there are $n+1$ edges of size 5, then there are two of them whose intersection is of odd size. But it can be 1 or 3.)

$\endgroup$

1 Answer 1

4
$\begingroup$

There's no such proof, because we can get $\binom{n-2}{3}$ edges with no size-one intersection: just take the $5$-uniform hypergraph of all edges containing two specific vertices.

What about the upper bound? Well, a generalization of the Erdős–Ko–Rado theorem says that this is optimal for a slightly stronger condition: if $n$ is sufficiently large, there can be at most $\binom{n-2}{3}$ edges in a hypergraph where any two edges intersect at least twice. (In our case, two edges can also be disjoint.)

I suspect that $\binom{n-2}{3}$ is the best possible in this problem, as well, but cannot prove it. Here is a proof of an $O(n^3)$ upper bound which almost certainly overcomplicates things and gives away too much.


Suppose that $M = \{e_1, e_2, \dots, e_k\}$ is a largest family of pairwise disjoint edges in the hypergraph. The rest must intersect at least one of these. There are at most $\binom 52^2 \binom k2 n \le 100 \binom{n/5}{2} n < \frac12 n^3$ edges that intersect two edges in $M$, because then only one vertex of those edges is left to pick freely. Delete these, and label each edge (including the edges in $M$) with a number $1, \dots, k$ according to which edge in $M$ it intersects.

Let $x$ be a vertex outside $\bigcup M$ contained in some edge $f$ with label $i$. Then any edge with a label $j \ne i$ containing $x$ must contain a second vertex of $f$ outside $e_i$, two vertices of $e_j$, and one other vertex: there are at most $20n$ choices total. So if we say that a vertex $x$ also has label $i$ if it's contained in more than $20n$ edges with label $i$, then a vertex can have at most one label. To clean up, for each vertex $x$ outside $\bigcup M$, delete the edges containing $x$ whose label is not the label of $x$, and for every vertex $x$ with no label, delete all edges containing it; this removes at most $(n-5k)k(20n) \le 4n^3$ edges total.

Finally, partition all vertices into $S_1, S_2, \dots, S_n$ according to their label, putting the vertices of $e_i$ into $S_i$ as well. The edges of label $i$ form a $2$-intersecting family contained in $S_i$: two edges of label $i$ cannot be disjoint, because then we could get a larger disjoint family than $M$ by replacing $e_i$ with those two edges. Therefore, by the Erdős–Ko–Rado extension cited above, at most $\binom{|S_i|-2}{3}$ edges have label $i$. By convexity, $$\binom{|S_1|-2}{3} + \dots + \binom{|S_k|-2}{3}$$ is maximized when all of the $S_i$ are empty except for one, in which case it is equal to $\binom{n-2}{3}$.

Taking into account our deletions, our original hypergraph had at most $\binom{n-2}{3} + 4n^3 + \frac12 n^3$ edges, which is $O(n^3)$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.