Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-30T20:03:00.915Z Has data issue: false hasContentIssue false
  • English
  • Français

Cycle-free partial orders and ends of graphs

Published online by Cambridge University Press:  01 May 2009

ROBERT GRAY  and
JOHN K. TRUSS
ROBERT GRAY
Affiliation:
School of Mathematics, University of Leeds, Leeds LS2 9JT. e-mail: [email protected], [email protected]
JOHN K. TRUSS
Affiliation:
School of Mathematics, University of Leeds, Leeds LS2 9JT. e-mail: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The relationship between posets that are cycle-free and graphs that have more than one end is considered. We show that any locally finite bipartite graph corresponding to a cycle-free partial order has more than one end, by showing a correspondence between the ends of the graph and those of the Hasse graph of its Dedekind–MacNeille completion. If, in addition, the cycle-free partial order is k-CS-transitive for some k ≥ 3 we show that the associated graph is end-transitive. Using this approach we go on to prove that, for infinite locally finite 3-CS-transitive posets with maximal chains of height 2, the properties of being crown-free and being cycle-free are equivalent. In contrast to this we show that the non-locally finite bipartite graphs arising from skeletal cycle-free partial orders each have only one end. We include a corrected proof of a result from an earlier paper on the axiomatizability of the class of cycle-free partial orders.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 146 , Issue 3 , May 2009 , pp. 535 - 550
Copyright
Copyright © Cambridge Philosophical Society 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Adeleke, S. A. and Neumann, P. M.Relations related to betweenness: their structure and automorphisms. Mem. Amer. Math. Soc. 131 (623) (1998), viii+125.Google Scholar
[2]Creed, P., Truss, J. K. and Warren, R.The structure of k-CS-transitive cycle-free partial orders with infinite chains. Math. Proc. Camb. Phil. Soc. 126 (1) (1999), 175–194.CrossRefGoogle Scholar
[3]Diestel, R., Jung, H. A. and Möller, R. G.On vertex transitive graphs of infinite degree. Arch. Math. (Basel), 60 (6) (1993), 591–600.CrossRefGoogle Scholar
[4]Chicot, K. M. Transitivity properties of countable trees. Ph.D thesis, University of Leeds (2004).Google Scholar
[5]Droste, M.Structure of partially ordered sets with transitive automorphism groups. Mem. Amer. Math. Soc. 57 (334) (1985), vi+100.Google Scholar
[6]Droste, M., Holland, W. C. and Macpherson, H. D.Automorphism groups of infinite semilinear orders. I, II. Proc. London Math. Soc. (3) 58 (3) (1989), 454–478, 479–494.CrossRefGoogle Scholar
[7]Droste, M., Truss, J. K. and Warren, R.Simple automorphism groups of cycle-free partial orders. Forum Math. 11 (3) (1999), 279–294.CrossRefGoogle Scholar
[8]Gray, R.k-CS-transitive infinite graphs To appear in J. Combin. Theory Ser. B.Google Scholar
[9]Gray, R. and Truss, J. K.Construction of some one-arc-transitive bipartite graphs. Discrete Math. 308 (2008), 6392–6405.CrossRefGoogle Scholar
[10]Gromov, M. Infinite groups as geometric objects In Proceedings of the International Congress of Mathematicians, Vol. 1, 2, pages 385–392. PWN, Warsaw (1983).Google Scholar
[11]Mendelson, B.Introduction to Topology. College Mathematics Series (Allyn and Bacon Inc., 1962).Google Scholar
[12]Möller, R. G.Ends of graphs. Math. Proc. Camb. Phil. Soc. 111 (2) (1992), 255–266.CrossRefGoogle Scholar
[13]Möller, R. G.Ends of graphs. II. Math. Proc. Camb. Phil. Soc. 111 (3) (1992), 455–460.CrossRefGoogle Scholar
[14]Möller, R. G. Groups acting on locally finite graphs—a survey of the infinitely ended case. In Groups '93 Galway/St. Andrews, Vol. 2, volume 212 of London Math. Soc. Lecture Note Ser., pages 426–456 (Cambridge University Press, 1995).CrossRefGoogle Scholar
[15]Möller, R. G.Descendants in highly arc transitive digraphs. Discrete Math. 247 (1–3) (2002), 147–157.CrossRefGoogle Scholar
[16]Morel, A. C.A class of relation types isomorphic to the ordinals. Michigan Math. J. 12 (1965), 203–215.CrossRefGoogle Scholar
[17]Praeger, C. E.On a reduction theorem for finite, bipartite 2-arc-transitive graphs. Australas. J. Combin. 7 (1993), 21–36.Google Scholar
[18]Rubin, M.The reconstruction of trees from their automorphism groups. Contemp. Math. 151 (1993).Google Scholar
[19]Thomassen, C. and Woess, W.Vertex-transitive graphs and accessibility. J. Combin. Theory Ser. B 58 (2) (1993), 248–268.CrossRefGoogle Scholar
[20]Truss, J. K. Countable homogeneous and partially homogeneous ordered structures. In Algebra, Logic, Set Theory, ed. Löwe, B., Studies in Logic (College Publications, 2007).Google Scholar
[21]Truss, J. K.Betweenness relations and cycle-free partial orders. Math. Proc. Camb. Phil. Soc. 119 (4) (1996), 631–643.CrossRefGoogle Scholar
[22]Truss, J. K.On k-CS-transitive cycle-free partial orders with finite alternating chains. Order 15 (2) (1998/99), 151–165.CrossRefGoogle Scholar
[23]Warren, R.The structure of k-CS-transitive cycle-free partial orders. Mem. Amer. Math. Soc. 129 (614) (1997), x+166.Google Scholar
[24]Woess, W.Topological groups and infinite graphs. Discrete Math. 95 (1–3) (1991), 373–384. Directions in infinite graph theory and combinatorics (Cambridge, 1989).CrossRefGoogle Scholar