# Head-disjoint strongly connected orientations

An orientation of a hypergraph is a directed hypergraph obtained by choosing a single head-node in each hyperedge. We call a set of orientations of a hypergraph head-disjoint if none of the hyperedges have the same head-node in two of them. When does a 3-uniform hypergraph admit three head-disjoint strongly connected orientations?

## Remarks

An easy sufficient condition is 3-partition-connectivity of the hypergraph. Indeed, in this case it decomposes into three partition-connected hypergraphs $H_1,H_2,H_3$ [1]. Let r be an arbitrary root node. In each $H_i$, we can choose distinct $u_e, v_e \in e$ for each $e \in E(H_i)$ such that $\{u_ev_e:e \in E(H_i)\}$ is a rooted connected digraph. Now we can define the three head-disjoint strongly connected orientations: in the i-th orientation, $e \in E(H_i)$ has head $u_e$, $e \in E(H_{i+1})$ has head $v_e$, and $e \in E(H_{i+2})$ has head $e-u_e-v_e$.

If the hypergraph is 3-edge-connected, then the existence of the required orientations would follow from Woodall's conjecture. To see this, take the corresponding bipartite graph (in which the colour classes V and H correspond to the nodes and hyperedges, respectively, with two nodes v and h connected iff h contains v). By orienting the edges of this bipartite graph from H towards V we get a directed graph where every directed cut has size at least 3. It is easy to see that three disjoint dijoins in the bipartite digraph correspond to three head-disjoint strongly connected orientations of the hypergraph.

András Mészáros [2][3] proved that Woodall's conjecture for k=3 holds if the underlying undirected graph is (2,1)-partition-connected. Therefore (2,1)-partition-connectivity of the corresponding bipartite graph, which is weaker than (2,1)-partition-connectivity of the hypergraph, is sufficient for the existence of three head-disjoint strongly connected orientations.

## References

1. A. Frank, T. Király, M. Kriesell, On decomposing a hypergraph into k connected sub-hypergraphs, Discrete Applied Mathematics 131 (2003), 373-383. DOI link, EGRES Technical Report
2. A. Mészáros, Matroid metszetek pakolása, MSc Thesis (in Hungarian), Eötvös University, Budapest (2015), PDF link
3. A. Mészáros, A note on disjoint dijoins, EGRES Quick Proof no. 2015-05