DIMACS DCI '03 Topic: Combinatorial Design Theory July 13 - 18, 2003 All lectures will be give in the first floor auditorium. Abstracts Frank Bennett Mount Saint Vincent University A Survey of Steiner Pentagon Packing and Covering Designs Let K denote the complete undirected graph on n vertices. A Steiner pentagon system (SPS) of order n is a pair (K, B), where B is a collection of edge-disjoint pentagons which partition K, and such that every pair of distinct vertices of K is joined by a path of length two in exactly one pentagon of B. A Steiner pentagon packing (covering) of order n is a pair (K, B), where B is a collection of pentagons from K such that any two vertices are joined by a path of length one in at most (at least) one pentagon of B, and also by a path of length two in at most (at least) one pentagon of B. If no other such packing (covering) has more (fewer) pentagons, the packing (covering) is said to be maximum (minimum) and the number of pentagons in a maximum packing (a minimum covering) is called the packing number (the covering number), denoted by p(n) (c(n)). We shall present a brief survey of the results relating to the determination of the values of p(n) and c(n) and mention some open problems. For the most part, the main results have been established on the strength of the existence of certain types of holey Steiner pentagon systems (HSPSs), which are of interest in their own right. Marco Buratti Universita di Perugia A survey on cyclic or $1$-rotational $k$-cycle systems Over the last thirty years $k$-cycle systems have received an increasing amount of attention. In spite of this, the obvious necessary conditions for their existence were proven to be also sufficient quite recently. This important result is due to Alspach and Gavlas in the odd case and to \v Saina in the even case. In this talk we give a survey on very recent results about $k$-cycle systems admitting a cyclic automorphism group acting sharply transitively on the vertices $k$-cycle systems or fixing one vertex and acting sharply transitively on the others $1$-rotational $k$-cycle systems. We illustrate, in particular, a result according to which for $k$ odd and any admissible $v<3k$ there exists a $k$-cycle system of order $v$ that is either cyclic or $1$-rotational. This, in view of a well known result by Hoffman, Lindner and Rodger, may also be viewed as an alternative proof of the theorem of Alspach and Gavlas mentioned above. Bibliography B. Alspach and H. Gavlas, Cycle decompositions of $K_n$ and $K_n-I$, J. Combin. Theory Ser. B, 81 (2001), 77-99. M. Buratti, 1-rotational $k$-systems of order $v<3k$; an alternative proof of the existence of odd cycle systems, J. Combin. Des., to appear. D.G. Hoffman, C.C. Lindner and C.A. Rodger, On the construction of odd cycle systems, J. Graph Theory, 13 (1989), 417-426. M. \v Sajna, Cycle decompositions III: Complete graphs and fixed length cycles}, J. Combin. Des., 10 (2002), 27-78. Peter Danziger Ryerson University A characterisation of Class-Uniformly Resolvable Designs A Class-Uniformly Resolvable Design (CURD) is a resolvable pairwise balanced design, with multiple block sizes, in which each of the esolution classes has the same number of blocks of each size. These designs are related to many well known classes of designs. In this talk we investigate the necessary conditions for the existence of Class-Uniformly Resolvable Designs with block sizes two and three. A CURD on $v$ points has $r$ resolution classes and each class contains $p_2$ blocks of size 2 and $p_3$ blocks of size 3. We will see how these necessary conditions give rise to some unexpected extremal bounds on $v$ for given values of either $p_2$, or $p_3$. A Class-Uniformly Resolvable Design with block sizes two and three can be characterised by the four (interelated) parameters $(v, r, p_2, p_3)$. A classification of which parameter sets are permissable has proved elusive, we will show how a standard frame construction leads to a complete characterisation of admissable parameter sets. Jeff Dinitz University of Vermont Firefighting and Enumerating Balanced Tournament Designs In this talk I will discuss two different problems that I have been interested in lately. The first is a problem in graph theory. A fire breaks out at a node at time 0. At each time period a firefighter (or several firefighters) can be placed at a node of the graph that it protects for all subsequent time periods. All unprotected nodes that are adjacent to burning nodes catch on fire at each time period. We discuss several questions concerning firefighting on the rectangular grid graph. The second topic concerns the enumeration of balanced tournament designs (BTDs) of order 10. These are arrangements of the 45 pairs of elements from a 10 set into the cells of a 5 x 9 array in such a way that each symbol occurs exactly once in each column and at most twice in each row. In 1988 it was determined that there are exactly 47 nonisomorphic BTDs on 8 points. We have found that there are precisely 30,220,557 nonisomorphic BTDs on 10 points. We will give a short discussion of the techniques used to determine this value. Peter Dukes Arizona State University Designs and permutation codes The (Hamming) distance between two permutations on the same symbol set is the number of positions in which they differ. A permutation code (or permutation array) with length n' and minimum distance d' is a collection of permutations on a symbol set of size n' such that the distance between any two distinct members of this collection is at least d'. Finding large permutation codes is of some interest for powerline communication. In this talk, I will mention a variety of old and new constructions of permutation codes. In particular, a recursive construction of permutation codes using resolvable designs (or packings) will be presented. The performance of maximum clique searching to this problem will also be discussed. Heather Gavlas Illinois State University Cycles Systems in the Complete Bipartite Graph Minus a One-Factor Let $K_{n,n}-I$ denote the complete bipartite graph with $n$ vertices in each part from which a 1-factor $I$ has been removed. An $m$-cycle system of $K_ {n,n}-I$ is a collection of $m$-cycles whose edges partition $K_{n,n}-I$. Necessary conditions for the existence of a $m$-cycle system of $K_{n,n}-I$ are that $m \ge 4$ is even, $n \ge 3$ is odd, $m \le 2n$, and $m | n(n-1)$. In this talk, we show these necesssary conditions are sufficient except possibly in the case that $m$ is congruent to $0$ modulo $4$ with $n < m < 2n$. Lucia Gionfriddo Universita degli Studi di Catania Nesting Kite and 4-cycle systems (Joint work with Curt Lindner) A $\lambda$-fold kite system is a pair $(X, K)$, where K is a collection of edge disjoint kites which partitions the edge set of $\lambda$$K_n with vertex set X. A \lambda-fold 4-cycle system is a pair (X, C), where C is a collection of edge disjoint 4-cycles which partitions the edge set of \lambda$$K_n$ with vertex set X. If $(X,B)$ is a $3$-fold block design, $(X,K)$ a $2$-fold kite system, and $(X,C)$ a $2$-fold $4$-cycle system of order n, then $|B| =n(n-1)/4=|K|=|C|$. We can ask: for which n does there exist a 3-fold block design $(X,B)$ with the property that a kite [$4$-cycle] can be selected from each block in B so that the resulting collection of kites K [$4$-cycles C] is a $2$-fold kite system $(X,K)$ [$4$-cycle system $(X,C)$] of order n? As with Steiner triple systems, the $2$-fold kite system [4-cycle system ] is said to be nested in the $3$-fold block design $(X,B)$. In general we will say that the $\lambda_1$-fold kite system $(X,K)$ is nested in the $\lambda_2$-fold block design $(X,B)$ provided a kite can be selected from each of B so that the resulting collection of kites is K. We have the same definition for the nesting of a $\lambda_1$-fold $4$-cycle system $(X,C)$. Now if the $\lambda_1$-fold kite system $(X,K)$ [$\lambda_1$-fold $4$-cycle system $(X,C)$] can be nested in the $\lambda_2$-fold block design $(X,B)$, then $\lambda_2n(n-1)/12=|B|=|K|=|C|= \lambda_1n(n-1)/8$ implies $\lambda_1= 2k$ and $\lambda_2= 3k$. Hence the general problem of " the nesting for kites and $4$-cycles". We give a complete solution of nesting problem for $2k$-fold kite [$4$-cycle] systems. D.R. Stinson, The spectrum of nested Steiner triple systems, Graphs and Combinatorics, 1985, 189-191. Vishal Gupta Yale University Advisor: James Abello, DIMACS Realizing Simple Polygons from Visibility Graphs Given a polygon P, the visibility graph of P is the graph whose vertices are the vertices of P with two vertices connected by an edge if they are visible in P, that is, if the line segment between them lies inside P. This problem touches many areas and related problems that are "difficult" in the computational sense. This talk will provide a basic introduction the problem of recognizing/characterizing visibility graphs and further describe our current research in a special, fundamental, case of the problem, staircase polygons, specifically realizing a staircase polygon from its visibility graph via group theoretic operations in the Weak Bruhat Order. Dean Hoffman Auburn University A Curiously Different Sort of Graph-Decomposition Problem The typical graph-decomposition problem asks if the edges of the complete graph on n vertices can be partitioned into copies of a given graph G. What if we don't specify G, but rather just specify the number b of copies of G in the decomposition? (For example, if b = 2, we're asking for a self-complementary graph on n vertices.) We give a simple solution to this problem, and also the corresponding problem for indices other than one. Steven Jaslar Rutgers University Advisors: Vladimir A. Gurvich and Khaled Elbassioni, RUTCOR,and William Cuckler, Mathematics, Rutgers University d-embeddablity of Hypergraphs Let S be a finite set of nonzero points in d-dimensional space. Then S is a simplex if it is minimal such that 0 is in the convex hull of S. A hypergraph is d-embeddable if there exists a mapping from its vertex set into d-dimensional space such that every hyperedge is a simplex. In this talk we describe what is known about which hypergraphs are d-embeddable for d = 1, 2. Jonathan Jedwab University of Richmond Designing the IEEE 802.12 transmission code In 1993 S Crouch and I designed a coding scheme for 100 Mbit/s data transmission over copper telephone cabling. This scheme satisfied physical, economic and social constraints, allowing a tenfold increase in transmission speed whilst maintaining error detection capability. In 1995 the Institute of Electrical and Electronic Engineers (IEEE) approved this coding scheme as part of its 802.12 international standard for data transmission. For many years commercial considerations prevented us from revealing the design principles underlying the code structure. However I now have permission to explain how geometrical insight, combinatorial reasoning, and computer search were combined to satisfy all the imposed constraints simultaneously. Sandra Kingan Penn State University, Harrisburg Representability of rank 3 combinatorial geometries A rank 3 combinatorial geometry (simple matroid) consists of a set of points and a family of distinguished subsets of points called lines that satisfy two properties: any two distinct points belong to exactly one line; and any line has at least two distinct points. A geometry is said to be representable over a finite field GF(q), where q is a power of a prime, if there is a rank preserving map from the elements of the geometry to a matrix with entries from GF(q). We show how to use automated matroid generation to study the representability problem for rank 3 geometries. We verify that up to 9 elements all except four rank 3 geometries are representable and the bound on the order of the field is 11. Victor Kostyuk Rochester Institute of Technology Advisor: Michael Capalbo, DIMACS Colored Necklace Bisection Suppose we have a necklace with 2n beads of k different colors, 2ai beads of color i. The necklace bisection problem is to find the smallest number of strings into which a necklace can be cut so that it is then possible to divide the strings into two groups with equal number of beads of every color in each group. Although an exponential in k algorithm for making these cuts is known, the existence of an algorithm polynomial in or independent of k is a long-standing open problem and the subject of my presentation. Esther Lamken Caltech Scheduling CCRR tournaments It this talk, I will describe how to construct CCRRSs, complete coupling round robin schedules, for $n$ teams each consisting of two pairs. The motivation for these schedules is a problem in scheduling bridge tournaments. For $n$ odd, we show that a CCRRS can be constructed using a house with special properties. For $n$ even, a CCRRS is equivalent to a Howell design, $H(2n-2,2n)$, with a special property called Property P. We use a combination of direct and recursive constructions to construct $H(2n-2,2n)$ with Property P. In order to apply our main recursive construction, we need group divisible designs with both odd block and odd group size. One of our main results is the existence of these GDDs. This is joint work with Alan Ling and Gennian Ge. Curt Lindner Auburn University Constructing Quasigroups from Cycle Systems An m-cycle system of order n is a pair (X,C), where C is a collection of edge disjoint m-cycles which partitions the edge set of K_n with vertex set X. Given an m-cycle system we can define a groupoid (X,o) as follows: (i) x o x = x for all x in X, and (ii) if x =/ y, x o y = z and y o x = w if and only if the cycle (....,w,x,y,z,....) belongs to C. It is well-known that the groupoid (X,o) is a quasigroup if and only if the m-cycle system (X, C) is 2-perfect. (2-perfect means that each pair of vertices are connected by a path of length 2 in exactly one m-cycle of C.) This is an elementary survey of results on constructing quasigroups from 2-perfect m-cycle systems. Alan Ling University of Vermont On resolvable packings with block size four (Joint work with Gennian Ge. Shen Hao and Clement Lam) In this talk, we present a result on resolvable packings with block size 4. Particular attention will be given on the direct constructions aspect of this problem. As a result of direct and recursive constructions, it is shown that there are at most 18 possible exceptions for resolvable packings with block size four. Sasha Logan Auburn University Maximal Sets of Hamilton Cycles A set S of edge-disjoint hamilton cycles in a graph T is said to be maximal if the hamilton cycles in S form a subgraph of T such that T-E(S) has no hamilton cycle. The spectrum of a graph T is the set of integers m such that T contains a maximal set of m edge-disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs, all complete bipartite graphs, and most complete multipartite graphs. In this paper we solve one of the two unsolved cases for complete multipartite graphs, giving two substantially different proofs. Karen Meagher University of Ottawa A Construction for Covering arrays Covering arrays are a type of design with many applications. Like most interesting designs they can be difficult to build. In this talk I will give a construction for strength 2 covering arrays based on an algebraic method of Chateauneuf, Colbourn and Kreher. This construction uses a subarray of a covering array and a group action on that subarray. With this construction we can improve the best known upper bounds on the size of many covering arrays 2-CA(n,k,g) with k between g and 2g. Lorenzo Milazzo Universita di Catania New colourings for Steiner systems with different block colour patterns This talk presents last new vertex colourings of Steiner systems S(t,k,v), for t = 2, k = 3 or 4, and for t = 3, k = 4, respect different block colour patterns. New concepts such as upper chromatic number, uncolourability, chromatic spectrum, will be shown. Lucia Moura University of Ottawa Mixed Covering Arrays (Joint work with John Stardom, Brett Stevens and Alan Williams) Covering arrays are generalizations of orthogonal arrays useful for testing systems such as software, networks and circuits. Each parameter of the system corresponds to a row of the array and each test to be performed on the system correspond to a column; the covering array property requires that every possible pair of values for any pair of parameters is covered by some test. A covering array is said to be mixed if each row may take values from different alphabet sizes. In this talk, we present results and constructions for mixed covering arrays. Alexander Rosa McMaster University Extended Petersen graphs PowerPoint Presentation We discuss some properties and an application of yet another class of graphs whose smallest member is the Petersen graph. These graphs, which we call extended Petersen graphs, arise naturally in the context of a construction of Steiner systems S(2,4,v) with maximal arcs but seem to be interesting on their own. Brett Stevens Carleton University Packing arrays and related designs Packing arrays are the natural generalizations of orthogonal arrays, or transversal designs, to packing criteria. We will discuss their definition, construction and bounds on their size. Additionally we will discuss their applications to disk arrays and their relationship to other families of designs including CURDS, packing designs and finite projective planes. Leo Storme Ghent University Blocking sets in projective spaces A $t$-fold $(N-k)$-blocking set in the projective space $PG(N,q)$ of dimension $N$ over the finite field of order $q$ is a set of points intersecting every $k$-dimensional subspace in at least $t$ points. A $t$-fold $(N-k)$-blocking set is called minimal when none of its proper subsets is still a $t$-fold $(N-k)$-blocking set. We present new characterization results on minimal $t$-fold $(N-k)$-blocking sets in $PG(N,q)$, $N \geq 3$, $q=p^h$, $p$ prime, $h \geq 1$. The most important part in obtaining these characterization results is the fact that, presently, for $t$-fold $(N-k)$-blocking sets, of not too large cardinality, a so-called $t$ mod $p$ result is known. This result gives crucial information on the intersection sizes of these blocking sets with the subspaces of $PG(N,q)$, leading to the characterization results. Ida Svejdarova Charles University Advisor: Jozsef Beck, Mathematics, Rutgers University Ultimate Independence Ratio of Wheels In this talk I will introduce the notion of the ultimate independence ratio of a graph and present an open problem (UIR of odd wheels). I will also mention a few results relevant to this problem. Walter Wallis Southern Illinois University Triple Arrays A triple array A is an array with r rows and c columns, based on a set V, having the following properties: (P1) no element is repeated in any row or column; (P2) any member of V occurs k times in the array, for some constant k; (P3) any two distinct rows have the same number of common elements; (P4) any two distinct columns have the same number of common elements. (P5) any row and any column have the same number of common elements. We shall discuss triple arrays. In particular, we prove various constraints on the parameters, and report on the existence of these arrays. Bridget Webb The Open University Teaching Combinatorics to 700 Students per Year The Open University presents the half-credit (30 point) course MT365 Graphs, Networks and Design annually to over seven hundred students. This is a problems-based course, presented in a down-to-earth manner, and is intended for a wide audience. The course evolved from separate plans in the Pure Mathematics Department and the Design Group of the Technology Department to produce combinatorics-based courses. The resulting joint venture continues with an inter-departmental team up keeping and presenting the course. Open University students are adults, mostly in full-time employment, who are studying part-time. They live around the UK and elsewhere. Their backgrounds and experience are diverse?some students studying mathematics courses have no formal mathematics education prior to embarking with the Open University, while others may have had considerable experience. The course MT365 is intended for highly motivated students who do not necessarily have a strong mathematical background. The course is popular with mathematicians, technologists, scientists and computer scientists alike. The emphasis is on solving problems and applying algorithms, rather than understanding proofs; it is very much a "doing" course. The development of combinatorics as a subject is integrated with the modelling of practical situations. In my talk I will discuss this course in more detail; how it was developed, the topics covered, the method of presentation and the ideas behind it.

Page last updated July 8, 2003.