3
$\begingroup$

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if

  1. $\bigcup{\frak P} = X$, and

  2. $P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$.

Let $H = (V,E)$ be a hypergraph with $V \neq \varnothing$ and $\bigcup E = V$. A partition ${\frak P}$ of $V$ is said to be splitting if for all $e\in E$ and $P \in {\frak P}$ we have $|e \cap P| = 1$, and we call such a hypergraph admitting a splitting partition partite. It is easy to see that the edges of a partite hypergraph all have the same cardinality - and every splitting partition also has that cardinality.

If $E_1 \subseteq E$ we call $H|_{E_1}:=(\bigcup E_1, E_1)$ the subhypergraph induced by $E_1$.

Question. If $H=(V,E)$ is a hypergraph with $\bigcup E = V$, is there $E_1\subseteq E$ such that $H|_{E_1}$ is partite, but whenever we have $E_2\subseteq E$ with $E_1\subseteq E_2$ and $E_1\neq E_2$, then $H|_{E_2}$ is no longer partite?

Note. A straightforward application of Zorn's Lemma seemed to bear no fruit; I wasn't able to prove that the union of a chain of partite edge sets needs to be partite again. Of course I will remove this question if I committed a stupid mistake and there is an easy argument showing that partiteness carries through unions of chains.

$\endgroup$
2
  • $\begingroup$ I don't understand the question. What's to stop $E$ itself being partite, in which case all its subsets will be partite? $\endgroup$
    – gowers
    Commented May 12, 2020 at 7:25
  • $\begingroup$ Right @gowers, in that case $E$ is the (only) maximal partite subset of itself. But the question is, even if $H=(V,E)$ is not partite, can we find $E_1 \subseteq E$ such that $(\bigcup E_1, E_1)$ is partite, but no proper superset of $E_1$ has this property? $\endgroup$ Commented May 12, 2020 at 10:22

0

You must log in to answer this question.

Browse other questions tagged .