Symmetry Breaking in Discrete Structures (18w5050)
The Casa Matemática Oaxaca (CMO) will host the "Symmetry Breaking in Discrete Structures" workshop from September 16th to September 21st, 2018. Can the vertices of a cube be can be colored using the colors black and white so that no symmetry of the cube preserves the coloring? The answer is no; three colors are required. On the other hand, four are needed for the tetrahedron and only two for the dodecahedron. In general, one can ask how many colors are needed to break the symmetry of any mathematical structure. The idea of symmetry-breaking with colors first arose for networks, or “graphs”, in the 1970s, was rediscovered in 1996, and has generated more than 100 papers since then. But the notion of the “group” of all symmetries of a structure has been studied since the 19th century, and symmetry-breaking with colors also appeared in group theory papers of the 1980s. Moreover, the idea has been applied to many structures other than graphs. The goal of this workshop is to bring together graph theorists and group theorists to study symmetry-breaking in all its variations and contexts. The Casa Matemática Oaxaca (CMO) in Mexico, and the Banff International Research Station for Mathematical Innovation and Discovery (BIRS) in Banff, are collaborative Canada-US-Mexico ventures that provide an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station in Banff is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT). The research station in Oaxaca is funded by CONACYT.
19
2018
34
10 Stunden 35 Minuten
19 Ergebnisse
22:58
Imrich, WilfriedMany results on distinguishing finite and locally finite graphs have easy extensions to graphs without degree restrictions or to uncountable graphs. Some other results are very difficult to generalize, and many hopelessly difficult. The talk presents a selection of results and problems for graphs without degree restrictions or uncountable graphs, and how they relate to the locally finite case. It concludes with challenging, interesting problems.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
37:19
Conder, MarstonThe symmetry of a discrete structure can easily be altered (or in the case of maps, destroyed) by changing just a small part of it. But there are other contexts where a large degree of symmetry is desirable without achieving the maximum possible symmetry, for example with maps and polytopes that are maximally symmetric by orientation-preserving automorphisms but are chiral (admitting no refections). In a similar vein, sometimes restricting the symmetry can help achieve things that are either impossible or difficult when full symmetry is assumed. I will outline a few recent discoveries that explain and illustrate these phenomena.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
35:16
Collins, KarenWe introduce two distinguishing chromatic numbers of partially ordered sets, one based on incomparability and the other on comparability. This study has given us the opportunity to apply classic results in poset theory to obtain results about these parameters. We use Dilworth's Theorem to obtain a bound for the parameter based on incomparability. In distinguishing chromatic bounds based on comparability, we use the proof of Birkoff's Fundamental Theorem of Distributive Lattices. In contrast, we provide a bound for the Boolean lattice, Bn, based on its high degree of symmetry.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
30:19
Trenk, AnnWe introduce the distinguishing numbers of partially ordered sets. This study has given us the opportunity to apply classic results in poset theory to obtain results about this parameter. We present both an elementary proof of the distinguishing number of divisibility lattices and a more general result that employs Birkoff's Fundamental Theorem of Distributive Lattices. In other distinguishing bounds, we use a fundamental result about straight line embeddings of ranked planar posets with a minimum element and a maximum element to find bounds on planar posets.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
41:23
Ellingham, MarkIn 2011 Ellingham and Schroeder introduced the idea of a "distinguishing partition" for an action of a group Γ on a set X, namely a partition of X that is preserved by no nontrivial element of Γ. As a special case, a distinguishing partition of a graph is a partition of the vertex set that is preserved by no nontrivial automorphism. Distinguishing partitions are weaker at breaking symmetry than distinguishing colourings, and not every graph has a distinguishing partition. We discuss our work with Schroeder which linked distinguishing partitions of complete equipartite graphs with asymmetric uniform hypergraphs. We find a function f(n) such that a distinguishing partition for Km(n)=Kn,n,…,n, or equivalently for the wreath product action Sn≀Sm, exists if and only if m≥f(n). We also discuss some other work on distinguishing partitions of complete multipartite graphs by Michael Goff.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
30:24
1Harper, ScottThe distinguishing number of a permutation group G≤\Sym(X) is the smallest number of colours required to colour the points of X such that only the identity of G preserves the colouring. The distinguishing number of a graph, in the traditional sense, is simply the distinguishing number of its automorphism group. Seress proved that every primitive group of degree n other than \Alt(n) and \Sym(n) has distinguishing number 2, except for a short list of known examples (with distinguishing number 3 or 4). In this talk, I will overview previous work on the distinguishing number of groups, before discussing recent joint work with Alice Devillers and Luke Morgan on the distinguishing number of semiprimitive groups. I will highlight the application of our result to graphs.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
33:39
1Morgan, LukeA permutation group is semiprimitive if each normal subgroup is transitive or semiregular. This class of groups generalises the classes of primitive and quasi primitive groups, and has attracted most interest due to problems in algebraic graph theory. In this talk, I will survey some recent joint work with Kyle Rosa and Cheryl Praeger where we explored the question of whether certain bounds (in terms of degree) that hold for primitive groups could be adapted to the class of semiprimitive groups. Motivated by "useful'' results for the class of primitive groups, we investigated bounds on order, base size and fixity. In general, we found that similar bounds hold, or, one can establish even stronger bounds if we exclude certain families of primitive groups.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
26:06
11Zemljič, Sara SabrinaThe Sierpiński product of graphs was introduced as a generalization of Sierpiński graphs, which is a fractal-like family of graphs. The main building blocks of Sierpiński graphs are complete graphs and each next iteration is built in the fractal-like manner of a complete graph. This idea was recently generalized to a graph product, where instead of initially taking just one graph, we build a fractal-like structure with two arbitrary graphs, say G and H. Intuitively this is done in such a way that the product G⊗H has |G| copies of graph H which are connected among themselves according to the edges in G. So we get a graph with local structure of H, but global structure of G (i.e., if we contract all copies of H to a vertex, we get a copy of graph G). This construction is interesting because it may yield graphs with distinguishing number greater than 2. In the talk I will describe the Sierpiński products and list some of their basic properties, which may be useful to answer the open question(s) about the distinguishing number of Sierpiński products.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
31:53
1Lachmann, ThomasAll but four finite vertex-transitive cubic graphs are 2-distinguishable. We discuss the corresponding amount, resp. density, of points needed to break all the symmetries for the latter ones. This will be done by splitting the problem into three cases depending on the number of edge orbits the graph has. In the cases of one or three edge orbits the number needed is always finite. The talk will be focused on the case of two edge orbits which will prove to be a bit more diverse.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
39:31
1Laflamme, ClaudeHomogenous structures exhibit a high degree of symmetry. In particular their automorphism group is transitive, and any partial isomorphism between two finite substructures extends to an automorphism of the entire structure. It is thus natural to better understand these symmetries, and one approach is by trying to break them. The distinguishing number provides an interesting tool to do so and at the same time providing structural information. Two such well known homogeneous structures are the rationals and the Rado graph. The first one is easily seen to have unbreakable symmetry in this setting, its distinguishing number is infinite. On the other hand Imrich et al. showed that the Rado graph has distinguishing number 2. We will present an overview of the distinguishing number of the homogeneous simple and directed graphs through their classification, and discuss recent results for the countable Urysohn homogenous metric spaces of given spectrum.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
36:32
1Kivva, BohdanThis talk is based on the paper by Xiaorui Sun and John Wilmes, "Structure and automorphisms of primitive coherent configurations" (2015). Coherent configurations (CCs) are edge-colorings of the complete directed graph satisfying certain regularity conditions, modeling the orbitals (orbits on ordered pairs) of permutation groups. Introduced by Schur in 1934 for the study of permutation groups, CCs also include strongly regular graphs and association schemes, structures that do not necessarily arise from groups. Primitive CCs (PCCs) are a combinatorial model of primitive permutation groups. A base of a permutation group is a subset of the permutation domain of which the pointwise stabilizer is the identity. A base of a structure (such as a graph or a CC) is a base of its automorphism group. The minimum size of a base is a measure of the cost of destroying all symmetry. 37 years ago Babai gave a nearly tight O(n−−√logn) upper bound on the minimum base size of PCCs with the trivial exception of the clique (Annals of Math, 1981). As a corollary, this result solved the then century-old problem of bounding the order of primitive permutation groups in an unexpected, purely combinatorial way. In a major recent development, Sun and Wilmes reduced the upper bound to O(n1/3(logn)4/3), with known exceptions. As a corollary, they classify the largest primitive permutation groups, a result previously only known through the classification of finite simple groups (CFSG) (Cameron 1981). At the same time, the scope of their result goes significantly beyond primitive permutation groups, into a combinatorial domain where the CFSG has little relevance. To prove their result, Sun and Wilmes develop a combinatorial structure theory of PCCs. A crucial element of their theory is the discovery of "asymptotically uniform clique geometries" in PCCs with parameters in a certain range. Like Babai's, the Sun-Wilmes result is algorithmic: the proof is an analysis of the individualization/refinement method.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
46:43
1Kivva, BohdanThe minimal degree of a permutation group G is the minimum number of points not fixed by non-identity elements of G. Lower bounds on the minimal degree have strong structural consequences on G. In 2014 Babai proved that the automorphism group of a strongly regular graph with n vertices has minimal degree at least cn, with known exceptions. Strongly regular graphs correspond to primitive coherent configurations of rank 3. We extend Babai's result to primitive coherent configurations of rank 4. We also show that the result extends to non-geometric primitive distance-regular graphs of bounded diameter. The proofs combine structural and spectral methods. The results have consequences to primitive permutation groups that were previsouly known using the classification of finite simple groups (Cameron, Liebeck).
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
23:18
Alikhani, SaeidThe distinguishing number (index) D(G) (D′(G)) of a graph G is the least integer d such that G has a vertex (edge) labeling with d labels that is preserved only by a trivial automorphism. In this talk we consider the maximal outerplanar graphs (MOP graphs) and show that MOP graphs, except K3, can be distinguished by at most two vertex (edge) labels. We also consider the distinguishing number and distinguishing index of regular and Cayley graphs. In particular, we present a family of Cayley graphs, graphical regular representations of a group, for which the distinguishing number and the distinguishing index is two. Coauthor: Samaneh Soltani
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
29:23
3Shekarriz, Mohammad HadiA vertex coloring of a graph G is called distinguishing if no non-identity automorphism of G preserves it. The distinguishing number of G, denoted by D(G), is the smallest number of colors required for such a coloring. We are intent to count number of different distinguishing colorings with a set of k colors for some certain kinds of graphs. An application to distinguishing lexicographic products of graphs is also presented. Coauthors: Bahman Ahmadi, Fatemeh Alinaghipour.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
36:16
1Wozniak, MariuszIf we want to distinguish all vertices of the graph by coloring its elements, then we have the following possibilities. We can use the concept of coloring that breaks non-trivial automorphisms, or coloring that induces different color palettes for each vertex. These approaches are not independent. Always distinguishing using automorphisms is stronger than using palettes. And, very often, the corresponding parameters are quite distant from each other. We will show several situations when the corresponding parameters are close to each other. The talk is based on the papers [1] and [2]. [1] R. Kalinowski, M. Pilśniak, J. Przybyło and M. Woźniak, How to personalize the vertices of a graph?, European Journal of Combinatorics 40 (2014), 116-123. [2] R. Kalinowski, M. Pilśniak, M. Woźniak, Distinguishing graphs by total colourings, Ars Mathematica Contemporanea 11 (2016), 79-89.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
31:14
1Kalinowski, RafalThe distinguishing index D′(G) of a graph G is the least number of colours in an edge colouring that breaks all nontrivial automorphisms of G. This invariant is defined only for graphs with at most one isolated vertex and without K2 as a component (we call them admissible graphs). The general upper bound for connected admissible graphs is D′(G)≤Δ(G) except for small cycles C3,C4,C5. Moreover, it was proved by the second author that the equality holds only for cycles of length at least six, symmetric and bisymmetric trees and for two small graphs K4,K3,3. Recently, we proved with Imrich and Woźniak that D′(G)≤⌈Δ(G)√⌉+1 for every connected graph of order at least seven and without pendant edges. There are classes of graphs with the distinguishing index at most two (perhaps with few known exceptions). For instance, traceable graphs, claw-free graphs, Cartesian powers of connected graphs, and 3-connected planar graphs (the latter result was recently proved by Pilśniak and Tucker). A number of open problems will be formulated.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
15:40
2Verret, GabrielApart from finitely many exceptions, connected vertex-transitive graphs of valency at most 3 have distinguishing number 2. Recently, Florian Lehner and I determined the distinguishing number of all vertex-transitive graphs of valency 4. In this case, there are infinitely many examples with distinguishing number 3. I will discuss this recent work, as well as some intriguing related questions.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
41:06
8Lehner, FlorianA graph is said to have infinite motion, if every automorphism moves infinitely many vertices. Tucker's Infinite Motion Conjecture asserts that if a locally finite graph has infinite motion, then there is a 2-colouring of its vertex set which is only preserved by the identity automorphism. We show that this is true for graphs whose maximum degree is at most 5. In case the maximum degree is 3, we can even drop the assumption of infinite motion.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
46:16
2Tucker, ThomasGiven a group A acting on a set X, the distinguishing number, or asymmetric coloring number, denoted D(A,X) or ACN(A,X), is the smallest k such that X has a k-coloring where the only elements of A preserving the coloring fix all elements of X, thus "breaking" the symmetry of X under A. Albertson and Collins [1996] introduced and named D(G) in the context of a graph G with A=Aut(G),X=V(G), but precedents include Babai's work [1977] on regular trees, Cameron et al.\ [1984] and Seress [1997] on regular orbits for a primitive permutation group acting on the set of subsets of X, and work of many authors on the graph isomorphism problem using colors to "individualize" vertices. This talk will survey various aspects of symmetry breaking: contexts other than graphs (such as maps), bounds relating D(G) and the maximal degree of G, variations of D(G) where the coloring is proper or where edges are colored instead of vertices. An underlying theme is the role of the elementary "Motion Lemma'' (Cameron et al. [1984] and Russel and Sundaram [1997]) that D≤2 when m(A)>2log2(|A|), where m(A) is the minimum number of elements of X moved by any element of A not acting as the identity on X.
2018Banff International Research Station (BIRS) for Mathematical Innovation and Discovery