Bounding the distinguishing number of infinite graphs and permutation groups

zbMATH Open1301.05138arXiv1302.4409MaRDI QIDQ743653FDOQ743653

Authors: Simon M. Smith, Mark E. Watkins 

Publication date: 30 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A group of permutations G of a set V is k-distinguishable if there exists a partition of V into k parts such that only the identity permutation in G fixes setwise all of the cells of the partition. The least cardinal number k such that (G,V) is k-distinguishable is its distinguishing number. In particular, a graph X is k-distinguishable if its automorphism group Aut(X) has distinguishing number at most k in its action on the vertices of X. Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph X is not k-distinguishable (for a given cardinal k), then it contains a ball B of finite radius whose distinguishing number is at least k. Moreover, this lower bound cannot be sharpened, since for any integer k greater than 3 there exists an infinite, locally finite, connected graph X that is not k-distinguishable but in which every ball of finite radius is k-distinguishable. In the second half of this paper we show that a large distinguishing number for an imprimitive graph X is traceable to a high distinguishing number either of a block of imprimitivity or of the induced action of Aut(X) on the corresponding system of imprimitivity. The distinguishing numbers of infinite primitive graphs have been examined in detail in a previous paper by the authors together with Tom W. Tucker.

Full work available at URL: https://arxiv.org/abs/1302.4409

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Distinguishability of infinite groups and graphs
• On primitive permutation groups with nontrivial global stabilizers.
• Infinite motion and 2-distinguishability of graphs and groups
• Distinguishing numbers for graphs and groups
• The distinguishing number of quasiprimitive and semiprimitive groups

zbMATH Keywords

infinite graphdistinguishing numberimprimitive graphdistinguishing coloringimprimitive permutation groupinfinite permutation group

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Infinite graphs (05C63) Infinite automorphism groups (20B27)

Cites Work

• Symmetry breaking in graphs
• The distinguishing number of the direct product and wreath product action.
• Primitive Groups with no Regular Orbits on the Set of Subsets
• Title not available (Why is that?)
• The distinguishing chromatic number
• Distinguishability of locally finite trees
• Distinguishing infinite graphs
• Distinguishability of infinite groups and graphs
• Notes on infinite permutation groups
• Title not available (Why is that?)

Cited In (9)

• Distinguishability of infinite groups and graphs
• On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture
• The cost number and the determining number of a graph
• On the graphs with distinguishing number equal list distinguishing number
• The distinguishing number of quasiprimitive and semiprimitive groups
• On a theorem of Halin
• Infinite motion and 2-distinguishability of graphs and groups
• Title not available (Why is that?)
• Trees with distinguishing index equal distinguishing number plus one

This page was built for publication: Bounding the distinguishing number of infinite graphs and permutation groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743653)