Week 1 Topic: Matchings in Graphs and their Applications 1-factorizations of Cayley graphs It has been conjectured that every connected Cayley
graph on an even order group has a 1-factorization. I shall present a
survey of the current status of this conjecture. Rently the problem of decomposing complete graphs and complete graphs minus a 1-factor into cycles of fixed length has been completely solved. I will present a survey on some of my other favorite cycle decomposition problems. Orthogonal matchings Joint work with L.Caccetta Let G be a graph which has been decomposed as the union of m spanning subgraphs F_1,F_2,...,F_m. An orthogonal matching is a matching M with |E(F_i)\cap M| for i=1,2,..., m. We consider cases where each F_i is regular of degree k (and so G is regular of degree km) and we seek a matching M with |E(F_i) \cap M| <= 1. For k=1, we are able to show the existence of a matching M of size at least m - {2/3}m^{2/3} (for a large m). A special case of this is looking for a transversal in a latin Square for which Schor has obtained the best bound For k=2, Alspach has conjectured that we should be able to find an orthogonal matching M of size m. We show the existence of a matching M of size at least m-m^{2/3} (for large m). The arguments use special augmenting paths. A (k,g)-graph is a k-regular graph with girth g. A (k,g)-cage is a (k,g)-graph of smallest order f(k,g). Cages have been shown to be monotonic in the sense that f(k,g1) < f(k,g2) whenever g1 < g2. We examine a related question: Is f(k1,g) < f(k2,g) whenever k1 < k2 ? In science education today we talk of the process of science and ways of encouraging students to "do science", not just learn about it, through hands-on, inquiry-based lessons and units. Not much has been said about the process of mathematics, nor what would be meant by inquiry in mathematics, yet there is a great deal said about problem solving and modeling using mathematics in the NCTM Standards. How the problems are constructed, where they come from, how one attempts to search and iterate for solutions, and how one discovers new mathematical results to use in the solution is a mystery to most students and teachers. This is a talk that will have something in it for everyone in the audience, teachers, students, and senior researchers. I will try to illustrate the process of mathematics by looking at a problem that exists in software design, construct formulations of the problem, indicate the search for solutions of the formulations, indicate known results, and how one would develop new mathematical tools to solve the problem. The ultimate or optimal answers are not yet known, so the audience will be able to search for solutions as well. The only hint for now is that the problem formulation involves network stability. In 1976 Gyarfas and Lehel conjectured that every sequence of trees T_1,T_2,...,T_n such that |V(T_i)| = i for all 1<=i<=n, can be packed into K_n. This conjecture is usually referred to as the Tree Packing Conjecture. We will discuss recent results on this conjecture concerning sequences of trees which have a vertex of "large" degree. Similar type results for Ringel's conjecture, which states that 2n + 1 copies of a tree of order n+1 can be packed into K_{2n + 1} will also be discussed, as well as recent progress on related questions. In this presentation I will introduce three real problems which were modeled as graph problems and solved by matching theory. The first is a Chinese postman problem: to find a minimum distrance route for a postman who starts from a post office and goes along each street at least once and ends at the post office. This problem was raised in 1962 by Meigu Guan and solved by Edmonds. It was one of the most beautiful applications of classical matching theory. The second is a special garbage collection problem: to find a route with minimum number of U-turns for a large garbage collecting truck which goes along each street from each direction exactly once. This problem was again formulated to a graph problem and solved by using the matroid matching theory. The third one is a routing problem in VLSI circuit design. The focus of this presentation is on modeling real world problems by graph and trying to solve them by using matching theory. Some background stories will be covered. Minimal cost dynamic matchings using a genetic algorithmGraph theoretical problems in formal verificationThe integrated circuits built by the micro-electronics industry in 1999 are several orders of magnitude more complex than those of a decade ago. A design error discovered late in the development cycle can result in the loss of hundreds of millions of dollars. The current technologies for verification of designs include massive simulations and, more recently, formal verification techniques. Formal verification begins with the construction of a finite state automaton which represents the design of the circuit. Properties of the design are then formulated in a temporal logic language. These properties can be associated with sets of paths in the labeled digraph of the finite state automaton. Formal verification consists of proofs of the existence (or non-existence) of these paths in the finite state automaton. One of the major issues in this area is how to represent the enormous digraphs involved in these computations. The current technology of choice for this representation problem is Binary Decision Diagrams (BDDs) which are themselves objects of considerable graph theoretical interest. This talk will survey some of the issues and hopefully encourage the interest of the graph theory community in this exciting area of research. Ranking intervals under visibility constraintsLet S be a set of n closed intervals on the real line. A ranking assigns to each interval s, a distinct rank, p(s) in {-1,2...,n} We say that an endpoint x of an interval s is exposed if no interval t with p(t) < p(s) contains x. A ranking is optimal if the number of exposed endpoints is maximum. We characterize all optimal rankings of a given set S, and present a polynomial time algorithm which finds an optimal ranking. The results have applications to intersection problems for intervals as well as to channel routing problems which arise in layouts of VLSI circuits. This problem was first posed by H. Edelsbrunner in 1982 and was solved simultaneously in 1989 by two teams of researchers: Edelsbrunner, Overmars, Welzl, and Hartman with Feldman. Matching in bipartite graphs and hypergraphs Hall's Theorem gives a necessary and sufficient condition for a bipartite graph to have a complete matching. We define a more general object called a "bipartite hypergraph", in which there is a natural notion of "complete matching", and give a theorem analogous to Hall's Theorem for these more general objects. Universal vertices and the ole switcheronny This will be an elementary talk on two fundamental concepts in matching theory: the role of universal vertices, those contained in every maximum matching, and path interchanges (= the ole' switcheroony). The emphasis will be on a game children could play on a graph, 'Slither'. The ideas introduced here are actually strong enough to prove both Hall's classic theorem on matchings in bipartite graphs, as well as Tutte's celebrated theorem on perfect matchings.
Matching designsThe Role of symmetry in the construction, recognition and classification of 1-Factorizations of the complete graphOpen questions concerning the 1-Factorizations GK(G) of the complete graph.New upper bounds for a canonical ramsey problemA strengthenning of the Kuratowski Planarity Criterion for graphsNew side constraints for the traveling salesman problem Arising in printed circuit board assemblyThe problem is of significant importance, both as a prototype problem for Combinatorial Optimization and since many industrial applications can be modeled as TSPs [5]. However, it is extremely hard to tackle and well known to be NP-hard. Here we would like to consider a TSP based model used in printed circuit board assembly to determine optimized component insertion sequences for automated component placement machines. In order to model this problem as a TSP, cities and inter-city distances need to be defined. This can be achieved by defining the placement locations as cities and the distances can then be defined by the time between two successive insertions. This sequencing problem has recently become of significant importance for the electronic manufacturing industry with the development of Surface Mount Technology (SMT) in Printed Circuit Board (PCB) assembly. Since surface mount introduced the possibility to mount a large number of components on a single circuit the reduction of assembly time is now probably the most important issue to further cut down production costs and increase productivity. However, the industrial printed circuit board component placement problem is more complicated as the design of the production line and machine specifications introduce additional restrictions on the TSP. Schematically can the assembly of printed circuit boards on a typical production line be divided in three problems: 1. the assignment of component types to machines, 2. the assignment of component types to component feeder locations for each machine, 3. the component placement sequencing for each machine. Here we are considering a single component placement machine, assuming that the first problem, the allocation of component types to machines, has already been solved. Many publications have been devoted to this complex optimization problem and various models and techniques have been presented by Shellwell, Buzzcott and Magazine [ 10], Ball and Magazine [ 1 ], Brad et al. [2], Leipala and Nevalainen [7], Kho and Ng [4], Moyer and Gupta [9], Foulds and Hamacher [31 and Leon and Peters [8] to name but a few. In contrast to most publications considering the problems (2) and (3), we avoid separating them and address the assignment of components to feeders as a complication of the component placement sequencing problem, i.e. we treat (2) and (3) together as a complication of the TSP. We further present some complicating factors introduced by machine specifications which may be modeled as additional side constraints on the TSP. Our aim is to investigate and discuss these side constraints arising in printed circuit board assembly. Finding the "middle" of a graph and why it mattersOn a graph whose vertices are graphs with bounded degree Joint work with Krystyna Balinska Let U(n,f) be the graph whose vertices consist of the unlabeled graphs of order n having no vertex of degree greater than f and such that the vertex corresponding to the graph G is adjacent to the vertex corresponding to the graph H if and only if H is obtainable from G by the insertion of a single edge. This graph can be extended to directed graphs with arcs weighted with probabilities yielding Markov chain models which are of interest in random graph theory and in mathematical chemistry. We shall discuss results and problems which range from those applicable to undergraduate instruction to quite difficult open problems. Near-Automorphisms of complete multipartite graphsPartitioning the edges of a graph G into 4-cycles Joint work with Hung Lin Fu In this talk, I will discuss some of the latest results on partitioning the edges of a graph G into 4-cycles. In particular, necessary and sufficient conditions are found in the case where G is obtained from the complete graph by removing the edges of F, where F is any tree, and where F is any 2-regular graph. The case where G consists of m sets of vertices of size n, in which 2 vertices are joined by x edges if they are in the same set and y vertices if they are in different sets, is also solved. Imbalance in round robin tournaments Joint work with Dalibor Fron In a round robin tournament (i.e., a 1-factorization of the complete graph, each of the 2n teams plays each other's team exactly once. The n(2n-l) matches are played in 2n-l rounds each of which consists of n games played simultaneously on n distinct fields. A tournament design is a round robin tournament together with an assignment of matches to particular fields. For a tournament design, a reasonable requirement appears to be some sort of a fair and equitable distribution of teams to particular fields, as the latter may be of different quality. We introduce several measures of such an equitability, such as 'team imbalance', or 'field imbalance'. Tournament designs with minimum (team or field) imbalance are the well-known balanced tournament designs. Our objective is to determine the spectrum for imbalances in tournament designs. The latter may or may not satisfy some additional requirements. Dancing with Eigenvalues=========================== To what extent do the eigenvalues of a Graph G determine G? One can argue that not much can be told about the graph from it's eigenvalues. After all there are many examples of graphs sharing the same spectrum. In some areas the eigenvalues play a central role. One such area is the Shannon Capacity of Graphs. The Shannon Capacity of a Graph G measures the information rate in an underlying noisy channel. In this talk an introductory survey of the Shannon Capacity and the special role of eigenvalues will be discussed. In particular, I'll try to show why determining the Shannon capacities of some "famous" graphs like the Peterson Graph, Grotsch Graph, Hoffman-Singleton Graph are of particular interest. Dancing with Eigenvalues II. =========================== Given 4 lines through the origin in R^3. How large can be the smallest angle among the 12 angles determined by them? In how many distinct (non-isometric) ways can one arrange 4 lines through the origin so that the angles between any pair of distinct lines are the same? These questions are part of the study of equiangular lines pioneered by J.J.Seidel. Again the central tool in studying equiangular lines are Graph Eigenvalues. In this talk I'll show how Graphs and equiangular lines are related and describe some current results and open problems. Using 1-factorizations of the complete graph to find arc-distinct Hamilton cycles in certain networksVariability of 1-factorizationsMatching extension and factor-critical in graphs(2 + epsilon)-flow for nearly eulerian graphs |