 Open Journal of Discrete Mathematics, 2013, 3, 183-191 http://dx.doi.org/10.4236/ojdm.2013.34032 Published Online October 2013 (http://www.scirp.org/journal/ojdm) Graph Derangements* Pete L. Clark University of Georgia, Athens, USA Email: plclark@gmail.com Received June 25, 2013; revised July 15, 2013; accepted August 10, 2013 Copyright © 2013 Pete L. Clark. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT We introduce the notion of a graph derangement, which naturally interpolates between perfect matchings and Hamilto- nian cycles. We give a necessary and sufficient condition for the existence of graph derangements on a locally finite graph. This result was first proved by W. T. Tutte in 1953 by applying some deeper results on digraphs. We give a new, simple proof which amounts to a reduction to the (Menger-Egerváry-König-)Hall(-Hall) Theorem on transversals of set systems. We also consider the problem of classifying all cycle types of graph derangements on m × n checkerboard graphs. Our presentation does not assume any prior knowledge in graph theory or combinatorics: all definitions and proofs of needed theorems are given. Keywords: Graph Derangement Cycle Perfect Matching 1. Introduction 1.1. The Cockroach Problem An interesting problem was conveyed to me at the Normal Bar in Athens, GA. The following is a mathe- matically faithful rendition, although some of the details may be misremembered or mildly embroidered. Consider a square kitchen floor tiled by 255 5 square tiles in the usual manner. Late one night the house’s owner comes down to discover that the floor is crawling with cockroaches: in fact each square tile contains a single cockroach. Displeased, she goes to the kitchen cabinet and pulls out an enormous can of roach spray. The roaches sense what is coming and start skitter- ing. Each roach has enough time to skitter to any adjacent tile. But it will not be so good for two (or more) roaches to skitter to the same tile: that will make an obvious target. Is it possible for the roaches to perform a collective skitter such that each ends up on its own tile? This is a nice problem to give undergraduates: it is concrete, fun, and far away from what they think they should be doing in a math class. 1.2. Solution Suppose that the tiles are painted black and white with a checkerboard pattern, and that the center square is black, so that there are 13 black squares and 12 white squares. Therefore there are 13 roaches who start out on black squares and are seeking a home on only 12 white squares. It is not possible—no more than for pigeons!—for all 13 cockroaches to end up on different white squares. 1.3. A Problem for Mathematicians For a grown mathematician (or even an old hand at mathematical brainteasers), this is not a very challenging problem, since the above parity considerations will quickly leap to mind. Nevertheless there is something about it that encourages further contemplation. There were several other mathematicians at the Normal Bar and they were paying attention too. “What about the 66 case?” One of them asked. “It reminds me of the Brou- wer fixed point theorem,” muttered another1. One natural follow-up is to ask what happens for cockroaches on an mn rectangular grid. The preced- ing argument works when and are both odd. On the other hand, if e.g. mmn n2 it is clearly possible for the cockroaches to skitter, and already there are several different ways. For instance, we could divide the rectangle into two dominos and have the roaches on each domino simply exchanging places. Or we could simply have them proceed in a (counter)clockwise cycle. Dominos are a good idea in general: if one of and is even, then an mnmn rectangular grid may be tiled 1Unfortunately, a connection with Brouwer’s theorem is not achieved here, but see . *Thanks to Mariah Hamel, Josh Laison, and the Math Department at Willamette University. Copyright © 2013 SciRes. OJDM P. L. CLARK 184 with dominos, and this gives a way for the roaches to skitter. Just as above though this feels not completely satisfactory and one naturally looks for other skittering patterns: e.g. when , one can have the roaches in the inner square skittering clockwise as before and then roaches in the outer ring of the square skittering around in a cycle: isn’t that more fun? There are many other skittering patterns as well. 4mnV1vvv22EI found considerations like the above to be rather interesting (and I will come back to them later), but for me the real problem was a bit more meta: what is the mathematical structure underlying the Cockroach Pro- blem, and what is the general question being asked about this structure? Here we translate the Cockroach Problem into graph- theoretic terms. In doing so, we get a graph theoretic problem which in a precise sense interpolates between two famous and classic problems: existence of perfect matchings and existence of Hamiltonian cycles. On the other hand, the more general problem does not seem to be well known. But it’s interesting, and we present it here: it is the existence and classification of graph derangements. 2. Graph Derangements and Graph Permutations 2.1. Basic Definitions Let be a simple, undirected graph: that is, we are given a set of vertices and a set of edges, which are unordered pairs of distinct elements of . For , we say that and 2 are adjacent if and write 12. In other words, for a set , to give a graph with vertex set is equivalent to giving an anti-reflexive, symmetric binary relation on , the adjacency relation. A variant formalism is also useful: we may think of a graph as a pair of sets ,GV12 V12vv EEV,vv,VvVV,VE and an incidence relation on V. Namely, for ExV and , eEx is incident to if exe, or, less formally, if x is one of the two vertices comprising the endpoints of . If one knows the incidence relation as a subset of then one knows in particular for each the pair of vertices 12 which are incident to and thus one knows the graph . eVE,GVE,EEvVeE,vv GFor and , the degree of is the number of edges which are incident to . A degree zero vertex is isolated; a degree one vertex is pendant. vvA graph is finite if its vertex set is finite (and hence its edge set is finite as well). A graph is locally finite if every vertex has finite degree. If and GV,EGV are graphs with , we say is an edge subgraph of : it has the same underlying vertex set as G and is obtained from by removing some edges. If GV and EEGG G,E,GVE are finite graphs with V and VE equal the set of all elements of linking two vertices in EV, we say G is an induced subgraph of . GFor a graph ,GVE, a subset XV is in- dependent if for no 12,xxX do we have 12xx. Example 2.1: For , we define the checker- board graph ,mn. Its vertex set is ,mnRmn1,,, 1,, and we decree that ,2,121xxyy if 11xy 2 21xy. Example 2.2: More generally, for and 1n,,mmn1,,nmmR we may define an n-dimensional an- alogue of . Its vertex set is ,mnR11,ni,im, and we decree that 11,,mm,,xxyy if 1Example 2.3: For we define the cylinder checkerboard graph ,mn. This is a graph with the same vertex set as and having edge set consisting of all the edges of ,mn together with 1miiixy1n. 2,C,mnRRm,,1xnx for all 1xm. We put ,1m, the cycle graph. The checkerboard graph is an edge subgraph of . mC,mnR,2mnC,Example 2.4: For we define the torus checkerboard graph ,mn. Again it has the same vertex set as ,mn and contains all of the edges of together with the following ones: for all 1mnCTR,mnRxm, ,xn,1x and for all 1yn, 1,y,myT. The cylinder checkerboard graph ,mn is an edge subgraph of the torus checkerboard graph . C,mnFor a graph ,EGV and xV, we define the neighborhood of x as xNyVx y. More generally, for any subset XV we define the neigh- borhood o f X as  such that xxXNNXy VxXxy . Remark 2.5: Although ,xxNX and NX need not be disjoint. In fact, iff XNXX is an independent set. Now the “cockroach skitterings” that we were asking about on can be formulated much more generally. Let ,mnR,GVE be a graph. A graph derangement of is an injection G:fVV such that fvv for all vV. Let be the set of all graph derange- ments of . DerGGExample 2.6: If nGK is the complete graph on the vertex set 1, ,nn, then a graph permutation of is nothing else than a permutation of Gn. A derangement of nK is a derangement in the usual sense, i.e., a fixed-point free permutation. Derangements exist iff and the number of them is asymptotic to >1n!ne as . nIt is natural to also consider a slightly more general definition. Copyright © 2013 SciRes. OJDM P. L. CLARK 185For a graph , a graph permutation of is an injection ,GVE:GfVV such that for all vV, either fvv or fvvVvG. Let be the set of all graph permutations of . Thus a graph derange- ment is precisely a graph permutation which is fixed point free: for all , PermGfvv. Lemma 1 Let be a graph. ,GVE1) If has an isolated vertex, . GDerG2) If has two pendant vertices adjacent to a com- mon vertex, . GDerGProof. Left to the reader as an exercise to get com- fortable with the definitions. Remark 2.7: If is an edge subgraph of G, any graph derangement (resp. graph permutation) G of G is also a graph derangement (resp. graph permutation) of . G2.2. Cycles and Surjectivity Given a graph , we wish not only to decide whether is nonempty but also to study its structure. The collection of all derangements on a given graph is likely to be a very complicated object: consider for instance GDerGDer nK, which has size asymptotic to !ne. Just as in the case of ordinary permutations and derangements, it seems interesting to study the possible cycle types of graph derangements and graph permutations on a given graph . Let us give careful definitions of these. GFirst, let be a set and V:fVV an function. For , let mmff f be the mth iterate of f. We introduce a relation on as follows: for V,xyV, xyn iff there are such that ,mn mfxfy. This is an equivalence relation on : the reflexivity and the symmetry are immediate, and as for the transitivity: if V,,xyzV are such that xy and then there are abc with yz,,,dabfxfy and cdfyfaczc a, and then .bc bd bdc bbcfxf fxf fyfyffy ffz fz Now suppose f is injective: we now call the -equi- valence classes cycles. Let xV, and denote the cycle containing x by xC. Then:  xC is finite iff x lies in the image of f and there is m such that mfxx.  xC is singly infinite iff it is infinite and there are yV, m such that mfyx and y is not in the image of f.  xC is doubly infinite iff it is infinite and every xyC lies in the image of f. These cases are mutually exclusive and exhaustive, so f is surjective iff there are no singly infinite cycles. Suppose ,GVE is a graph and PermfG. We can define the cycle type of f as a map from the set of possible cycle types into the class of cardinal numbers. When V is finite, this amounts to a partition of in the usual sense: e.g. the cycle type of roaches skittering counterclockwise on a #V55 grid is . A graph permutation is a graph derangement if it has no -cycles. We will say a graph derangement is matchless if it has no 2-cycles. 11,8,16Proposition 2 Suppose that a graph G admits a graph derangement. Then G admits a surjective graph derange- ment. Proof. It is sufficient to show that any graph derange- ment can be modified to yield a graph derangement with no singly infinite cycles, and for that it suffices to con- sider one singly infinite cycle, which may be viewed as the derangement 1nn on the graph  with 1nn for all n,212n. This derangement can be decomposed into an infinite union of 2-cycles: 12,34, ,n. 2.3. Disconnected Graphs Proposition 3 Let be a graph with components GiGiI, and let PermfG. 1) For all iiG,iIf G. 2) Conversely, given graph permutations if on each i, G:iiIffGDerGDeri is a graph permutation. More- over ifGfG for all . iIEThe proof is immediate. Thus we may as well restrict attention to connected graphs. 2.4. Bipartite Graphs A bipartition of a graph is a partition 12 of the vertex set such that each iV is an independent set. A graph is bipartite if it admits at least one bipartition. ,GVVV VFor k, a k-coloring of a graph E,GV is a map :1,,kCV such that for all ,xyV, xyCxCy22G. There is a bijective corres- pondence between -colorings of and bipartitions of : given a -coloring we define GCVxVCxii, and given a bipartition we define iCx if ixV. Thus a graph is bipartite iff it admits a 2-coloring. Remark 2.8: For a graph ,GVE, a map :0,CV1 is a 2-coloring of G iff its restriction to each connected component i is a 2-coloring of i. It follows that a graph is bipartite iff all of its connected components are bipartite. G GRemark 2.9: Any subgraph of a bipartite graph G is bipartite. Indeed, any 2-coloring of restricts to a 2-coloring of GGG. Example 2.10: The cycle graph is bipartite iff is even. mCmCopyright © 2013 SciRes. OJDM P. L. CLARK 186 Corollary 4 Let G be a bipartite graph, and let DerG. Then every finite cycle of  has even length. Proof. Since a subgraph of a bipartite graph is bipartite, a bipartite graph cannot admit a cycle of odd finite degree2. Example 2.11: 1) The n-dimensional checkerboard graph 1,,nmm admits a graph derangement iff are not all odd. R1,,nmm2) The cylinder checkerboard graphs ,mn all admit graph derangements. Hence, by Remark 2.7, so do the torus checkerboard graphs . C,mn3) For odd , the square checkerboard graph ,nn admits graph permutation with a single fixed point. For instance, by dividing the square into concentric rings we get a graph permutation with cycle type TnR11,8,16, ,82n. 3. Existence Theorems 3.1. Halls’ Theorems The main tool in all of our Existence Theorems is a truly basic result of combinatorial theory. There are several (in fact, notoriously many) equivalent versions, but for our purposes it will be helpful to single out two different formulations. Theorem 5 (Halls’ Theorem: Transversal Form) Let be a set and iI be an indexed family of finite subsets of . The following are equivalent: ViSV1) (Hall Condition) For every finite subfamily JI, ##iiJ.JS 2) ,VI admits a transversal: a subset XV and a bijection :fXI such that for all xX, fxxS. We will deduce Theorem 5 from the following refor- mulation. Theorem 6 (Halls’ Theorem: Marriage Form) Let be a bipartitioned graph in which every has finite degree. The following are equivalent: 12,,GVVEvV11) (Cockroach Condition) For every finite subset of , . 1V11##VNV2) There is a semiperfect matching, that is, an in- jection 12:VV such that for all 1xV, xxV. Proof. We follow . Step 1: Suppose is finite. We go by induction on . The case 1 is trivial. Now suppose that 1 and that the result holds for all bipartitioned graphs with first vertex set of car- dinality smaller than . It will be notationally con- venient to suppose that , and we do so. 1#V#Vnn1#VnCase 1: Suppose that for all , every - element subset of 1 has at least neighbors. Then we may match n to any element of 2V and semi- perfectly match 11,V,2Conversely, a graph with no cycles of odd degree is bipartite, a famous result of D. König. Copyright © 2013 SciRes. OJDM P. L. CLARK 187Remark 3.3: The generalization to arbitrary index sets was given by Marshall Hall Jr. , whence “Halls’ Theorem” (i.e., the theorem of more than one Hall). Remark 3.4: M. Hall Jr.’s argument used Zorn’s Lemma, which is equivalent to the Axiom of Choice (AC). The proof supplied above uses Tychonoff’s Theo- rem, which is also equivalent to (AC) . However, all of our spaces are Hausdorff. By examining the proof of Tychonoff’s Theorem using ultrafilters , one sees that when the spaces are Hausdorff, by the uniqueness of limits one does not need (AC) but only that every filter can be extended to an ultrafilter (UL). In turn, (UL) is equivalent to the fact that every Boolean ring has a prime ideal (BPIT). (BPIT) is known to be weaker than (AC), hence Halls’ Theorem cannot imply (AC). Question 1 Does Halls’ Theorem imply the Boolean Prime Ideal Theorem? Remark 3.5: The use of compactness of a product of finite, discrete spaces is a clue for the cognoscenti that it should be possible to find a nontopological proof using the Compactness Theorem from model theory. The reader who is interested and knowledgeable about such things will enjoy doing so. The Compactness Theorem (and also the Completeness Theorem) is known be equi- valent to (BPIT). Example 3.6 (, pp. 288-289): Let 1 be the set of non-negative integers and let 2V be the set of positive integers. For all positive integers 1VxV, we decree that x is adjacent to the corresponding positive integer in 2 and to no other elements of 2. However, we decree that 1 is adjacent to every element of . It is clear that there is no semiperfect matching, because if we match 0 to any 2, then the corresponding element 1 cannot be matched. But the Cockroach Condition holds: for a finite subset 1VnV0VVYnVXV, if 0X then 1#NV 1#V, whereas if 0X then 12VNV. 3.2. The First Existence Theorem Theorem 7 Consider the following conditions on a graph ,GVEDerG : (D) . (H) For all subsets XV, ##XNX. (H′) For all finite subsets XV, ##XNX. 1) Then (D) (H) (H′).  2) If is locally finite, then (H′) (D) and thus (D) (H) (H′). G Proof. a) (D) (H): If DerG and XV, then :VV is an injection with XNX. Thus ##XNX. (H) (H′) is immediate. G3) (H′) (D) if is locally finite: for each xV, let xx, and let SNxxV. Since G is locally finite, ISI is an indexed family of finite subsets of . By assumption, for any finite subfamily VJI, #### :xixJ iJJNJNS this is the Hall Condition. Thus by Theorem 5, there is XV and a bijection such that for all :fX VxX, fxxN, i.e., xfx. Let 1:fVX. Then for all yV, yf yy, so DerG. Remark 3.7: Example 3.3 shows (H) need not imply (D) without the assumption of local finiteness. The graph with vertex set and such that every x is adjacent to every integer satisfies (H′) but not (H). >nxLemma 8 Let be a locally finite graph which violates the cockroach condition: there is a finite subset GXVG such that #>#XNXYX. Then there is an independent subset such that #>#YNY. Proof. Let be the subset of all vertices which are not adjacent to any element of YXX, so is an in- dependent set. Put 1Y#mY, 2, and \mXY#12nmm #X . By hypothesis, #