# 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 [math]H_1,H_2,H_3[/math] ^{[1]}. Let *r* be an arbitrary root node. In each [math]H_i[/math], we can choose distinct [math]u_e, v_e \in e[/math] for each [math]e \in E(H_i)[/math] such that [math]\{u_ev_e:e \in E(H_i)\}[/math] is a rooted connected digraph. Now we can define the three head-disjoint strongly connected orientations: in the i-th orientation, [math]e \in E(H_i)[/math] has head [math]u_e[/math], [math]e \in E(H_{i+1})[/math] has head [math]v_e[/math], and [math]e \in E(H_{i+2})[/math] has head [math]e-u_e-v_e[/math].

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

- ↑ 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 - ↑ A. Mészáros,
*Matroid metszetek pakolása*, MSc Thesis (in Hungarian), Eötvös University, Budapest (2015), PDF link - ↑ A. Mészáros,
*A note on disjoint dijoins*, EGRES Quick Proof no. 2015-05