Perfect Matchings After Vertex Deletions in n-dimensional Lattice Graphs by Hangjun Yang B . S c , Zhejiang University, China, 2003 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M a s t e r o f Sc i ence in T H E F A C U L T Y O F G R A D U A T E STUDIES Mathematics The University of British Columbia August 2005 © Hangjun Yang, 2005 Abstract This thesis studies lattice graphs which are readily seen to have many perfect matchings and considers whether if we delete vertices the resulting graphs continue to have perfect matchings. It is clear that one can destroy the property of hav-ing a perfect matching by deleting an odd number of vertices, by deleting all the neighbours of a given vertex, etc. Besides these trivial "destructions", in order to guarantee the resulting graph still have perfect matchings, we require the deleted vertices to be mutually far apart. In this thesis, we consider an n-dimensional lattice graph Q(m, n) with bipartition of black and white vertices, where m is even. If the distance of any two deleted black (or white) vertices is greater than 4n(n + l)y/m, then the resulting graph (after vertex deletions) continues to have a perfect match-ing. Contents Abstract ii Contents iii List of Tables v List of Figures vi Acknowledgements vii 1 Background 1 1.1 Basic Concepts 1 1.2 Matchings 3 1.2.1. Matchings in Bipartite Graphs 3 1.2.2 Matchings in General Graphs 5 1.3 Networks and Flows 6 1.4 Capacitated Perfect 6-matchings and Bidirected Flows 8 2 Applications of Matchings 12 2.1 Applications of Matchings in Bipartite Graphs 12 2.1.1 The Assignment Problem 12 iii \ 2.1.2 The Dimer Problem 14 2.2 Applications of Matchings in General Graphs 16 2.2.1 The Chinese Postman Problem 16 2.2.2 Quadrilateral Mesh Generation in Computer-Aided Design . 17 3 Introduction of the Problem 19 3.1 Robustness 19 3.2 Motivation 20 3.3 Definitions and Notations 21 3.4 A Result in the 2-D Case 23 4 Main Result for n-dimensional Lattice Graphs 25 4.1 Statement of Theorem 4.1 25 4.2 Proof of Theorem 4.1 29 Bibliography 36 iv List of Tables 2.1 Tableau F o r m of the K a b u k i Electronics Assignment Problem . . . . 13 2.2 T h e Opt imal Assignment of the K a b u k i Electronics Assignment Prob-lem 14 v ' List of Figures 1.1 A pictorial representation of a graph 2 1.2 A matching M i and a perfect matching M^. 3 3.1 Q(m,2) gives an m x m lattice graph, here m = 20 22 4.1 A 2-D diamond with d = 8 in the checkerboard with m — 20 27 4.2 A sketch of a 3-D diamond 28 vi > Acknowledgements This thesis was conducted under the supervision of Dr. Richard Anstee. I would like to thank him for his guidance, advice and encouragement. H A N G J U N Y A N G The University of British Columbia August 2005 vii Chapter 1 Background This chapter mostly follows the terminology in the textbook Introduction to Graph Theory by West [31]. 1.1 Basic Concepts , When speaking of graphs we might think about pictures of some kind that are used to represent information such as bar graphs, flow charts and graphs of functions. But the graphs we shall discuss' are quite different. They correspond more closely with the objects which, in everyday language that we call "networks". A graph G with n vertices and m edges consists of a vertex set V(G) — {v\,... ,vn} and an edge set E(G) — { e i , . . . , e m } , where each edge consists of two (possibly equal) vertices in V(G) called its endpoints. We usually write G = (V(G), E(G)), or simply G — (V, E). A directed graph or digraph G consists of a vertex set V(G) and an edge set E(G), where each edge is an ordered pair of vertices. A loop is an edge whose endpoints are equal. Parallel edges or multiple edges are edges that have the same pair of endpoints. A simple graph is a graph having 1 a d c Figure 1.1: A pictorial representation of a graph no loops or multiple edges. A complete graph is a simple graph in which every pair of vertices is an edge. Denote a complete graph with n vertices by Kn. A graph is finite if its vertex set and edge set are finite. We emphasize here that every graph mentioned in this paper is finite. A typical example of a simple graph G = (V, E) is given by the sets V = {a, b, c, d, z}, E = {(a, b), (a, d), (b, z), (c, d), (d, z)}. We represent the vertices as points, and join two points by a line whenever the corresponding pair of vertices is an edge. Thus Figure 1.1 is a pictorial (or graphical) representation of the graph given in the example above. A walk of length k is a sequence VQ, e i , V\, e2, . • . , e ,^ of vertices and edges such that e{ — Vi-\Vi for all i. A path is a walk with no repeated vertex. A trail is a walk with no repeated edge. A walk (or trail) is closed if it has length at least one and its endpoints are equal. A walk vo, e\, v\, ei-, • • • > 6fc, vk whose vertices are all distinct except that VQ = is called a cycle. We call a cycle odd if it has an odd number of distinct vertices (and an odd number of edges). A walk specifies a route in G which proceeds through a sequence of vertices joined by edges. A walk may visit any vertex an arbitrary number of times. In a path, each vertex is visited at most once. A u,v-path is a path whose first vertex is 2 u and last vertex is v. A graph G is bipartite if V(G) is the union of two disjoint sets X and Y such that each edge consists of one vertex from X and one vertex from Y. We say G is a bipartite graph with bipartition X, Y. Here is an important fact about bipartite graphs. T h e o r e m 1.1 A graph G is bipartite if and only if it contains no odd cycles. Theorem 1.1 implies that whenever a graph G is not bipartite, we can prove this statement by presenting an odd cycle in G. 1.2 Matchings 1.2.1 Matchings in Bipartite Graphs A matching of size A; in a graph G is a set of k pairwise disjoint edges. The vertices belonging to the edges of a matching are saturated by the matching; the others are unsaturated. If a matching saturates every vertex of G, then it is a perfect matching. A maximum matching is a matching of maximum size. Figure 1.2: A matching Mi and a perfect matching Mi. In Figure 1.2 two matchings M\ and Mi in the same bipartite graph are 3 illustrated; the edges which belong to the matchings are indicated by dashed lines. In particular, My is a perfect matching. Given a matching M , an M-alternating path is a path that alternates between edges in M and edges not in M. A n M-alternating path P that begins and ends at M-unsaturated vertices is an M-augmenting path; replacing MC\E(P) by E(P) — M produces a new matching M' with one more edge that M. Maximum matchings are characterized by the absence of augmenting path, which was proven by in 1957. Theorem 1.2 (Berge [5])A matching M in a graph (not necessarily bipartite) G is a maximum matching in G if and only if G has no M-augmenting path. A vertex cover of G is a set S of vertices such that S contains at least one endpoint of every edge of G. The vertices in S "cover" the edges of G. The Konig-Egervary Theorem states an equality relation between maximum matching and minimum vertex covering in bipartite graphs. Theorem 1.3 (Konig [20], Egervdry [10]) If G is a bipartite graph, then the max-imum size of a matching in G equals the minimum size of a vertex cover of G. For any S C I , let N(S) denote the set of vertices having a neighbor in 5. If a matching M saturates X, it must be true that | iV(S)| > \S\. This is known as Hall's condition. In 1935, the mathematician Philip Hall proved that this obvious necessary condition is also sufficient. Theorem 1.4 (Hall [16]) If G is a bipartite graph with bipartition X,Y, then G has a matching M that saturates X if and only if | iV(5)| > \S\ for all S C X. When the sets of the bipartition have the same size, i.e., \X\ — \Y\, then G has a perfect matching under Hall's condition. 4 C o r o l l a r y 1.5 If G is a bipartite graph with bipartition X,Y and \X\ = \Y\, then G has a perfect matching if and only if | i V ( S ) | > |5| for all S C I . The degree of a vertex v in a graph G, written da(v) or d(v), is the number of non-loop edges containing v plus twice the number of loops containing v. The maximum degree is A(G) ; the minimum degree is 6(G). A graph G is regular if A(G) = 6(G); k-regular if A(G) = 6(G) = k. The "first" Theorem of graph theory tells us the sum of vertex degrees is twice the number of edges. Thus every graph has an even number of vertices of odd degree. If G is a A;-regular bipartite graph, then it is easy to show that G satisfies Hall's condition, i.e. \N(S)\ > \S\ for all 5 C X. C o r o l l a r y 1.6 For k > 0, every k-regular bipartite graph has a perfect matching. 1.2.2 Matchings in General Graphs A graph G is connected if it has a path for each pair u, v € V(G); otherwise it is disconnected. A subgraph of a graph G is a graph H such that V(H) C V(G) and E(H) C E(G). A n induced subgraph of G is a subgraph H of G such that E(H) consists of all edges of G whose endpoints belong to V(H). For any subset S C V(G) , G — S denotes the induced subgraph on V(G) — S. The components of a graph G are its maximal connected subgraphs. A cut-edge or cut-vertex of a graph is an edge or vertex whose deletion increases the number of components. The order of a graph G, written n(G), is the number of vertices in G. A n odd component of a graph is a component of odd order; the number of odd components of H is o(H). Now we shall expand our discussion of matchings to general graphs. Tutte 5 found a necessary and sufficient condition for an arbitrary graph to have a perfect matching. T h e o r e m 1.7 (Tutte [SO]) A graph G has a perfect matching if and only if o(G — S) < \S\ for every S QY(G). Most applications of Tutte's Theorem involve showing that some other con-dition implies Tutte's condition, which then guarantees a perfect matching. Here is an example. C o r o l l a r y 1.8 (Petersen [27]) Every ^-regular graph with no cut-edge has a perfect matching. In this thesis, we will be examining bipartite graphs and will not be using Tutte's Theorem. 1.3 Networks and Flows A network is a digraph with a nonnegative capacity c(e) on each edge e and a distinguished source vertex s and sink vertex t. Vertices are also called nodes. A flow f assigning a value /(e) to each edge e. We write f+(v) or f+(S) for the total flow on edges exiting a node v or a set of nodes S; the total flow on entering edges i s / - ( t ; ) o r / - ( 5 ) . In terms of/(e) , / > ) = £ /(e) a n d / " ( « ) = £ /(e); e=(v,u) e=(u,v) f+(S)= £ / ( e ) a n d / - ( 5 ) = £ /(e). e=(v,u) e=(u,v) A feasible flow satisfies the capacity constraints 0 < /(e) < c(e) for each edge and the conservation constraints f+(v) = f~{v) for each node v £ {s,t}. The value val(f) of a flow / is the net flow f~(t) — f+{t) into the sink (or the net flow 6 / + ( s ) — f~(s) out of the source). A maximum flow is a feasible flow of maximum value. A source/sink cut partitions the nodes of a network into a source set S containing s and a sink set T containing t. The elements of the cut [S,T] are the edges from S to T; every s,t-path uses at least one edge of [S,T]. The capacity of the cut [S, T], written cap(S,T), is the total of the capacities on the edges of [S,T]. The most important result in network flows is the Max-flow Min-cut Theo-rem, proved by Ford and Fulkerson [12]. This result can be viewed as a special case of the strong duality property in Linear Programming. T h e o r e m 1.9 (Max-flow Min-cut Theorem) In every network, the maximum value of a feasible flow equals the minimum capacity of a source/sink cut. Let us now apply the Max-flow Min-cut Theorem to get a quick proof of the Konig-Egervary Theorem. Let G be a bipartite graph with bipartition X, Y. Build a network G' by directing all edges of G from X to Y, adding a new point s (the "source") joined to all points of X and a new point t (the "sink") to which all points of Y are joined. Assign capacity oo to all edges of G and capacity of 1 to all new edges of G'. It is easy to see that a maximum matching in G corresponds to a maximum flow in G', and so the maximum size of a matching equals the maximum value of a feasible flow. We need to show that the minimum size vertex cover in G equals the minimum capacity of a source/sink cut in G'. Assume I U J is a minimum vertex cover in G, where I C X and J C Y. Let S — {s} U (X — I) U J and T = {t} U I U (Y - J). Then cap{S,T) = \I U Jj = \I\ + | J | . We claim that [S,T] is a minimum source/sink cut in G'. Otherwise, there exists some cut [S',T'} such that cap(S',T') < cap{S,T). We may write S' = {s} U (X - V) U J' and 7 T = {t} Ul'u'Y- J') for some vertex cover V U J ' , where I' CX and J' C y . Then |7'| + \J'\ = cap(S',T') < cap(S,T) = \I\ + | J | . This leads to a contradiction. In combinatorial applications, we typically have integer capacities and want a solution in which the flow on each edge is an integer. C o r o l l a r y 1.10 (Integrality Theorem) If all capacities in a network are integers, then there is a maximum flow assigning integral flow to each edge. In Fulkerson, Hoffman and McAndrew [14], and Anstee.[3], there is an ex-ploration of how network flow techniques can assist in finding general matchings. 1.4 Capacitated Perfect 6-matchings and Bidirected Flows Let G = (V, E) be a graph representing a communication network, i.e. the nodes v can be viewed as terminals and there is an edge {v, w} if two terminals can directly communicate. Every node v has capacity/demand bv € N of possible information exchange operations. Now the task is to find an intersection of the terminals such that the demand is fulfilled. We denote the number of uses of edge e by xe and the set of edges having a node v G V as one of their endnodes by 5(v). A mapping x : E H-> N is called a 6-matching if x{S(v)) := x* ^ bv V v€V. eeS(v) These conditions are called node constraints if x(5(v)) = bv for all v and a mapping fulfilling all these conditions is called a perfect b-matching on G: When bv = 1 for all vertices in G, then (perfect) 6-matchings are the usual (perfect) matchings. Now the problem is complicated by "capacity constraints" and "lower bounds" on the 8 edges, i.e. for every edge e G E there are two numbers le,ue with ue > le > 0, which give the maximal necessary usage and minimal possible usage of a single edge in the graph. Then a mapping x is called a capacitated perfect b-matching if it is a perfect 6-matching on G and le < %e < Ue V e £ E. Now the optimization problem occurs when a cost function c : E i—> R is introduced giving for every edge e E E the cost for exchanging one unit from the tail node of e to the head node of e. Then we want to find a capacitated perfect 6-matching which minimizes total cost c(x) where eeE The above introduced capacitated perfect b-matching problem can be formu-lated as an integer linear programming problem. v min ^T^ cexe eeE s.t. x(5{v)) = bv V v e V le < xe < uey e € E x e N. A bidirected graph G = (V, E) is a graph in which some edges (called loops) may have both ends incident with the same node, some edges (called lobes) may have only one end, and in which each edge has a direction associated with each node with which it is incident. Thus each edge has either one or two (not necessarily distinct) ends, and each of these ends is either a tail end or a head end. For any vertex v G V, we define for bidirected graphs 9 S(v) := the set of edges having exactly one end at v, j(v) := the set of edges having both ends at v, S+(v) := the set of edges in 5(v) whose single end at v is a head end, 6 (v) :— the set of edges in 6(v) whose single end at v is a tail end, 7 (v) := the set of loops having two head ends at v, 7~(i>) := the set of loops having two tail ends at v. Similarly, if we denote by x ethe number of units assigned to edge e, then we have to find a mapping I : £ H N such that These conditions are called flow conservation constraints and a mapping fulfilling all these conditions is called a bidirected flow on G. Now the problem may again be complicated by "capacity constraint" and "lower bounds" on the edges, i.e. for every edge e € E there are two numbers le,ue with ue > le > 0, which give the maximal necessary usage arid minimal possible usage of a single edge in the network. Then a mapping x is called a feasible bidirected flow if it is a bidirected flow on G and As in the 6-matching problem we assume a cost function c : E i-> R giving for every edge e the cost for "transporting" one unit. Then the optimization problem is to find a feasible bidirected flow x which minimizes total cost c(x) where eeE The above introduced bidirected flow problem can also be formulated as an integer linear programming problem. x(5+(v)) - x{S-(v)) + 2x('y+(v)) - 2xia~(v)) = bv V v € V. V e € E. 10 min c e x e eeE s.t. x(S+(v)) - x(5~(v)) + 2x(>y+(v)) - 2x(-y~ (v)) = bv V v € V le < %e < uey e € E x e l . The bidirected flow problem looks quite similar to the capacitated b-matching problem. In fact a bidirected flow in a bidirected graph G = (V, E) can be reduced to a capacitated 6-matching in the undirected graph G' = (V U V, E) — with V = {i' : i e V} and E — {e : e € E}, where e are given below — by doing the following (Derigs [6] and Edmonds [8]). Let e = be an edge in E. • If e has 1 head for i and 1 head for j, then we construct one corresponding edge e = In particular, when i — j, i.e., e has 2 heads for i, then e = i.e., a loop at i'. • If e has 1 tail for i and 1 tail for j, then we construct e = (i, j). In particular, when i = j, i.e., e has 2 tails for i, then e — i.e., a loop at i. • If e has 1 head for i and 1 tail for j, then we construct e = (i', j ) . In particular, when i — j, i.e., e has 1 head and 1 tail for i, then e = (i', i). Thus a capacitated b-matching in a bidirected graph G = (V, E) is an assignment of nonnegative integers xe to the edges e of G such that xe fulfills the "lower bound" and "capacity" conditions and the capacity/demand bv at each node v S V is fulfilled, in the sense that edge e contributes — 2xe, —xe,0, xe, 2xe units to the capacity/demand at v according to whether e has 2 tails, 1 tail, 0 ends, 1 head, 2 heads at v. 11 Chapter 2 Applications of Matchings There are many applications of matchings in both bipartite and non-bipartite graphs, such as the Assignment Problem, the Chinese Postman Problem, etc. 2.1 Applications of Matchings in Bipartite Graphs 2.1.1 The Assignment Problem Assignment of people or other resources' to various workstations or certain equipment to accomplish certain tasks while minimizing the total cost is a frequent management decision problem. For example, assigning employees to various tasks, teachers to different classes, crews to projects, and ambulances to first-aid stations are good real-wold examples of assignment problems. The basic goal of the assign-ment problem is either to minimize the total cost of completing all the required tasks or to maximize the total payoff (or benefits) from the assignments. The following example is from Lee and Shim [22]. E x a m p l e Kabuki Electronics specializes in producing electronic scanners. The com-12 parry received a special order from a large cash-register company for optical scanners. To produce important components required for the scanner, the company has se-lected four employees for assignment to four different machines to complete the necessary tasks. Because of different individual training and experience, the cost of successful completion of the given task to each machine is different for the four employees. Only one employee can be assigned to each machine. Also, each task is completed independently by one employee on one machine. The assignment problem at Kabuki along with the cost involved for each employee to complete each task on each machine, is presented in Table 2.1. Notice that there are the same number of rows (employees) and columns (machines). Also, the amount of supply and demand for each row and each column is exactly one. Employee \ Machine A . B C D Supply 1 20 10 14 13 1 2 18 10 22 18 1 3 28 14 20 28 1 4 6 10 22 8 1 Demand 1 1 1 1 4 Table 2.1: Tableau Form of the Kabuki Electronics Assignment Problem In Table 2.1, we can easily see that it costs $20 for employee 1 to complete the task using machine A, $10 using machine B, and so on. The cost required for each employee to complete each task may be determined by the amount of time required and the amount of other resources (i.e., materials) used to complete the task. The objective of this assignment problem is to find the employee's optimum assignment schedule to each machine to minimize the total cost to complete the tasks. The assignment problem is a weighted bipartite matching problem, where 13 the costs are the weights. In particular, the sets of the bipartition have the same size, i.e., there are equal numbers of employees and machines. Our Goal is to find the perfect matching between employees and machines such that the total cost is minimized. The best known method to solve assignment problems is the Hungarian Method. For details, please refer to Kuhn [21] or Munkres [25]. The optimal assignment and total cost of the Kabuki Electronics Assignment Problem are as follows: O p t i m a l Ass ignment Employee Machine Cost 1 D 13 2 B 10 3 C 20 4 A 6 To ta l Cos t = $49 Table 2.2: The Optimal Assignment of the Kabuki Electronics Assignment Problem 2.1.2 The Dimer Problem The close-packed dimer model of statistical mechanics can be stated as fol-lows. One considers a set of sites and a set of bonds connecting certain pairs of' sites. Each bond b can absorb a "dimer" (which represents a diatomic molecule) with corresponding energy E^. It is required that each site is occupied exactly once by one the atoms of a dimer. A state s is an arrangement of dimers which meets this requirement, and its energy E(s) is E\> where the sum is taken over all bonds b which absorb a dimer. Then the partition function of the dimer model may be viewed as a density function of energy levels. The dimer model was first considered by Roberts [29] in 1935, and by Fowler and Rushbrook [13]. The dimer model for 2-dimensional lattice graphs appears in 14 calculations of the thermodynamic properties of a system of diatomic molecules-dimers arranged in a planar sheet. The partition function can be evaluated in polynomial time using Kasteleyn's method [18] for enumerating perfect matchings in planar graphs. One special type of graph for which enumeration of perfect matchings is of considerable "real-world" interest is the class of rectangular lattice graphs or chessboards (perhaps more accurately "go boards"). Consider an m x n chessboard with mn even. In how many ways can this board be covered by dominoes (dimers)? In graph theoretic terms, the dimer problem for 2-dimensional lattice graphs can be formulated as follows. Let L(m, n) denote the graph whose vertices are the squares (think of them as the centers of the squares) of an m x n chessboard with ran even, two being adjacent if and only if they have a boundary line in common. L(m,n) is a bipartite graph, which means that its vertices may be partitioned into two sets Zi,Z2 such that if e is an edge of L(m,n) then |e fl Z\\ — |e n Z2I = 1. Moreover, we have also that \Z\ \ = IZ2I = mn/2. Now, the problem is to determine the number $ (L(m, n)) of perfect matchings in L(m,n). Kasteleyn [18] gave the answer: m n / , , \ 1 / 4 * ( L ( m , » » = v * n n ( r o s 2 ( ^ T » + » s 2 ( ^ i » ) • But the same problem for 3-dimensional lattices remains an important open problem of statistical physics (see Kasteleyn [19] for references). 15 2.2 Applications of Matchings in General Graphs 2.2.1 The Chinese Postman Problem A postman has to leave a post office and traverse a number of streets at least once for delivering and picking up mails, then return to the post office to do his job. How should he plan his walk to minimize his walking distance or time? We can phrase it as a graph problem as follows: A postman traverses all edges in a road network, starting and ending at the same vertex. The edges have nonnegative weights representing distance or time. We seek a closed walk of minimum total length that covers each edge at least once. This is called the Chinese Postman Problem in honor of the Chinese mathematician Meigu Guan [15], who proposed it. Recall that a closed trail is a trail whose length is at least one and its end-points are equal. We say that a graph whose edges comprise a single closed trail is Eulerian. We use the term circuit as another name for "closed trail"; a circuit containing every edge of G is an Eulerian circuit. We also use odd vertex or even vertex to indicate the parity of a vertex degree. If every vertex in the road network is even, then we can show that the graph G is Eulerian and so the minimum total length is the sum of the weights. Otherwise, we must repeat edges. If there are only two odd vertices, then we can use Dijkstra's Algorithm [7] to find the shortest path between them and solve the problem. If there are 2k (k > 2) odd vertices, then we can use the shortest path algorithm to find the shortest paths connecting each pair of odd vertices. We can use these lengths as weights on the edges of Kik, and then our problem is to find the minimum total weight of k edges that pair up these 2k vertices. This is a weighted version of the maximum matching problem. Edmonds and Johnson [9] described a way to solve 16 this Problem. A n interesting application of the Chinese Postman Problem is the Plotter Problem which was introduced by Asano, Edahiro, Imai, Iri and Murota [4]. The problem is the plotting of a large figure on a computer controlled plotter. They draw straight line segments between points to draw a piecewise linear curve then lift the pen up and travel to the next curve to be drawn. We may think of the plotter as a postman with a pen. In the Chinese Postman Problem we form an auxiliary complete graph defined on the vertices of odd degree. Each edge has a weight, namely the distance between the vertices in the original graph. In the Plotter Problem this weight is the distance, d((x\,yi), ( 2 2 , 2 / 2 ) ) = max{|a:i — x%\ + \y\ — yiW- It is worth pointing out that the graph G in the Chinese Postman Problem must be connected (since the postman can only walk) while the graph G' in the Plotter Problem may be disconnected. If G' is connected, the solution is then the same as the that for the Chinese Postman Problem. Otherwise, we need first to add some extra edges carefully to make it connected. In fact, a minimal number of edges required to join components will correspond to the Travelling Salesman Problem (TSP). 2.2.2 Quadrilateral Mesh Generation in Computer-Aided Design Muller-Hannemann [26] considered the following definition of polygon for use in mesh generation. A polygon is a region in the plane or, more generally, of a smooth surface in the 3-dimensional space, bounded by a finite, closed sequence of straight line segments or curves (edges). A polygon is simple if its edges do not cross each other, and convex if the internal angle at each vertex is at most n. A mesh is a set of openly disjoint, convex and simple polygons. i 17 Miiller-Hannemann [26] has considered a mesh refinement problem arising in the computer-aided design (CAD) of motor vehicle parts, for example, bodyworks or chassis or their components: a coarse mesh of curved polygons, which approxi-mates the surface of a workpiece, has to be refined into quadrilaterals such that the resulting mesh can be used for a numerical analysis. Originating from a concrete application, [26] has described the difficult mod-eling process, analyze the computational complexity of the mesh refinement problem in various forms, and develop a new algorithmic approach. In [26], we see an original application of network flow and matching techniques in a mesh refinement problem. The experiments in [26] showed that this approach usually leads to meshes with a very good quality. The mesh generation problem can be reduced to a bidirected flow problem on a bidirected graph G with capacity constraints and lower bounds on the edges and some additional node balance conditions (Muller-Hannemann [26]). We have shown in section 1.4 that the bidirected flow problem can be reduced to the capacitated perfect 6-matching problem. There are several polynomial algorithms for 6-matching problems (see Pulleyblank [28], Anstee [2], and Miller and Pekny [24]). 18 Chapter 3 Introduction of the Problem 3.1 Robustness Network robustness measures how well a network can continue to perform its function after node or arc failures. There are several different ways and method-ologies to measure robustness of networks, e.g., resilience to random node failures (fragility), resilience to attacks (vulnerability), or number of alternative paths. The idea of "robustness" considered here is very different from network ro-bustness. We study the robustness of a graph with respect to the property of having a perfect matching under the operations of vertex deletion. This thesis studies lattice graphs which are readily seen to have many perfect matchings and considers whether if we delete vertices the resulting graphs continue to have perfect matchings. In order to guarantee the resulting graphs still have perfect matchings, we require some constraints on the deleted vertices. We will impose the constraint that the deleted vertices are at a certain distance from each other. 19 3.2 Motivation This thesis was motivated by a result of Jamison and Lochner [17]. T h e y studied a problem about tiling fringed chessboards with dominoes. A fringe on a p x q chessboard is a set of additional nonadjacent squares added above the top row. T h e squares may be considered as colored black and white consistently with the board. If the fringed board is to be tiled by dominoes, then the total number of black squares must equal the total number of white squares. In general, this parity condition is not sufficient. However, if the board is deep enough, i.e., p is big enough, then this parity condition does suffice to guarantee a tiling. A balanced fringe is a fringe that contains an equal number of black and white squares. T h e depth of a fringe X is defined as A(X) — max \Bi — Wj|, where l d, for (xi,X2),(x'1,x'2) e B', (c) d((x1,x2),{x'l,x2)) > d, for (xi,x2),(x'1,x2) G W, 23 where d — 4\^/m} + 8, then the graph Q(m,2) - (B' U W) has a perfect matching. * Theorem 3.2 gives a result for the 2-dimensional case. We try to get some similar results in higher dimensions in next chapter. 24 Chapter 4 Main Result for n-dimensional Lattice Graphs 4.1 Statement of Theorem 4.1 Theorem 4.1 is a nontrivial analogue of Theorem 3.2 for higher dimensions. We will use some proof ideas from the proof of Themreom 3.2 [1], but the overall proof of Theorem 4.1 is quite different from that of Theorem 3.2. In this whole chapter, we assume m,n are natural numbers and m is even, n > 2. Theorem 4.1 Let Let Q(m,n) be an n-dimensional lattice graph with bipartition B,W. Choose any sets B' C B,W C W. If B',W have the following three properties: (a) \B'\ = \W'\, (b) d^x^xi,... ,xn),(x[,x'2,... ,x'n)) > dn,y (xi,x2,. •.,xn), (x[,x'2,... ,x'n) G B', (c) d((xi,X2t...,xn),(x'ltx'2,...,x'n)) > dn,V (xi,x2,...,xn), (x'1,x'2,...,x'n) G W, 25 where dn — 4n(n + l)\y/m~\, then the graph Q(m,n) — (B' U W) has a perfect Before proving the theorem, we will prove 4 lemmas. The proofs of Lemma 4.2 and 4.3 are loosely based on arguments in [1]. The results of Lemma 4.4 and 4.5 are original, and the proofs are quite different from those of Lemma 4.2 and 4.3. Recall that if S U N(S) is connected, the side lengths of S U N(S) are ai = max{x; : (xi ,£2, • • • ,xn) € SliN(S)} - min{a:; : (x\,X2, • • • ,xn) G S U N(S)}, where i = 1, 2 , . . . , n. Without loss of generality, we may assume a\ > a2 > • • • > an. We first expand the region S U N(S) to an a\ x 02 x • • • x an grid. Then we expand the a i x 02 x • • • x an grid to an (ai + dn) x (02 + dn) x • • • x (a„ + dn) grid by adding dn/2 at each of 2n directions, where dn is even. For any x in the a\ x 02 x • • • x an grid, we define Then Bn(x, dn/2) is contained in the (a\ + dn) x (02 + dn) x • • • x (an + dn) grid since any point of Bn(x,dn/2) is at most dn/2 from x and hence at most dn/2 from the ai x a2 x • • • x an grid. Lemma 4.2 For any vertex x in Q(m,n), we have Proof: We prove it by induction. When n = 2, 2^(^ ,^ 2/2) gives a 2-dimensional "diamond". See Figure 4.1, the vertices which belong to the diamond are indicated by thick dots. The number of vertices in such a diamond is matching. Bn(x,d) = {y e Q(m,n) : d(x,y) < d}. 26 16 11 6 1 6 11 16 Figure 4.1: A 2-D diamond with d = 8 in the checkerboard with m = 20. When n = 3, B^(x, d 3/2) gives a 3-dimensional "diamond". We may consider the origin point as the center and d as the diameter of the diamond in 3 dimensions. See Figure 4.2 for a sketch of a 3-dimensional diamond. We only count vertices in the upper half of the diamond. So, Bs(x,d3/2)\ > i | s 2 ( M 3 / 2 ) | ( d 3 / 2 + l) > ± 2 ( ^ ) ^ 3 / 2 + 1) > 2 ( | ) 3 . l - / d 3 \ 2 For general n, we have 1 Bn(x,dn/2) > > Bn-i(x,dn/2)|(dn/2 + 1) only count the upper half n - l dn n \2(n-l) > 2 (dn/2 + 1) by induction ,(dny \2nJ ' 27 Figure 4.2: A sketch of a 3-D diamond. The result \Bn(x,dn/2)\ > 2 ^ ^ ) is enough to prove Theorem 4.1, where dn — 4n(n+1)[ \ /m] . Actually, we can count \Bn(x,dn/2)\ exactly for small n, e.g., B a ( x , | ) = - 2 - + d2 + l > - 2 i -and 5 s ( x , | ) It is easy to see that Bn(x, y ) B » - i ( i , y ) | + 2 £ | i ? „ - i ( x , i ) i=0 i i s even Thus approximately, dn/2)\ > However, even if we could show \Bn(x, dn/2)\ > ^ V , this would only improve dn by a constant factor in Theorem 4.1. 28 4.2 Proof of Theorem 4.1 We first consider a special case in 2 dimensions when |5u7V(5)| < \m2. The main proof idea of Lemma 4.3 is from the proof of Theorem 3.2 [1]. Lemma 4.3 Let Q(m,2) be a 2-dimensional lattice graph with bipartition B,W. Choose any sets S C W, B' C B. If B',W have the following two properties: (a) \SUN(S)\ < lm2, (b) d{{xi,x2), {x'x,x'2)) > d2 = 24 [ v /m] , for (x1}x2), (x'x,x'2) G B', then l -B'n N(S)\ < \N(S)\ - \S\. (4.1) Proof: First we consider the case when S U N(S) is connected. Then we can construct the (a\ + d2) x (a2 + d2) grid as described earlier. If a2 < m, then there is no complete column. Note that the surplus of every column is at least 0 since in any column the number of black vertices is > the number of white vertices. Every two adjacent incomplete nonempty columns have a surplus of at least 1, since in only these two columns, the number of black vertices is more than the number of white vertices at least by 1. Now we pair all the columns from left to right. If a\ is even, we have totally a\/2 pairs and so the surplus is at least a i /2 ; if a\ is odd, we have (a\ — l ) / 2 pairs (1 column left) and so the surplus is at least (ai — l ) / 2 . Hence, the surplus of the a\ incomplete nonempty columns is at least L ai/2J-If a 2 = m, then ax = a2 = m. Since | S U i V ( S ) | < | m 2 , SUN(S) has at most [ | m 2 / m j = [3m/4j complete columns. Hence, there are at least m — [3m/4j = [m/4] incomplete nonempty columns. Again, pair all the columns from left to 29 right and we obtain a\/2 = m/2 pairs. There are 3 different types of pairs: a pair of two complete columns, a pair of one complete column with one incomplete nonempty columns and a pair of two incomplete nonempty columns. The first type pair has a surplus at least 0; the second type has a surplus at least 1 and the third type has a surplus at least 1. Since we have at least fm/4] incomplete nonempty columns, then the surplus is at least [ \m/^ j > |_^y^J = L m / 8 J = L a i / ^ J - Therefore, | t f ( S ) | - | S | > L a i / 8 j . We want to show \B' C\N(S)\ < |_ai/8j. If a\ < 0*2/2 then at most one black vertex can be deleted. So we only need to consider the cases when ci\ > (I2/2, i.e. d2 < 2 a i . Note that for x,y £ B', B(x, d2/2) n B(y, d2/2) = 0. Thus the number of deleted black vertices \B'nN{S)\ < < < (Qi + d2)(a2 + d2) B2(x,d2/2) ( a i + d2)2 d22/8 _ (3ai) 2 7 2 a i 2 d22/8j L d22 J Now d2 = 24[ \ /m], so d22 > 576m > 576ai and so 72aV d22 < ax/8. Thus, \B'nN{S)\ < \N(S)\ - \S\. Second we consider the case that S U N(S) is disconnected, we may write Sl)N(S) = JT{Si{JN{Si)), where every SiUN(Si) is connected and (Sil)N(Si))n (Sj U N(Sj)) = 0 for i ^ j. By the above proof, we get \B' n N(S)\ = £ \B' n i=i N(Si)\ < E(\N(Si)\ - \St\) = E WSi)\- E \Si\ = \N(S)\ - \s\. i=l z=l i = l We use the complete plane 7T { x „ = i } = {(xi,x2,. • .,xn-i,i) :xj = l,2,...,m for j n} 30 to cut S U N(S). Denote the intersection by layer L^. Li = (SUN(S))f)n{Xn=i}. L e m m a 4.4 Let Q(m,n) be an n-dimensional lattice graph with bipartition B, W. Choose any set S C.W. If S has the following two properties: (a) \SUN(S)\<^^mn, (b) there exists some layer Li such that | L j | > 2 " _1[1mn~1, then \N(S)\-\S\> 1 m " " 1 2 n + 1 P r o o f : Let a\, a2,. •., an be the side lengths of S U N(S). We may assume a\ > 0,2 > ... > an. If an < m, then we can show that surplus |iV(5)| — \S\ > | _ ^ J = L 2 " 2 " + l m " ~ 1 J by * n e ^ a c * * n a * * n e number of black vertices > the number of white vertices in any layer and the following "projection line" idea. Since an < m, then at least one of the two layers L i - a n d Lm is empty. Assume Lm = 0. F ix _ 1, the vertex set {(xi, x°2,..., x°n_1J)J = i, i + 1,.. . , m) n (5 U N(S)) defines a projection line. Any projection line that starts with a black vertex has surplus > 1; any projection line that starts with a white vertex has surplus > 0. There are at least [^ 4] = \2" 2n+lmn~l] black vertices in Li and so the projection lines which start from Li give surplus > | " 2 " 2 ^ + 1 m n ~ 1 ] . Note that the number of black vertices > the number of white vertices in any other layers below Li , so \N(S)\-\S\>\2-^±±m^]. 31 If an = ra, then ai = a2 = ... = an = m. Since \S U iV(5) | < 2*2n+1mn, then there exists some layer Lj such that \Lj\ < L 2 " 2 l + 1 m " ~ x j . Then we can show that |AI(5)| - \S\ > \-2-^fImn~1] by the following "projection segment" idea. We may assume i < j. F ix x\, x®, • • •, a;°_i, the vertex set { « xl..., Xn-i,k),i < k 1. 2. Every projection segment which starts with a white vertex in Lj (or Lj) and ends with a white vertex in Lj (or Lj) has surplus > —1. 3. Every projection segment which starts with a white vertex in Lj (or Lj) and doesn't reach Lj (or Lj) has surplus > 0. There are at least [ ^ l ^ m " ' - 1 ] black vertices in Lj and at most L ^ n + t 1 " ^ " - 1 ] white vertices in Lj . So we have surplus at least Case 2: i + j = l (mod 2). 1. Every projection segment which starts with a black vertex in Lj (or Lj) and ends with a white vertex in Lj (or Lj) has surplus > 0. in—2 1 X 2" + 1 n - l in—1 + ( - l ) x 2n+l + 1 n - l 32 2 . Every projection segment which starts with a white vertex in Lj (or Lj) has surplus > 0 . 3. Every projection segment which starts with a black vertex in Lj (or Lj) and doesn't reach Lj (or Lj) has surplus > 1. So the surplus is 1 x f o n - 2 + 1 -ra n - l i n - 1 2 n + l + 1 n - l 2 n + l m n - l Therefore, the surplus between layers Lj and Lj inclusive is at least \ 2-^frran~1]. Since the number of black vertices > the number of white vertices in any other layers above Lj or below Lj , we have at least [ o ^ p - m ™ - 1 ] surplus. • L e m m a 4.5 Let Q(m,n) be an n-dimensional lattice graph with bipartition B,W. Choose any set S CW. If S satisfies \SUN(S)\ < 2 " ~ l + 1 m n , then (4.1) holds. Proof : Note that dn = 4n(n + l ) | \ / m l > d n _ i = 4(n — ^ n f y 7 ? ™ ] . We prove it by induction. Lemma 4.3 showed the case when n = 2. In the n-dimension, if \Li\ < ^ n - i ^ r a " " " 1 for a l i i = 1 , 2 , . . . , m, then we are done by induction. Otherwise, there exists some Lj such that | L , | > 2 ^ ~ ! , t 1 T n " ~ 1 . By Lemma 4.4, we have |iV(S)| — We want to show \B' n N(S)\ < r ^ F T 7 7 1 " - 1 ! - If m < dn/n then at most one black vertex can be deleted. So we only need to consider the cases when m > dn/n, i.e. dn < nm. Note that for x,y € B', B(x,dn/2) n B(y,dn/2) = 0. Thus the 33 number of deleted black vertices \B'nN(S)\ < < < (ai + dn)(a,2 + dn) • • • (an + dn) Bn{x,dn/2) (m + dn)n 2{dn/2n)n (m + nm)7 . 2(dn/2n)n J (2n(n+ l))nmn 2d7 Now dn = 4n(n + > 4 n ( n + l ) N 1 / n ] > 4n(n + ^ m 1 / " , so d n n > (4n(n + l ) ) "m and so (2n(n + l ) ) n m n (2n(n + l ) ) n m ' < -m n - l 2dnn 24n(n + l ) n m ~ 2™+! Thus, | B ' n AT(5)| < \N(S)\- \S\. • From the proof of Lemma 4.5, we see that if there is some layer L j such that | L j | > 2^7r=T^-m n~ 1, then dn = 4n(n+ l ) [ m 1 / , n ] is sufficient to guarantee (4.1). However, when every layer is small (< 2-2-^rLrnn~1), we rely on induction. And we start the induction with n = 2, so we require dn = 4n(n + l ) [ v / m ] for every n. Although we don't know how to prove it, we believe that the best possible dn — f{n)\'rnlln~\, where f(n) is a function of n. Here is an example to show that why the bound m 1 / " is best possible. We choose 5 = E n W, where E | ( x i , x 2 , ••• ,xn) \ xne {1,2, • • • , y } , Xi £ {1,2, • • • , m) for i ^ n j . Since the number of white vertices = the number of black vertices in E, the only surplus are those black vertices above E, then |iV(S)| - \S\ = m \ 1 . Every deleted black vertex takes up a space of size at most dnn, then the maximum number of 34 black vertices which can be deleted is \B'nN(S)\>— /dnn 2 ' " 2dnn' Remark that we can choose W in the other half. In order to make the resulting graph (after deletion) still have a perfect matching, it is necessary that \B> n N{S)\ < \N(S)\ - |5 | , i.e., ^ < ^ =• dn > m1^ Next, we give the proof of Theorem 4.1. P r o o f of T h e o r e m 4.1: We prove Theorem 4.1 by using Hall's Theorem on Q(m, n) — (B' U W). Choose any subset S C W. We need to show that \N{S)-B'\>\S\, (4.2) which is equivalent to (4.1). Lemma 4.5 proves (4.1) for | S U N(S)\ < V 1 " 1 " l t i s e a s y t 0 s e e C4-1) holds for |5 U N(S)\ < \mn since \mn < 2 " ^ + 1 m n . Next, we show (4.1) for \S U N(S)\ > \mn. Let T = B - N(S), then \T U iV(T) | < \mn. Interchanging the roles of W and B, we obtain \W n N(T)\ < \N(T)\ - \T\. Denote W - S - N(T) = A, Using the facts that \B'\ - \W'\ and |J3| = \W\, we have [\B'nN{S)\ < \B'\ = \W'\ = \W n(N(T)l)A)\ = \W C)N(T)\ + \A\ < | iV(T)| — |T | + | W - .S — '= \N(T)\-\B- N(S)\ + \W\ - \S\ - \N(T)\ - MS)\-\s\. We have shown (4.1) for any S C W. • 35 Bibliography [1] R . E . L . Aldred, R.P. Anstee and S.C. Locke, Perfect matchings after vertex deletions, Preprint. [2] R.P. Anstee, A polynomial algorithm for 6-matching: A n alternative approach, Information Processing Letters 24 (1987), 153-157. [3] R.P. Anstee, Matching theory: fractional to integral, New Zealand J. Math. 21 (1991), 17-32. [4] T. Asano, M . Edahiro, H . Imai, M . Iri. and K . Murota, Practical use of buck-eting techniques in computational geometry, Computational Geometry (1985), 153-195. [5] C. Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 842-844. [6] U . Derigs, Programming in networks and graphs, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 300 (1988). [7] E . W . Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959), 269-271. 36 [8] J . Edmonds, A n introduction to matching, Lecture notes, University of Michi-gan, Ann Arbor (1967). [9] J . Edmonds and E . Johnson, Matchings, Euler tours, and the Chinese postman, Math. Programming 5 (1973), 88-124. [10] E . Egervary, On combinatorial properties of matrices, Math. Lapok 38 (1931), 16-28. [11] P. Elias, A . Feinstein and C.E . Shannon, Note on maximum flow through a network, IRE Trans, on Information Theory IT-2 (1956) 117-119. [12] L .R . Jr. Ford and D.R. Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956) 399-404. [13] R . H . Fowler and G.S. Rushbrooke, Trans. Faraday Soc. 33 (1937), 1272. [14] D.R. Fulkerson, A . J . Hoffman and M . H . McAndrew, Some properties, of graphs with multiple edges, Canad. J. Math. 17 (1965), 166-177. [15] M . Guan, Graphic programming using odd and even points, Chinese Math. 1 (1962), 273-277. [16] P. Hall , On representation of subsets, J. Lond. Math. Soc. 10 (1935), 26-30. [17] R . E . Jamison, N . Lochner, Tiling fringed chessboards with dominoes, 34th Southeastern International Conference on Combinatorics, Graph Theory and Computing. [18] P .W. Kasteleyn, The statistics of dimers on a lattice, Physica 27 (1961), 1209-, 1225. 37 [19] P.W. Kasteleyn, Graph theory and crystal physics, Graph Theory and Theo-retical Physics, Academcis Press, New York (1967), 43-110. [20] D. Konig, Graphen und matrizen, Math. Lapok 38 (1931) 116-119. [21] H.W. Kuhn, The Hungarian method for the assignment problem, Naval Re-search Logistics Quarterly 2 (1955), 83-97. [22] S.M. Lee and J.P. Shim, Micro Management Science, A l lyn and Bacon, second edition, 1990, 218-219. [23] K . Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927), 95-115. [24] D .L . Miller and J .F. Pekny, A staged primal-dual algorithm for perfect b-matching with edge capacities, ORSA J. of Computing 7 (1995), 298-320. [25] J . Munkres, Algorithms for the assignment and transportation problems, J . Soc. Indust. Appl. Math. 5 (1957), 32-38. [26] M . Miiller-Hannemann, Quadrilateral Mesh Generation in Computer-Aided De-sign, Cuvillier Verlag Gottingen, 1997. [27] J . Petersen, Die theorie der regularen graphen, Acta Math. 15 (1891), 193-220. [28] W.R. Pulleyblank, Faces of matching polyhedra, Ph.D. thesis, Faculty of Math-ematics, University of Waterloo (1973). [29] J .K . Roberts, Proc. Roy. Soc. (London) A, 161 (1935), 141. [30] W . T . Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947), 107-111. [31] D .B . West, Introduction to Graph Theory, Prentice Hall , 1996. 38