Head-disjoint strongly connected orientations

From Egres Open
Jump to: navigation, search

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

  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