 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. m mn n 2 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 m nmn rectangular grid may be tiled 1Unfortunately, a connection with Brouwer’s theorem is not achieved here, but see [1]. *Thanks to Mariah Hamel, Josh Laison, and the Math Department at Willamette University. C opyright © 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 V 1 v vv 22 E I 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 12 vv E EV ,vv , V v VV ,VE and an incidence relation on V. Namely, for E V and , eE is incident to if e e , or, less formally, if 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 . e V E ,GVE ,E E vV eE ,vv G For 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. v v A 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 E G G G ,E ,GVE are finite graphs with V and V E equal the set of all elements of linking two vertices in E V , we say G is an induced subgraph of . G For a graph ,GVE, a subset V is in- dependent if for no 12 , xX do we have 12 x. Example 2.1: For , we define the checker- board graph ,mn. Its vertex set is ,mn R mn1,,, 1,, and we decree that , 2 , 121 xyy if 11 xy 2 2 1xy . Example 2.2: More generally, for and 1 n ,,mm n 1,, n mm R we may define an n-dimensional an- alogue of . Its vertex set is ,mn R 11, n i,i m , and we decree that 11 ,, mm ,, xyy if 1 Example 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 1 m ii ixy 1n . 2, C ,mn RR m ,,1 nx for all 1 m . We put ,1m , the cycle graph. The checkerboard graph is an edge subgraph of . m C ,mn R ,2 mn 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 1 mn C T R,mn R m , , n,1x and for all 1 n, 1,y,my T . The cylinder checkerboard graph ,mn is an edge subgraph of the torus checkerboard graph . C ,mn For a graph ,EGV and V, we define the neighborhood of x as x NyVx y. More generally, for any subset V we define the neigh- borhood o f X as such that xX NNXy VxXxy . Remark 2.5: Although , x NX and NX need not be disjoint. In fact, iff XNX is an independent set. Now the “cockroach skitterings” that we were asking about on can be formulated much more generally. Let ,mn R ,GVE be a graph. A graph derangement of is an injection G: VV such that vv for all vV . Let be the set of all graph derange- ments of . DerG G Example 2.6: If n GK is the complete graph on the vertex set 1, ,nn, then a graph permutation of is nothing else than a permutation of G n. A derangement of n 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!n e as . n It is natural to also consider a slightly more general definition. Copyright © 2013 SciRes. OJDM  P. L. CLARK 185 For a graph , a graph permutation of is an injection ,GVE : G VV such that for all vV , either vv or v vV v G . 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 , PermG vv. Lemma 1 Let be a graph. ,GV E 1) If has an isolated vertex, . GDerG 2) If has two pendant vertices adjacent to a com- mon vertex, . G DerG 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 . G 2.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 G DerG Der n , which has size asymptotic to !n e. 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. G First, let be a set and V: VV an function. For , let m m f f be the mth iterate of . We introduce a relation on as follows: for V , yV, y n iff there are such that ,mn m xfy . This is an equivalence relation on : the reflexivity and the symmetry are immediate, and as for the transitivity: if V ,, yzV are such that y and then there are abc with yz,,,d ab xfy and cd yf ac z c a , and then . bc bd bd c bbc xf fxf fyfy fy ffz fz Now suppose f is injective: we now call the -equi- valence classes cycles. Let V , and denote the cycle containing by C. Then: C is finite iff lies in the image of and there is m such that m xx . C is singly infinite iff it is infinite and there are V, m such that m yx and y is not in the image of . C is doubly infinite iff it is infinite and every yC lies in the image of . These cases are mutually exclusive and exhaustive, so f is surjective iff there are no singly infinite cycles. Suppose ,GVE is a graph and Perm G. 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 #V 55 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. 1 1,8,16 Proposition 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 i GiI , and let Perm G . 1) For all ii G,iIf G . 2) Conversely, given graph permutations i on each i, G: i iI fG Der G Der i is a graph permutation. More- over i GfG for all . iI E The 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 i V 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,,kCV such that for all , yV , yCxCy 2 2 G . There is a bijective corres- pondence between -colorings of and bipartitions of : given a -coloring we define G C VxVCxi i , and given a bipartition we define iCx if i V . Thus a graph is bipartite iff it admits a 2-coloring. Remark 2.8: For a graph ,GVE , a map :0,CV1 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 G Remark 2.9: Any subgraph of a bipartite graph G is bipartite. Indeed, any 2-coloring of restricts to a 2-coloring of G G G . Example 2.10: The cycle graph is bipartite iff is even. m Cm Copyright © 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,, n mm admits a graph derangement iff are not all odd. R 1,, n mm 2) The cylinder checkerboard graphs ,mn all admit graph derangements. Hence, by Remark 2.7, so do the torus checkerboard graphs . C ,mn 3) 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 T nR 1 1,8,16, ,82 n . 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 i S V 1) (Hall Condition) For every finite subfamily I, ## i iJ . S 2) ,VI admits a transversal: a subset V and a bijection : XI such that for all X , x S. 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 1 1) (Cockroach Condition) For every finite subset of , . 1 V 11 ##VNV 2) There is a semiperfect matching, that is, an in- jection 12 :VV such that for all 1 V, x V. Proof. We follow [2]. 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 n 1 #V n Case 1: Suppose that for all , every - element subset of 1 has at least neighbors. Then we may match n to any element of 2 V and semi- perfectly match 1<kn 1kk V , 1n1, into the remaining ele- ments of by induction. 2 Case 2: Otherwise, for some , , there is a -element subset 1 Vk1<k n k V such that #NXk . The subset may be semiperfectly matched into 2 V by induction, say via 12 : V , so it suffices to show that the Hall Condition still holds on the induced biparti- tioned subgraph on X 12 \,V1. Indeed, if not, then for some h, \ k VX 1hn ha , there would be an h- element subset Yving fewer than h neig bors in 1\VX h- 21 \V en ), but thX ## ## #. NX YNXNYNXNY kh XY Step 2: Suppose is infinite. For 1 V1 V, endow N with the discrete topology; endow 1 xV NN with the product topology. Each Nx is finite hence com- pact, so N is compact by Tychonoff’s Theorem. For any finite subset 1 V, let ,. Xixy nn NnnxyX Then X is closed in and is nonempty by Step 1. Since is compact, there is , and any such is a semiperfect matching. N GX X nH n Remark 3.1: Theorems 5 and 6 are equivalent results: Assume Theorem 5. In the setting of Theorem 6, take 2 VV , 1 V and x I. The local finiteness of the graph means each element of is finite, and the assumed Cockroach Condition is precisely the Hall Condition, so by Theorem 5 there is N 2 V and a bijection such that :fX I Xf xN. Let 1 1 : V X . Then for , let 1 Vy x , so fy yx . Assume Theorem 6. In the setting of Theorem 5 take 1 VI , 2 VV , and the set of pairs E ,ix such that i S . Since each i is finite, the graph is locally finite, and the assumed Hall Condition is precisely the Cockroach Condition, so by Theorem 6 there is a semi- perfect matching S : V . Let fI, and let be the inverse function. For :fX I X , if xif, i , so i x xSS . Remark 3.2: Theorem 5 was first proved for finite by Philip Hall [3]. Eventually it was realized that equi- valent or stronger versions of P. Hall’s Theorem had been proven earlier by Menger [4], Egerváry [5] and König [6]. The matrimonial interpretation was introduced some years later by Halmos and Vaughan [2]. Never- theless, with typical disregard for history the most com- mon name for the finite form of either Theorem 5 or 13 is Hall’s Marriage Theorem. 1 1> 1, V , 2Conversely, a graph with no cycles of odd degree is bipartite, a famous result of D. Köni . Copyright © 2013 SciRes. OJDM  P. L. CLARK 187 Remark 3.3: The generalization to arbitrary index sets was given by Marshall Hall Jr. [7], 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) [8]. However, all of our spaces are Hausdorff. By examining the proof of Tychonoff’s Theorem using ultrafilters [9], 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 ([10], pp. 288-289): Let 1 be the set of non-negative integers and let 2 V be the set of positive integers. For all positive integers 1 V V, we decree that 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 1 V n V 0V V Y nV V, if 0 then 1 #NV 1 #V, whereas if 0 then 12 VNV . 3.2. The First Existence Theorem Theorem 7 Consider the following conditions on a graph ,GVE DerG : (D) . (H) For all subsets V, ## NX. (H′) For all finite subsets V, ## NX. 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 V, then :VV is an injection with NX . Thus ## NX . (H) (H′) is immediate. G 3) (H′) (D) if is locally finite: for each V, let x, and let SN x V. Since G is locally finite, IS is an indexed family of finite subsets of . By assumption, for any finite subfamily V I, #### : i xJ iJ NJNS this is the Hall Condition. Thus by Theorem 5, there is V and a bijection such that for all :fX V X , x xN , i.e., fx. Let 1: VX . Then for all V, 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). >nx Lemma 8 Let be a locally finite graph which violates the cockroach condition: there is a finite subset G VG such that #># NX YX . 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 YX , so is an in- dependent set. Put 1 Y #mY , 2, and \mX Y# 12 nmm #X . By hypothesis, #<NX n12 m m ; since \\ YNXNY, we find 12 #<NYmm2 1 Combining Proposition 2, Theorem 7 and Lemma 8 we deduce the following result. <#m Ym . Theorem 9 (First Existence Theorem) For a locally finite graph, the following are equivalent: 1) For every finite independent set in , G ## NXG. 2) admits a surjecti ve gra ph dera ngement. Remark 3.8: Theorem 9 was first proved by W.T. Tutte ([11], 7.1). Most of Tutte’s paper is concerned with related—but deeper—results on digraphs. The result which is our Theorem 9 appears at the end of the paper and is proven by passage to an auxiliary digraph and reduction to previous results. Perhaps because this was not the main focus of [11], Theorem 9 seems not to be well known. In particular, our observation that one need only apply Theorem 5 appears to be new. 3.3. Bipartite Existence Theorems A matching on a graph is a subset such that no two edges in share a common vertex. A matching is perfec t if every vertex of is incident to exactly one edge in . ,VGE E G A graph permutation is dyadic if all of its cycles have length at most 2. Proposition 10 Let be a graph. G 1) Matchings of correspond bijectively to dyadic graph permut a t i ons . G 2) Under this bijection perfect matchings correspond to dyadic graph derangements. Proof. 1) Let be a matching. We define E SymV as follows: if incident to the edge Copyright © 2013 SciRes. OJDM  P. L. CLARK 188 ,exy, we put y . Otherwise we put x . This is well-defined since by definition every vertex is incident to at most one edge and gives rise to a dyadic graph permutation. Conversely, to any dyadic graph per- mutation SymV , let V be the subset of ver- tices which are not fixed by and put , xX x . Then and are mutually inverse. 2) A matching is perfect iff every vertex V is incident to an edge of iff the permutation E is fixed-point free. ,,GVV 12 ,VVE ,,E Let 12 be a bipartitioned graph. A semi- perfect matching on G is a matching such that every vertex of 1 is incident to exactly one ele- ment of . Thus a subset is a perfect match- ing on iff it is a semiperfect matching on both and on . E V VV G ,,VVE 12 21 A semiderangement of 12 is an in- jective function ,,VGV E 21 :VV such that x for all 1 V . But in fact we have defined the same thing twice: a semiderangement of a bipartitioned graph is nothing else than a semiperfect matching. Theorem 11 (Semiderangement Existence Theorem) Consider the following conditions on a bipartitioned graph : E 12 (SD) There is an injection ,,GVV 1 V 2 :V such that for all 1 V, x . (H) For every finite subset 1 V, ## NJ. Then (SD) (H), and if G is locally finite, (H) (SD). Proof. This is precisely Theorem 6 stated in the language of semiderangements. Theorem 12 (Königs’ Theorem) Let 12 ,,VE 2 V GV 11 :V be a bipartitioned graph, which need not be locally finite. Suppose there is a semiderangement V of and a semiderangement 221 12 ,,VVE :V of 21 . Then admits a perfect matching, i.e., a bijection such that ,,VVE 1 :fV G 2 V fx for all 1 V. Proof. Let 12 . Then 12 is a graph derangement. The injection VVV :V V partitions V into finite cycles, doubly infinite cycles, and singly infinite cycles. For each cycle C which is finite or doubly infinite, 11 2 :CV CV and 221 :CV CV are bijections. Thus if there are no singly infinite cycles, taking 1 f we are done. If C is a singly infinite cycle, it has an initial vertex 1 . If 11 V, then 211 :CV CV 2 is surjective; the problem occurs if 1 V: then 1 does not lie in the image of 1 . We have 1 221 xV , 312 2 x V, and so forth. So we can repair matters by defining 1 on 24 by 21 ,,xx x, 43 x, and so forth. Doing this on every singly infinite cycle with initial vertex lying in V2 a bijection 1. Moreover, since 2 :fV V2 is a semi- derangement and 21 2nn x for all n , we have 2212nnn xx V xf 1 V , so is a bijection. Remark 3.9: Suppose and 2 are sets and 112 V :V and 221 :VV are injections between them. If we apply Theorem 12 to the bipartitioned graph on 12 ,VV in which 121 VyV xy or 2 x , we get a bijection 12 : this is the celebrated Cantor-Bernstein Theorem. As a proof of Cantor-Bernstein, this argument was given by Gyula (“Julius”) König [12] and remains to this day one of the standard proofs. His son Dénes König explicitly made the connection to matching in infinite graphs in his seminal text [13]. :fV V Theorem 13 (Second Existence Theorem) Let 12 ,,VEGV G G G be a locally finite bipartitioned graph. The following are equivalent: 1) admits a perfect matching. 2) admits a dyadic graph derangement. 3) admits a gr ap h de rangem en t . 4) For every subset V, ## NJ. Proof. 1) 2) by Proposition 10. 2) 3) is immediate. 3) 4) is the same easy argument we have already seen. 4) 1): By Theorem 11, we have semiderange- ments 112 :VV and 1 V 22 :V . By Theorem 12 this gives a perfect matching. Remark 3.10: The equivalence 1) 4) above is due to R. Rado [14]. 3.4. An Equivalence Theorems 9 and 13 are “equivalent” in the sense that they were proved using equivalent formulations of Halls’ Theorem (together with, in the case of Theorem 13, a Cantor-Bernstein argument). In this section we will show their equivalence in a stronger sense: each can be rapidly deduced from the other. Assume Theorem 9, and let be a locally finite bipartitioned graph satisfying the Cock- roach Condition: for all finite independent subsets 12 12 ,,VEGV V V#NJ , . Then Theorem 9 applies to yield a surjective graph derangement f. A cycle admits a dyadic graph derangement iff it is not finite of odd length; since G is bipartite, no cycle in f is finite of odd length. Thus decomposing f cycle by cycle yields a dyadic graph derangement. #JC Assume Theorem 13, and let ,GVE be a locally finite graph satisfying the Hall Condition: for all finite independent subsets V#NJ, . Let #J 22 ,,VE V 21 GV VV be the bipartite double of : we put 12 G . For V , let 1 (resp. 2 ) denote the copy of in (resp. ). For every 1 V2 V ,exyE, Copyright © 2013 SciRes. OJDM  P. L. CLARK 189 we give ourselves edges 12 122 ,,, yyxE GG 2 f . Then 2 is locally finite bipartitioned, and it is easy to see that the Hall Condition in implies the Cockroach Condition in 2. By Theorem 13, 2 admits a dyadic graph derangement . From we construct a graph derangement of : for G G f2 fG V1 , let be the corresponding element of 1; let V 221 fxy, and let be the element of corresponding to 2. Then we put y V xy. It is immediate to see that is a graph derangement of . It need not be surjective, but no problem if it isn’t: apply Proposition 2. f G Remark 3.11: Our deduction of Theorem 9 from Theorem 13 is inspired by an unpublished manuscript of L. Levine [15]. Remark 3.12: Recall that Theorem 13 implies the Cantor-Bernstein Theorem. The above equivalence thus has the following curious consequence: Cantor-Bernstein follows almost immediately from the transversal form of Halls’ Theorem. 3.5. Dyadic Existence Theorems One may ask if there is also an Existence Theorem for dyadic derangements in non-bipartite graphs. The answer is yes, a quite celebrated theorem of Tutte. A later result of C. Berge gives information on dyadic graph per- mutations. Let be a graph. For a subset ,GVE V, we denote by the induced subgraph with vertex set . \GX \VX Theorem 14 (Third Existence Theorem) For a finite graph , TFAE: ,GVE G 1) has a dya dic gra p h dera ngement. 2) For every subset V, the number of connected components of with an odd number of vertices is at most \GX # . Proof. See [16]. Remark 3.13: Theorem 14 can be generalized to locally finite graphs: see [17]. A maximum matching of a finite graph G is a matching such that is maximized among all matchings of . Thus if admits a perfect matching, a matching is a maximum matching iff it is perfect, whereas in general the size of a maximum matching measures the deviation from a perfect matching in . # GG G For a finite graph , let odd be the number of connected components of with an odd number of vertices. Theorem 15 (Berge’s Theorem [18]) Let be any finite graph. The size of a maximum matching in is GG 1#odd(\)# min 2 GXV BXGXV . We immediately deduce the following result on dyadic graph permutations. Corolla ry 16 Let be a finite graph. Then the least number of fixed points in a dyadic graph permutation of is G G#2 G VB . 3.6. Matchless Graph Derangements Let ,GVE be a finite graph with . Then a graph permutation of cycle type is called a Hamil- tonian c y c l e (or Hamiltonian circuit). #Vn n From the perspective of graph derangements it is clear that Hamiltonian cycles lie at the other extreme from dyadic derangements and permutations. Here much less is known than in the dyadic case: there is no known Hamiltonian analogue of Tutte’s Theorem on perfect matchings, and in place of Berge’s Theorem we have the following open question. Question 2 Given a finite graph G, determine the largest integer such that admits a graph per- mutation of type nG ,1,,1n. Equivalen tly, deter mine the maximum order of a vertex subgraph of admitting a Hamiltonian cycle. G A general graph derangement is close to being a partition of the vertex set into Hamiltonian cycles, except that if x and y are adjacent vertices, then sending x to y and y to x meets the requirements of a graph derange- ment but does not give a Hamiltonian subcycle because the edge from x to y is being used twice. Let us say a graph derangement is matchless if each cycle has length at least 3. The above Existence Theorems lead us na- turally to the following question. Question 3 Is there an Existence Theorem for match- less graph derangements? As noted above, there is no known Existence Theorem for Hamiltonian cycles. Since a Hamiltonian cycle is a graph derangement of a highly restricted kind, one might hope that Question 3 is somewhat more accessible. 4. Checkerboards Revisited 4.1. Universal and Even Universal Graphs Let G be a graph on the vertex set 1, ,nn such that DerG . As in §2, it is natural to inquire about the possible cycle types of graph derangements (and also graph permutations) of G. We say G is uni- versal if for every partition of there is a graph derangement of with cycle type . For instance, the complete graph .2 pn pG n is (rather tautologously) universal. If and G is bipartite, by Corollary 4 G is not universal, because the only possible cycle types are even. Thus for graphs known to be bipartite the more interest- ing condition is that every possible even partition of 5n n G occurs as the cycle type of a graph derangement of : we call such graphs even un iversal. Copyright © 2013 SciRes. OJDM  P. L. CLARK 190 4.2. On the Even Universality of Checkerboard Graphs Proposition 17 For all n , the checkerboard graph is even universal. 2,n RProof. This is an easy inductive argument which we leave to the reader. Proposition 18 Let be an even number. Then: 4n 1) If are even numbers greater than 2 such 1,, k aa k that , then there is no graph derangem ent 1 4 i ia 3n of of cycle type . 3,n 2) It follows that is not even universal. R 1,,,4 k aa 3,n Proof. 1) A -cycle on any checkerboard graph must be a -square. By symmetry, we may assume that the -square is placed so as to occupy portions of the top two rows of ,mn. The two vertices immediately underneath the square cannot be part of any Hamiltonian cycle in the complement of the square, so any graph derangement containing a -cycle must also contain a -cycle directly underneath the -cycle. Thus the cycle type is excluded. R 4 4 4 22 22 aa n R 4 3n 2 4 1 2) Since is even, is even and at least , so there are even partitions of of the above form: if is divisible by 4; otherwise. ,,, k 12 , 4 3n 4, 4,,4 n 6, 4,4, Proposition 19 If is odd and is divisible by , then admits no graph derangement of cycle type and is therefore not even universal. m n 4,mn R 4,, 44, Proof. Left to the reader. Example 4.1 : There are 3,4 G12 11 2 p even partitions of 12. By Proposition 19, we cannot realize the cycle types , by graph derangements. We can realize the other nine: 8, 4 4, 4,4 12,10, 2,8, 2, 2,6, 6,6, 4, 2,6, 2, 2,2, 4, 4, 2, 2,4, 2, 2, 2, 2,2, 2, 2,2, 2,2. Example 4.2 : Of the 4,4 G16 22 2 p even parti- tions of , we can realize : 16 20 16,14, 2,12, 4,12, 2, 2,10, 4, 2,10, 2, 2,2, 8,8,8, 6, 2,8, 4, 4,8, 4, 2, 2, 8, 2, 2, 2,6, 6, 2, 2,6, 4, 4, 2,6, 4, 2, 2, 2, 6, 2, 2,2, 2,2,4,4,4, 4,4, 4, 4,2, 2, 4, 4, 2, 2,2, 2,4, 2, 2, 2, 2,2, 2,2, 2, 2,2, 2,2, 2, 2,2. We cannot realize: 10,6 ,6,6,4 . Indeed, the only order 6 cycle of a checkerboard graph is the checkerboard subgraph. Removing any 6- cycle leaves one of the corner vertices pendant and hence not part of any cycle of order greater than . 23 2 Example 4.3 3,6 G: There are 18 2 30p even partitions of . We can realize these 23 of them: 18 18, 16,2, 14,2,2, 12,6, 12,4, 12, 2, 2, 2,10,6, 2,10, 4, 2, 2, 2, 10,2,2,2,2 ,8,8,2 , 8,6,2,2 , 8,2,2 , 8, 2,2,2,2, 2, 2,6,6,6,6,6,4,2, ,4,2 6, 6, 2, 2, 2,6, 4, 4, 2, 2,6, 4, 2, 2,, 6, 2, 2,2, 2,2, 2,4, 4, 4,2, 2,2, 2, 2 4, 4, 2, 2, 2, 2, 2,4, 2, 2, 2,2,2, 2, 2 2, 2, 2, 2, 2, 2, 2, 2, 2. , We cannot realize the following ones: 14, 4,10,8,10, 4, 4,8, 6, 4 8, 4, 4, 2,6, 4, 4,4,4,4, 4,4 , , 2. Of these, all but 10,8 and 4, 4,24, 4, are ex- cluded by Proposition 18, and we leave it to the reader to check that these two “exceptional” cases cannot occur. Example 4.5 4,5 G: There are 20 2 42p even partitions of . We can realize of them. We cannot realize: 20 39 8,8, 4,8, 4, 4, 4,4, 4, 4, 4, 4. No 8,8, 4: to place a 4-cycle in 4,5 without leaving a pendant vertex, we must place it in a corner, without loss of generality the upper left corner. The only -cycle which can fit into the remaining lower left corner is the recantagular one, and this leaves a pendant vertex at the lower right corner. G 8 No 8, 4, 4, 4: Any placement of three -cycles in 4,5 gives two of them in either the top half or the bottom half, and without loss of generality the top half. Any such placement leaves a pendant vertex in the top row. 4 G No 4, 4, 4, 4,4: This follows from Proposition 19. Alternately, the argument of the previous paragraph works here as well. Example 4.6 ( 4,6 G): There are 24 12 77p even partitions of . They can all be realized by graph derangements: is even universal. 24 G4,6 By analyzing the above examples, we found the fol- lowing additional families of excluded cycle types. The proofs are left to the reader. Proposition 20 Let 21nk be an odd integer Copyright © 2013 SciRes. OJDM  P. L. CLARK Copyright © 2013 SciRes. OJDM 191 [7] M. Hall Jr., “Distinct Representatives of Subsets,” Bulle- tin of the American Mathematical Society, Vol. 54, No. 10, 1948, pp. 922-926. http://dx.doi.org/10.1090/S0002-9904-1948-09098-X greater than 1. Then 4,n admits no matchless graph derangemen t with or more -cycles. G 1 2k 4 Proposition 21 For any non-negative integer , admits no graph derangement of the cycle type . Thus these graphs are not even universal. k 4,6 4k G 6,6,,6, 4[8] J. L. Kelley, “The Tychonoff Product Theorem Implies the Axiom of Choice,” Fundamenta Mathematicae, Vol. 37, No. , 1950, pp. 75-76. Proposition 22 For any odd integer and mk, admits no graph derangement of the cycle type . Thus these graphs are not even universal. ,4 2mk G 6, 4,,[9] H. Cartan, “Théorie des Filtres,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 205, 1937, pp. 595- 598. 4 In particular, for ,mn to be even universal, it is necessary that m and n both are even. Proposition 21 shows that having m and n both even is not sufficient; however, we have found no examples of excluded even cycle types of ,mn when are both even and at least . Such considerations, and others, lead to the following conjecture, made by J. Laison in collaboration with the author. R [10] C. J. Everett and G. Whaples, “Representations of Se- quences of Sets,” American Journal of Mathematics, Vol. 71, No. 2, 1949, pp. 287-293. http://dx.doi.org/10.2307/2372244 R,mn 6[11] W. T. Tutte, “The 1-Factors of Oriented Graphs,” Pro- ceedings of the American Mathematical Society, Vol. 4, No. 6, 1953, pp. 922-931. Conjecture 23 There is a positive integer such that for all , the checkerboard graph is even universal. 0 N 2,k R[12] J. König, “Sur la Theorie des Ensembles,” Comptes Ren- dus de l’Académie des Sciences, Paris, Vol. 143, 1906, pp. 110-112. 0 N,kl2l [13] D. König, “Theorie der Endlichen und Unendlichen Gra- phen. Kombinatorische Topologie der Streckenkom- plexe,” Chelsea Publishing Co., New York, 1950. REFERENCES [14] R. Rado, “Factorization of Even Graphs,” Quarterly Jour- nal of Mathematics: Oxford Journals, Vol. 20, No. 1, 1949, pp. 95-104. [1] O. Knill, “A Brouwer Fixed Point Theorem for Graph Endomorphisms,” Fixed Point Theory and Applications, Vol. 2013, 2013, p. 85. [15] L. Levine, “Hall’s Marriage Theorem and Hamiltonian Cycles in Graphs,” 2001. [2] P. R. Halmos and H. E. Vaughan, “The Marriage Prob- lem,” American Journal of Mathematics, Vol. 72, No. 1, 1950, pp. 214-215. http://dx.doi.org/10.2307/2372148 [16] W. T. Tutte, “The Factorization of Linear Graphs,” Jour- nal of the London Mathematical Society, Vol. 22, No. 2, 1947, pp. 107-111. http://dx.doi.org/10.1112/jlms/s1-22.2.107 [3] P. Hall, “On Representatives of Subsets,” Journal of the London Mathematical Society, Vol. 10, No. 37, 1935, pp. 26-30. [17] W. T. Tutte, “The Factorization of Locally Finite Gra- phs,” Canadian Journal of Mathematics, Vol. 2, No. 1, 1950, pp. 44-49. http://dx.doi.org/10.4153/CJM-1950-005-2 [4] K. Menger, “Zur Allgemeinen Kurventheorie,” Funda- menta Mathematicae, Vol. 10, 1927, pp. 96-115. [5] E. Egerváry, “Matrixok Kombinatorius Tulajdonságai- rol,” Matematikai és Fizikai Lapok, Vol. 38, 1931, pp. 16- 28. [18] C. Berge, “Sur le Couplage Maximum d’un Graphe,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 247, 1958, pp. 258-259. [6] D. König, “Gráfok és Mátrixok,” Matematikai és Fizikai Lapok, Vol. 38, 1031, pp. 116-119.
|
