Week 1 Topic: Graph Partitions Edge-colouring bipartite graphs without 2-coloured 4-cycles Joint work with Eric Mendelsohn It is well known that any bipartite graph of maximum degree d
has an edge-colouring with d colours (a proper edge-colouring,
i.e., edges incident with the same vertex have distinct colours).
We have begun an investigation of when this can be done without
2-coloured 4-cycles being present. So far, we have been particularly interested in bipartite graphs
of maximum degree 3, so this is what most of the talk will be
about. Very small embeddings of some partial Steiner triple systems A Steiner triple system of order v is a partition of the edges
of the complete graph on v vertices into triangles. A partial Steiner
triple system of order v is a partition of some subset of the edges of
the complete graph of order v into triangles. Not every partial Steiner
triple system of order v can be completed to a Steiner triple system of
order v, but it is known that any partial Steiner triple system can be
completed to a Steiner triple system of larger order. Such completions
are called embeddings of the partial Steiner triple systems. The Lindner
conjecture states that any partial Steiner triple system of order u can be
embedded in a Steiner triple system of order v whenever v is equivalent
to 1 or 3 (mod 6) and v is at least 2u+1. Although in one sense this is
the best possible result on the embedding problem, some partial triple
systems of order u can be embedded in Steiner triple systems of order
less than 2u+1. Such embeddings will be topic of this talk. Maximal sets of hamilton cycles in complete multipartite graphs In a connected graph G, a set S of hamilton cycles is called
maximal
if G - S contains no hamilton cycle. The spectrum for maximal
sets in G
is the set of numbers m such that there is a maximal set of size
m. The spectrum
for complete graphs and complete bipartite graphs has been studied. We will
look at complete
multipartite graphs.
Complimentary Steiner Triple Systems Joint work with Esther Lamken and Alan Ling A Steiner triple system of order v, STS(v), is a partition of the
edges of the complete graph on v vertices into triangles (called
blocks). It is well known that there are v(v-1)/6 blocks in a
STS(v). In order to generate all the blocks using the cyclic group of
order v, one therefore needs (v-1)/6 base blocks, these base blocks are
called a (v,3,1)-difference family. We will first discuss when there
exists a difference family in which all the blocks are disjoint.
An s-partial resolution of an STS is a partition of the blocks into
partial parallel classes each containing s blocks. Hence the existence
of a difference family with disoint blocks yields a (v-1)/6 - partial
resolution of an STS(v). Two s-partial resolutions R and R' of an
STS(v) are orthogonal if a partial parallel class in R and a
partial parallel class in R' contain at most one block in common. In
this case the blocks of the STS can be placed in a v x v square with
exactly (v-1)/6 blocks in each row and each column and no symbol
appearing twice in any row or column (i.e. each row and column is a
(v-1)/6 - partial parallel class). From the numbers, one sees that it
may be possible to place 6 STS(v) (on the same symbol set) in a v x v
square such that only the diagonals are empty and each of these STS
have the property that the each row and column is a (v-1)/6 - partial
parallel class. It may even be possible that every symbol appears 3
times in all but one row and column (in which it does not appear at
all); and that if the triples are ordered, the square can be
decomposed into 3 mutually orthogonal latin squares of side v.
We will show that such a square exists for all v = 1 mod 6 with at
most 10 exceptions. On graph labelings and graph decompositions Graph labelings were first introduced by Alex Rosa (around 1967) as means
of attacking the problem of cyclically decomposing the complete graph into
other graphs. Since Rosa's original article, literally hundreds of papers
have been written on graph labelings (mostly on beta-labelings, also known
as graceful labelings). Unfortunately however, most of these papers bare
little relation to Rosa's original intent (investigating cyclic
decompositions). In this talk we will review some of the various graph labelings with a
focus on their decomposition applications. The talk is accessible to both
students and teachers of high-school level mathematics.
Fractional Domatic Numbers and Asymptotic Knight Density A "Knight" in Chess attacks two squares horizontally or vertically, and then
one square perpendicular. A set of Knights "cover" a board if a Knight attacks
every empty square. What is the minimum number of Knights needed to cover an
nxn board? This is the domination number of the nxn Knight graph: nodes (i,j)
for all i,j=1,2,...,n and edges between node (i,j) and (k,l) if |i-k||j-l|=2.
A Knight covers at most 9 squares. So at least n^2/9 Knights are needed to
cover an nxn board. However, the sparsest known Knight covers have density 1/8.
What is the asymptotic density? Look at Fractional Domatic Number (FDN): a
maximum fractional packing of a graph with dominations. We show the asymptotic
sparsest density is the inverse of the FDN of the infinite Knight graph.
A dual solution to the FDN problem is a set of weights on the nodes whose sum
in any domination is at least one. For example, consider these weights on the
Knight graph (with denominator of 40). Outside, the weights are 0.
2 3 4 4 3 2 2 6 6 7 7 6 6 2 3 6 8 10 10 8 6 3 4 7 10 10 10 10 7 4 4 7 10 10 10 10 7 4 3 6 8 10 10 8 6 3 2 6 6 7 7 6 6 2 2 3 4 4 3 2
Any set of Knights covering the middle 4x4 lie on squares whose weights sum to
at least 1. These weights add to 8.8. So the FDN of the infinite Knight graph
is at most 8.8, and the asymptotic density of a Knight cover is at least 1/8.8
improving the best known lower bound of 1/9.
These techniques show promise for many asymptotic problems on regular graphs. Cycle decompositions of the complete bipartite graph A bipartite graph is one whose vertex set can be partitioned into
two subsets X and Y, so that each edge has one end in X and
one in Y; such a partition (X,Y) is called a bipartition of the
graph. A complete bipartite graph is a simple bipartite graph with
bipartition (X, Y) in which each vertex of X is joined to each
vertex of Y. If |X| = m and |Y| = n, such a graph is denoted
by Km,n. A 2-fold complete bipartite graph 2Km,n is a
bipartite graph with bipartition (X, Y) in which each vertex of
X is joined to each vertex of Y by exactly 2 edges.
The problem of the existence of a decomposition of the complete graph
Kn(the complete graph from which a 1-factor has been removed,
Kn - F) into cycles of different lengths has been investigated
several times. In this talk first we will
decompose the complete bipartite graph Km,n (K2n+1,2n+1 - F,
where F is a 1-factor of K2n+1,2n+1) into cycles of lengths
4, 6, or 8. Second, we will show the decompositions of 2-fold
complete bipartite graph 2Km,n into cycles of lengths 4,
6, or 8 for each positive integers m, n and m <= 2, n <= 2.
Then, we will decompose the 2-fold complete tripartite graph
Kp,q,r into most cycles, that is, pq + /lceil (p + q)r/2 /rceil
cycles,
for each triple p, q, r of positive integers and p <= q <= r. Traffic Flow Theory and Transportation Networks The workings of traffic flow theory and flow networks have long been
used to analyze and optimize traffic patterns, especially in urban areas.
While traffic flow theory associates with the properties of a vehicle or
vehicles on a road given different localized conditions, transportation
networks deal with the interrelations of many roads as a whole, taking the
length and optimum flow on a road to find optimizations on many roads.
Transportation networks are represented by weighted graphs or digraphs
in which edges are roads and vertices are intersections. To make this model
realistic in problems such as optimization, metrices are assigned to each
edge, along with a flow, which is often determined by the metric space.
Several properties associated with metric spaces are non-negative distances,
symmetry, and the triangle inequality. In transportation networks, the
symmetric property can be ignored due to one way streets, which are
represented by directed edges.
Traffic flow theory uses equations to model the properties of cars with
respect to position and time. The fundamental relation in traffic flow
theory is: Flow = Density x Speed. In other flow theories, such ones that
deal with water flow through pipes, density and speed are independent
variables. However, in traffic flow theory, density and speed are dependent
on each other, and on flow. Traffic flow theory^Òs applications extend to
describing the motion of one car on a highway to determining the effect
several cars have on each other.
Complement domination Let D be a weakly connected digraph, and assume D
contains no loop nor multiple arc. If u and v are
vertices of D, then u dominates v if and only if
(u,v) is an arc of D. In this paper, an algorithm
for solving the following problem is given. Given
D and a positive integer k, is it possible to
partition the vertex set of D into two non-empty
sets X and Xc (the complement of X) such that Cycle Decompositions of Kn and Kn-I It is natural to ask when a complete graph on n vertices admits a
decomposition into cycles of a fixed length. The necessary conditions
are that n is odd and that the number of edges in the complete graph is a
multiple of the cycle length. This question can be extended to complete
graphs with an even number of vertices by removing a 1-factor. We will
discuss the solution when the number of vertices in the complete graph and
the cycle length are of the same parity. Anti-Pasch Steiner Triple Systems A Pasch configuration in a Steiner triple system is a collection of four
triples whose union has cardinality six.
Such a configuration must be isomorphic to {a, b, c}, {a, y, z}, {x, b, z}
and {x, y, c}. An anti-Pasch Steiner triple system is one which contains no Pasch
configurations. It is well known that Steiner triple systems, STS(v), exist if and only if v
= 1 or 3 (mod 6). and it has been a long standing conjecture that anti-Pasch
Steiner triple systems also exist for all these values except for v = 7 or
13. The case in which v = 3 (mod 6) was first solved by Brouwer in 1979. The case in which v = 1 (mod 6) appears to be more problematical but has
also recently been solved. The details are in two papers, the first by Alan Ling, Charlie Colbourn,
Mike Grannell and myself and the second by Mike Grannell, Carol Whitehead
and myself which will appear this year. In this talk I will describe the stages in the eventual solution of the
anti-Pasch problem and put it in context of what further problems still need
to be considered. The Mathematics of Software Engineering Software affects almost every aspect of our lives in the 21st century. It
manages our telephone networks,
nuclear power plants, air-traffic control systems, and our banking and
financial institutions -
to name just a few. Unfortunately many software systems are "fragile" in the
sense that they are unreliable,
suffer from security and performance lapses, and are difficult to maintain and
upgrade to satisfy new demands.
Software Engineering, as it is practised today, is an art rather than a
science. This talk will discuss
research in Software Engineering, the creation and analysis of mathematical
models of software systems,
and how these ideas promise to provide tools for combatting the fragility of
software.
Path Partitions and Colorings in Directed Graphs In this talk we present some results and open problems related to path
partitions, path coverings, and colorings in directed graphs.
A path partition in a directed graph G is a set of vertex-disjoint paths
that cover the vertex set of G. Dilworth's Theorem states that if G is a
di-graph of a poset, then the minimum number of paths in a path partition
equals the size of a maximum independent set in G. Greene and Kleitman
extended Dilworth's Theorem by considering, for each positive integer k, a
collection of k disjoint independent sets in a poset. Berge made a
conjecture in 1982 extending the Greene-Kleitman Theorem to all di-graphs.
The conjecture is still open. We present some other conjectures and results
extending the Greene-Kleitman Theorem to all di-graphs.
Perfect graphs and good charactarizations We give an introduction to vertex coloring, perfect graphs, and good characterizations, with examples to illustrate the intimate interconnections among these. On packing subgraphs in a graph Let G be a graph and F a connected subgraphs of G.
A subgraph H of G is called an F-packing if each component
of H is isomorphic to F. The F-packing problem is that of
finding an F-packing having the maximum number of vertices
(or, the same, the maximum number of components). A spanning F-packing of G is called an F-factorization of G.
It provides a partitioning of V(G) into subsets each of which
induces in G a subgraph isomorphic to F. If F is of two vertices then the F-packing problem is
a classical matching problem that can be solved in polynomial
time. If F has at least three vertices (for example, F is a
3-vertex path) then the F-packing problem is known to be NP-hard. We consider the F-packing problem when F is either a 3-vertex
path or, more generally, a tree. We will discuss for some classes of graphs (1) asymptotic results (due to A. Kelmans, D. Mubayi, B. Sudakov), (2) approximation and worst case results
(due to A. Kelmans, D. Mubayi), and (3) exact results
(due to A. Kaneko, A. Kelmans, T. Nishimura). A small embedding for partial 4-cycle systems A partial 4-cycle system of order n can be embedded in a
4-cycle system of order approximately 2n + (square root)2n. This isn't
the best possible result.....but it's pretty good. The best result is
probably around n + (square root)n. This is a very elementary talk and is
designed to generate interest in reducing the known bound. Self-Complementary Graphs and Their Lexicographic Products A graph G is said to be self-complementary if it is isomorphic to its complement. Given a pair of graphs G and H, their "lexicographic product" G[H], is ontained by replacing each vertex of G by a copy of H, and each edge of G by the edge set of the complete bipartite graph adjoining the two indicated copies of H. For arbitrary graphs, the automorphism group A(G[H]) contains the wreath product of A(G) and A(H), in some cases properly. Given two self-complementary graphs G and H, it is true that their lexicographic product G[H] is self-complementary. It is also true that when G and H are self-complementary, in the construction of the lexicographic described above, each copy of H is a block of imprimitivity of the automorphism group A(G[H]). In consequence, A(G[H]) is precisely the wreath product of A(G) and A(H). Both of these claims are believed to be new. Two other new claims are given: First, for each positive integer n, their exists a unique graph Un which satisfies the folowing three constraints: i. Its order is 4n. ii. It is self-complementary. iii. It has a unique matching. The second new claim is that the degree sequence of a self-complementary graph of order 4n is distinguished by the following trait: Given any j between 1 and 2n, the sum of the degrees of the 2j vertices of least degree is at least 2j2. This bound is best possible, and is realized for each j in [2n] by Un. Some partition problems involving Hamiltonian Paths Let G be a connected graph. An edge e of G is called a Hamiltonian Path
Edge, if there exists a Hamiltonian path in G that contains e. Since every
edge in G is either a Hamiltonian path edge or not, the edges E(G) of G are
uniquely partitioned into two sets Y(G) and N(G), where Y(G) is the set of
Hamiltonian path edges of G. Clearly, if G does not contain a Hamiltonian
path, then E(G) = N(G) and if every edge is in some Hamiltonian path of G,
then E(G) = Y(G). Problem 1. Characterize graphs G such that E(G) = Y(G). Problem 2. Determine the (Y, N) partition of E(G) for well known and/or
interesting graphs G. By an f-graph we mean a graph having no vertex of degree greater than f.
Let U(n, f) denote the graph with vertices the set of unlabeled f-graphs
of order n. A pair of f-graphs {G, H} is an edge in U(n, f) if and only if
H can be obtained from G by the addition of a single edge. Variations of graphs of this type play a role in a variety of contexts. For
example, G can be the transition digraph for a random process, the vertices
of G can be interpreted as molecular graphs, or G can be studied strictly
with respect to its graph theoretical properties. It is of particular
interest that the study of such graphs ranges from topics suitable for an
introduction to graph theory with quite elementary problems to problems
that are considered very difficult. As an illustration, consider the
following. Problem 3. For what values of n and f does U(n, f) contain a Hamiltonian
path? Problem 4. For what values of n and f does U(n, f) have a perfect matching? We shall report on the status of our work in progress concerning Problems 1
to 4. Embedding Extended Mendelsohn Triple Systems Vince Castellana and Michael Raines n extended Mendelsohn triple is an ordered triple of the form
(x,x,x), (x,x,y), or (x,y,z), called a loop, a directed
lollipop, and a directed 3-cycle, respectively. An extended
Mendelsohn triple system (V,B) of order n and index \lambda, or
EMTS(n, \lambda), is a collection B of extended Mendelsohn triples
defined on an n-set V such that every ordered pair of (not
necessarily distinct) elements of V is contained in exactly \lambda
extended triples of B. An extended Mendelsohn triple system (V, B) of
order n and index \lambda is said to be embedded in an extended
Mendelsohn triple system (V', B') of order v and index \lambda if
V \subseteq V' and B \subseteq B'. In this talk, we give necessary
and sufficient conditions for embedding an EMTS(n,\lambda) in an
EMTS(v, \lambda). Partitions of tournaments into transitive subtournaments In this talk we consider partitions of the vertex sets of tournaments so
that the blocks induce transitive subtournaments. Such partitions are easy
to find if there is no restriction on the orders of the transitive
subtournaments and if there is no restriction on the number of transitive
subtournaments. Indeed, merely remove the largest transitive
subtournament, then iterate this in the remaining subtournament. We treat
two problems concerning partitions of tournaments into transitive
subtournaments. In the first problem all transitive subtournaments are
to be the same order (and, hence the number of such transitive
subtournaments is fixed). In the second problem the number of transitive
subtournaments is fixed (but their orders may vary).
From Garbage to Rainbows: The Many Applications of Graph Coloring The simple concept of coloring a graph has a long history and has been
a fundamental idea in graph theory. This talk will survey its many
applications, such as channel assignments in telecommunications,
task scheduling, traffic phasing, fleet assignment, and mobile radio
frequency assignment. We will also describe generalizations of the
standard notion of graph coloring that arise from applications. Amalgamations of graphs In this talk, amalgamations of graphs will be described, some of the history of their uses will be presented, and latest applications of the technique will be discussed. Specialized Colouring and Maximal Arcs We consider colourings of Steiner triple systems and Steiner
systems S(2,4,v) in which blocks have prescribed colour patterns, as a
refinement of classical weak colourings. We study the question of the
existence of a colouring of given type in which exactly k colours are
used, as well as the question of uncolourable systems. We also examine
the related question of the existence of S(2,4,v) with maximal arcs. "Geometric" Graph Partitions Certain partitions of graphs occur as a byproduct of other investigations.
For instance, the edge set of K12 can be partitioned into 2 disjoint
copies of an icosahedron plus a 1-factor. The edge set of the complete
graph K2n can be partitioned into two copies of "some" G(2n,n-1) graphs
(G(2n,n-1) an (n-1)-regular graph of order 2n) plus a 1-factor. Who are
these graphs? Can these partitions be "extended uniformly" so that all
edges will be treated equal? For instance, 5K12 can be partitioned into
11 copies of an icosahedron so that each edge appears in 5 icosahedra.
These partitions are a "natural" byproduct of some geometric structures.
These topics and some related open problem will be discussed. Asymptotically optimal tree-packings in regular graphs Given a graph G and a family F of graphs,
an F- packing of G is a subgraph of G each of
whose components is
a member of F. The F-packing problem is to find an
F--packing of the maximum number of vertices.
The very special case of F-packing when F=K2, a single edge, is
simply that of finding the size of a maximum matching. This problem is
well-studied,
and can be solved in polynomial time. On the other hand,
the F-packing problem even when F is a path of length at least two,
is known to be NP-complete. Here we consider an asymptotic version of this problem, where F
consists of a single member that is a tree with t vertices. Our main
result is
the following. Let T be a tree on t vertices and let
e > 0. Suppose that G is a
d-regular n vertex graph
satisfying d >= (128t3/e2)ln(
128t3/e2).
Then G contains
(1-e)n/t vertex disjoint copies of T. Amalgamations of graphs as a tool for k-factor embeddings A. J. W. Hilton, C. A. Rodger, E. B. Wantland* Given graphs G and H with |V(G)| >= |V(H)| and |E(G)| = |E(H)|,
we say H is an amalgamation of G (or G is a detachment of H)
if there exist a bijection f: E(G) -> E(H) and a surjection
p: V(G) -> V(H) such that: i) if e is an edge in G joining x and y, then f(e) is an edge
in H joining p(x) and p(y) (if p(x) = p(y) then f(e) is a loop),
and ii) if e is a loop on x in G, then f(e) is a loop on p(x) in H. In this presentation we will discuss necessary and sufficient
conditions for the embedding of an edge-colored graph H into
an edge-colored graph G in which the edges of each color
induce a k-factor. We will give results when H and G are
complete graphs or complete multipartite graphs and for
different edge-connectivity conditions on the k-factors.
We will obtain these results by investigating necessary
conditions on amalgamations of k-factorizations and then
showing when these are sufficiaent by reconstructing a
k-factorization from an amalgamation.
|