Klarner systems and tiling boxes with polyominoes

Let T be a protoset of d-dimensional polyominoes. Which boxes (rectangular parallelepipeds) can be tiled by T? A nice result of Klarner and Göbel asserts that the answer to this question can always be given in a particularly simple form, namely, by giving a finite list of “prime” boxes. All other boxes that can be tiled can be deduced from these prime boxes. We give a new, simpler proof of this fundamental result. We also show that there is no upper bound to the number of prime boxes, even when restricting attention to singleton protosets. In the last section, we determine the set of prime rectangles for several small polyominoes.     

Fractal penrose tiles II: Tiles with fractal boundary as duals of penrose triangles

Summary Suppose given a quasi-periodic tiling of some Euclidean space E _u which is self-similar under the linear expansiong: E_μ→E_μ. It is known that there is an embedding of E_μ into some higher-dimensional space ℝ ^N and a linear automorphism with integer coefficients such that E _u ⊂ ℝ ^N is invariant under andg is the restriction of to E _u . Let E _s be the -invariant complement of E _u , and . If certain conditions are fulfilled (e.g. must be a lattice automorphism,g ^* is an expansion), we construct a self-similar tiling of E _s whose expansion isg ^*, using the information contained in the original tiling of E_μ. The term “Galois duality” of tilings is motivated by the fact that the eigenvalues ofg ^* are Galois conjugates of those ofg. Our method can be applied to find the Galois duals which are given by Thurston, obtained in a somewhat other way for the case that dim E_μ=1, andg is the multiplication by a cubic Pisot unit. Bandt and Gummelt have found fractally shaped tilings which can be considered as strictly self-similar modifications of the kites-and-darts, and the rhombi tilings of Penrose. As one of the examples, we show that these fractal versions can be constructed by dualizing tilings by Penrose triangles.     

A four-color theorem for periodic tilings

There exist exactly 4044 topological types of 4-colorable tile-4-transitive tilings of the plane. These can be obtained by systematic application of two geometric algorithms, edge-contraction and vertex-truncation, to all tile-3-transitive tilings of the plane.     

Arc-transitive digraphs with quasiprimitive local actions

Let Γ be a finite G-vertex-transitive digraph. The in-local action of $(\mathrm{\Gamma },G)$ is the permutation group $L_{?}$ induced by a vertex-stabiliser on the set of in-neighbours of the corresponding vertex. The out-local action$L_{+}$ is defined analogously. Note that $L_{?}$ and $L_{+}$ may not be isomorphic. We thus consider the problem of determining which pairs $(L_{?},L_{+})$ are possible. We prove some general results, but pay special attention to the case when $L_{?}$ and $L_{+}$ are both quasiprimitive. (Recall that a permutation group is quasiprimitive if each of its nontrivial normal subgroups is transitive.) Along the way, we prove a structural result about pairs of finite quasiprimitive groups of the same degree, one being (abstractly) isomorphic to a proper quotient of the other.     

Relative difference sets fixed by inversion and Cayley graphs

Using graph theoretical technique, we present a construction of a (30,2,29,14)-relative difference set fixed by inversion in the smallest finite simple group—the alternating group A₅. To our knowledge this is the first example known of relative difference sets in the finite simple groups with a non-trivial forbidden subgroup. A connection is then established between some relative difference sets fixed by inversion and certain antipodal distance-regular Cayley graphs. With the connection, several families of antipodal distance-regular Cayley graphs which are coverings of complete graphs are presented.     

Semisymmetric graphs

Let be a regular covering projection of connected graphs with the group of covering transformations isomorphic to N. If N is an elementary abelian p-group, then the projection ℘_N is called p-elementary abelian. The projection ℘_N is vertex-transitive (edge-transitive) if some vertex-transitive (edge-transitive) subgroup of the automorphism group of X lifts along ℘_N, and semisymmetric if it is edge- but not vertex-transitive. The projection ℘_N is minimal semisymmetric if it cannot be written as a composition ℘_N=℘℘_M of two (nontrivial) regular covering projections, where ℘_M is semisymmetric.Malni? et al. [Semisymmetric elementary abelian covers of the Möbius-Kantor graph, Discrete Math. 307 (2007) 2156-2175] determined all pairwise nonisomorphic minimal semisymmetric elementary abelian regular covering projections of the Möbius-Kantor graph, the Generalized Petersen graph GP(8,3), by explicitly giving the corresponding voltage rules generating the covering projections. It was remarked at the end of the above paper that the covering graphs arising from these covering projections need not themselves be semisymmetric (a graph with regular valency is said to be semisymmetric if its automorphism group is edge- but not vertex-transitive). In this paper it is shown that all these covering graphs are indeed semisymmetric.     

An infinite family of tetravalent half-arc-transitive graphs

A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, a new infinite family of tetravalent half-arc-transitive graphs with girth 4 is constructed, each of which has order 16m such that m>1 is a divisor of 2t²+2t+1 for a positive integer t and is tightly attached with attachment number 4m. The smallest graph in the family has order 80.     

The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis, I

We compute the number of rhombus tilings of a hexagon with sidesN,M,N, N,M,N, which contain a fixed rhombus on the symmetry axis that cuts through the sides of lengthM.     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

Farthest points and cut loci on some degenerate convex surfaces

We study farthest points and cut loci on doubly covered convex polygons, and determine them explicitly on doubly covered n-dimensional simplices.     

On tile-k-transitive tilings of the space

General methods for finding tile-k-transitive tilings of the three-dimensional Euclidean space with polyhedral bodies are discussed. Analogous methods for enumerating k-isohedral tilings of a two-dimensional plane of constant curvature have been obtained previously.     

Search for properties of the missing Moore graph

In the degree-diameter problem, the only extremal graph the existence of which is still in doubt is the Moore graph of order 3250, degree 57 and diameter 2. It has been known that such a graph cannot be vertex-transitive. Also, certain restrictions on the structure of the automorphism group of such a graph have been known in the case when the order of the group is even. In this paper we further investigate symmetries and structural properties of the missing Moore (57, 2)-graph(s) with the help of a combination of spectral, group-theoretic, combinatorial, and computational methods. One of the consequences is that the order of the automorphism group of such a graph is at most 375.     

The nonexistence of 8-transitive graphs

We prove that the inequalitys≦7 holds for finites-transitive graphs assuming that the list of known 2-transitive permutation groups is complete.     

The graph induced by affine <Emphasis Type="Italic">M</Emphasis>-flats over finite fields II

Let AG(n, F _q) be the n-dimensional affine space over F _q, where F _q is a finite field with q elements. Denote by Γ ^(m) the graph induced by m-flats of AG(n, F _q). For any two adjacent vertices E and F of is studied. In particular, sizes of maximal cliques in Γ ^(m) are determined and it is shown that Γ ^(m) is not edge-regular when m<n−1. Supported by the National Natural Science Foundation of China (19571024) and Hunan Provincial Department of Education (02C512).     

On automorphism groups of Cayley graphs

LetX _G,H denote the Cayley graph of a finite groupG with respect to a subsetH. It is well-known that its automorphism groupA(X_G,H) must contain the regular subgroupL _G corresponding to the set of left multiplications by elements ofG. This paper is concerned with minimizing the index [A(X_G,H)L_G] for givenG, in particular when this index is always greater than 1. IfG is abelian but not one of seven exceptional groups, then a Cayley graph ofG exists for which this index is at most 2. Nearly complete results for the generalized dicyclic groups are also obtained.     

Factorial regular representation of groups in complete graphs

A necessary and sufficient condition for the group of isomorphisms involved in a factorization of a complete graph into isomorphic factors is established.