Head-disjoint strongly connected orientations

Definitions and mathematical statement

Let $H=(V,\mathcal E)$ be a finite $3$-uniform hypergraph: every hyperedge is a three-element subset of $V$. Hyperedges may be indexed separately if repetitions are allowed. An orientation chooses one head $h(E)\in E$ for each hyperedge. The other vertices of $E$ can reach that head in one directed step.

Call an orientation strongly connected when every nonempty proper $X\subset V$ has a hyperedge with \[ h(E)\in X,\qquad E\setminus X\ne\varnothing. \] This is equivalently mutual reachability through finite directed hyperedge steps. Three orientations $h_1,h_2,h_3$ are head-disjoint when their three heads on every fixed $E$ are distinct, and hence together use all vertices of that triple.

Characterize the $3$-uniform hypergraphs admitting three head-disjoint strongly connected orientations. Seek conditions expressed in the unoriented hypergraph that are both necessary and sufficient, together with a construction when feasible.

Each orientation uses every hyperedge, so the requested disjointness does not mean an edge partition into three subhypergraphs. A necessary condition for every nontrivial $X$ is $\sum_{E\text{ crossing }X}|E\cap X|\ge3$: across the three orientations each crossing edge can contribute exactly $|E\cap X|$ heads inside $X$. Whether proposed cut conditions suffice is part of the characterization problem, not assumed in the definition.

Short English statement

When can every triple of a hypergraph be given three different heads so that each of the three resulting orientations is strongly connected?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000041 (AMR-029-0041), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Head-disjoint strongly connected orientations. Original source indexed by AMR-029-0041. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Head-disjoint strongly connected orientations. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Head-disjoint_strongly_connected_orientations.
• S4 Strongly Connected Orientations and Integer Lattices, hypergraph orientation definitions and related conjectures. https://eprints.lse.ac.uk/127860/3/978-3-031-93112-3_1.pdf.