4
$\begingroup$

A hypergraph $H=(V,E)$ is said to be complete and linear if

  1. whenever $e_1\neq e_2\in E$ then $|e_1\cap e_2|=1$, and
  2. for $v,w\in V$ there is $e\in E$ such that $\{v,w\}\subseteq e$.

Assuming that $V$ is infinite, is there an injective function $f:E\to V$ such that $f(e)\in e$ for all $e\in E$? (There is a Hall-marriage-theorem argument that the answer is positive for finite $V$.)

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ If $V\in E$ then either $E=\{V\}$ or else $E=\{V,\{v\}\}$ for some $v\in V$, and the existence of an injective choice function is trivial. Suppose $V\notin E$ and $V$ is infinite. Then there is an infinite cardinal $\kappa$ such that $|V|=|E|=\kappa$, and there are $\kappa$ points on each line and $\kappa$ lines through each point. Then $E$ has an injective choice function, since it's a collection of $\kappa$ sets, each of cardinality $\kappa$, where $\kappa$ is an infinite cardinal. $\endgroup$
    – bof
    Commented Nov 6, 2020 at 12:51
  • 1
    $\begingroup$ Oops, I was wrong. Your definition allows a hypergraph with vertices $$w,v_1,v_2,v_3,\dots$$ and edges $$\{v_1,v_2, v_3,\dots\},\ \{w,v_1\},\ \{w,v_2\},\ \{w,v_3\},\dots$$ which has an injective choice function. $\endgroup$
    – bof
    Commented Nov 6, 2020 at 14:34
  • 1
    $\begingroup$ However, if we assume that $V\notin E$ and that $|e|\gt2$ for all $e\in E$, then we can prove that there is an infinite cardinal $\kappa$ such that $|V|=|E|=\kappa$, and $|e|=\kappa$ for all $e\in E$, and $|\{e\in E:v\in e\}|=\kappa$ f0r all $v\in V$. Unless I'm making another mistake. $\endgroup$
    – bof
    Commented Nov 6, 2020 at 14:41
  • 1
    $\begingroup$ I was about to write an answer, but then realized that I don't immediately see how to find the injection in the last case. So I will post the first part of my answer as a comment here: If you allow for edges of order 1, then then answer is no as seen by letting $E=V\cup \{V\}$. If every edge has order at least 2 and some edge has order exactly 2, then $H$ is a "near-pencil." In this case, you can clearly find a bijection. So that leaves the case where every edge has order at least 3, in which case $H$ is a (non-degenerate) projective plane and thus every edge has the same order. $\endgroup$
    – Louis D
    Commented Nov 6, 2020 at 15:50
  • 1
    $\begingroup$ As bof points out, a projective plane with $|V|=\kappa$ will have $|E|=\kappa$, $|e|=\kappa$ for all $e\in E$, and $|\{e\in E: v\in e\}|=\kappa$ for all $v\in V$. In such a case, an injection can be constructed as described here mathoverflow.net/questions/331656/… However, this leads me to wonder about a more general question which I will start a new thread for in a moment. $\endgroup$
    – Louis D
    Commented Nov 6, 2020 at 17:35

1 Answer 1

Reset to default
2
$\begingroup$

After the discussion above, here is what I think is the cleanest proof and it has the property that $f$ is bijection (unless there is an edge of order 1).

If there is an edge of order 1, then we must have $E=\{\{v\}, V\}$ for some $v\in V$, in which case the desired injection is trivial. If there is an edge of order 2, then $H$ must be a near-pencil and $f$ can easily be found and is necessarily a bijection.

So suppose every edge has order at least 3 in which case $H$ is a non-degenerate projective plane where $\kappa:=|V|=|E|$, every edge has the same cardinality $\lambda$, and every vertex has degree $\lambda$. Now let $B$ be a bipartite graph with parts $V$ and $E$ such that $\{v,e\}\in E(B)$ if and only if $v\in e$. Note that $B$ is a $\lambda$-regular bipartite graph and thus has a perfect matching by bof's answer to my question. This perfect matching is the function $f$ you are looking for and $f$ is in fact a bijection.

Improve this answer
$\endgroup$

You must log in to answer this question.

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