3
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\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$ Commented Oct 30, 2018 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$ Commented Oct 30, 2018 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$ Commented Oct 30, 2018 at 22:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .