Symmetry Breaking in Discrete Structures (18w5050)

Arriving in Oaxaca, Mexico Sunday, September 16 and departing Friday September 21, 2018


(Grenfell Campus, Memorial University of Newfoundland)

Wilfried Imrich (Montanuniversität Leoben)

Debra Boutin (Hamilton College)

Thomas Tucker (Colgate University)


The aim of the workshop is to bring together researchers in distinguishing number, from both the graph theory and the permutation group communities. There has not been any other conference focussing on this topic, although a few other conferences have included talks or special sessions on the subject. The workshop will have three themes. One is applications to graph theory. Another is to apply symmetry-breaking to other areas of mathematics besides graph theory: other discrete structures, group theory, logic, computer science. The third theme is to provide a coherent vision of symmetry-breaking, developing tools and general structure theorems that can be used in a variety of contexts.

The workshop will begin with a morning of introductory lectures, presented by experts in the area. Since the audience will include researchers from different fields, these talks will be as general as possible, employing language, notation, and examples that are consistent and widely used. Each talk, however, may focus on one particular context or problem. The remaining sessions will be organized by topic: graphs, other combinatorial structures, permutation groups, refinements or extensions of distinguishing number.

There are a number of questions that speakers will address: 1) Transitivity has played a much smaller role than one would expect, especially since small motion implies a local structure that might be quite restrictive globally. Are there general theorems that apply to transitive permutation groups in general, and vertex-transitive graphs in particular? 2) A small number of families of graphs, such as products or Kneser graphs, have received most of the attention. For what other families of graphs is distinguishing number a natural question? 3) There are various refinements and extensions of distinguishing number. When $D(G)=2$, one can consider the “cost”, that is, the least number of times one color is used. For graphs, there is the “distinguishing chromatic number”, where the coloring is required to be proper, that is, adjacent vertices receive different colors. Again for graphs, there is the “edge-distinguishing number”, also called the “distinguishing index”, where the coloring is on edges instead of vertices. One interesting aspect of this is that if a graph has a hamiltonian path of length at least 7, then its edge-distinguishing number is two. Thus for vertex transitive graphs, there is a connection to Lovász's conjecture. 4) Collins and Trenk have shown that the distinguishing number of a finite graph is at most one more than the maximum valence. (For locally finite graphs it is the supremum as Imrich, Klavžar and Trofimov have shown.) Are there ways that a bound on valence can be used to classify finite or infinite graphs with distinguishing number greater than two? 5) Motion versus minimal degree is a prime example of the lack of communication between graph theorists and group theorists. We have mentioned Cameron's 1986 work, but minimal degree goes back to the 19th century. Are there other connections to uncover between motion and minimal degree? 6) For infinite graphs and groups, the cardinality of both $\Omega$ and $|G|$ become important. A common application is to automorphism groups of relational structures on a denumerable set, $\Omega$, which are by definition closed in the compact-open topology on $\Omega$. For example, in the Infinite Motion Conjecture for permutation groups, one requires $G$ to be closed. What can one say about $G$ if it is not closed?

A total of 35 mathematicians (in addition to the organizers) have been contacted and have expressed keen interest in participation in the workshop, should it be selected. The list includes at least four mathematicians who have completed their PhD within the last two years, or are in the process of completing it, and eight women mathematicians.

We expect numerous new results, methods and new insight pertaining to the topics of the workshop and invite the participants to publish articles (possibly in a special issue of a journal) based on the work presented and progressed at the workshop.