Let $V$ be a finite set, $G$ a simple graph with vertex set $V$, and $H$ a hypergraph (i.e., set of subsets) with vertex set $V$ satisfying the following three conditions:

  • each pair of elements of $V$ is contained in a unique hyperedge of $H$;

  • for $x, y, z \in V$, if $x$ is $G$-adjacent to $z$ and $y$ is $G$-adjacent to $z$, then $z$ is also $G$-adjacent to every other element of the hyperedge containing $x$ and $y$;

  • the restriction of $G$ to any hyperedge of $H$ is a perfect or near-perfect matching (i.e., a disjoint union of edges together with at most one isolated vertex).

Question: is it possible that there is $x\in V$ such that $x$ belongs to two (or more) hyperedges in $H$ of size greater than or equal to three?

Note: if we allow $V$ infinite, then this is possible. Indeed, we can take $V$ to be the set of all lines in $\mathbb{R}^n$ for $n\geq 3$, with two elements $G$-adjacent if they are orthogonal, and where the hyperedges of $H$ are all the two-dimensional subspaces.


I'm sorry, but I do not understand why you cannot model the same example over a finite field.

Let, say, $V$ be the set of non-isotropic points in the projective space $P^3(\mathbb F_p)$ for a large $p$, i.e., the points $(x:y:z:t)$ with $x^2+y^2+z^2+t^2\neq0$. Again, two points are connected in $G$ if they are orthogonal (the non-isotropy condition avoids loops), and the hyperedges in $H$ are projective lines (restricted to $V$). All the conditions are clearly satisfied (in the third condition, each hyperedge induces even a perfect matching --- again with the use of non-isotropy condition). Moreover, almost al hyperedges of $H$ will be large, if $p$ is such.

  • $\begingroup$ Sorry, maybe the problem is indeed simple: I'm not used to thinking about these kind of configurations. But can I ask what "orthogonal" means in this context? $\endgroup$ – Sam Hopkins Oct 30 '18 at 21:20
  • $\begingroup$ Sorry, I did not mean to say this is completely trivial;). Surely, two points $(x_1:x_2:x_3:x_4)$ and $(y_1:y_2:y_3:y_4)$ are orthogonal if $\sum x_iy_i=0$. Notice that the points orthogonal to a given non-isotropis point $p$ form a 2-dimensional projective plane which does not contain $p$. $\endgroup$ – Ilya Bogdanov Oct 30 '18 at 22:22
  • $\begingroup$ Ok, I think I understand. I did not realize this non-isotropic condition was enough to make the finite field case behave like the real case. $\endgroup$ – Sam Hopkins Oct 30 '18 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.