Find a hypergraph such that $|e|$ even, $|e\cap f|$ odd, and $|E|>|V|$

91 Views Asked by At

Here is a problem I have been working on (it comes from the standard "odd-town" problem. The idea is to show that the analogy for "even-town" doesn't work).

Find a hypergraph such that the edges have even size, the intersection of any two edges has odd size, and there are strictly more edges then vertices.

Some things to note: any two edges must intersect, since empty intersection is even.

In any intersecting linear space, $|E|=|V|$. Since our graph is intersecting, it must NOT be a linear space. That is, at least two vertices are not connected by any edge.

The Fisher inequality says that if the intersection of any two edges is $\lambda>0$, then $|E|\le |V|$. Thus, there must be more than one possible "intersection size."

From trying cases, I believe you need at least five vertices to find such a hypergraph. Any suggestions would be much appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

It turns out no such counterexample can exist.

Look at theorem $2$ in this pdf