Covering Partial Cubes with Zones - Discrete and Computational Geometry and Graphs - page 12

Proof. Again, this is a consequence of Lemma 4 and a recent result of Cardinal
and Joret [ 4 ] showing that the corresponding problem for fibres in bipartite
posets is ʣ 2 -complete.
Duffus et al. [ 9 ] mention that it is possible to construct posets on 15 n +2 elements,
every fibre of which must contain at least 8 n + 1 elements, which gives a lower
bound with a factor 8 / 15. The guarding sets for these examples do not seem to
require as many elements.
Open Problems
We left a number of problems open. For instance, we do not know the complexity
status of the problem of deciding whether there exists a guarding set of edges of
size at most k in a given graph. A natural candidate class would be ʣ 2 . For the
same problem, we do not have any nontrivial lower bound on the minimum size of
a guarding set. It would also be interesting to give tighter lower and upper bounds
on the minimum size of a guarding set in a poset and in a line arrangement.
Finally, questions involving partial cubes derived from antimatroids, such as
elimination orderings in chordal graphs, are currently under investigation.
Acknowledgments. This work was initiated at the 2nd ComPoSe Workshop held at
the TU Graz, Austria, in April 2012. We thank the organizers and the participants for
the great working atmosphere. We also acknowledge insightful discussions on related
problems with several colleagues, in particular Michael Hoffmann (ETH Zurich) and
Ferran Hurtado (UPC Barcelona).
References
1. Ackerman, E., Pach, J., Pinchasi, R., Radoicic, R., Toth, G.: A note on coloring
line arrangements (submitted)
2. Bjorner, A., Las Vergnas, M., White, N., Sturmfels, B., Ziegler, G.M.: Oriented
Matroids. Cambridge University Press, Cambridge (1993)
3. Bose, P., Cardinal, J., Collette, S., Hurtado, F., Korman, M., Langerman, S.,
Taslakian, P.: Coloring and guarding arrangements. Discrete Math. Theor. Com-
put. Sci. 15 , 139-154 (2013)
4. Cardinal, J., Joret, G.: Hitting all maximal independent sets of a bipartite graph.
Algorithmica (to appear)
5. Cheng, C.T.: A poset-based approach to embedding median graphs in hypercubes
and lattices. Order 29 , 147-163 (2012)
6. Cordovil, R., Forge, D.: Flipping in acyclic and strongly connected graphs (sub-
mitted)
7. Doignon, J.-P., Falmagne, J.-C.: Learning Spaces - Interdisciplinary Applied Math-
ematics. Springer, Heidelberg (2011)
8. Duffus, D., Kierstead, H.A., Trotter, W.T.: Fibres and ordered set coloring. J.
Comb.TheorySer.A 58 , 158-164 (1991)
9. Duffus, D., Sands, B., Sauer, N., Woodrow, R.E.: Two-colouring all two-element
maximal antichains. J. Comb. Theory Ser. A 57 , 109-116 (1991)