What the Hell do Graph Decompositions have to do with Experimental Designs?
Motivating Graph Packings and Coverings of Non-Complete Graphs
“Old Bob” Gardner Math Department Seminar January 27, 2012
Complete Graphs:
Comparing Samples
Note. Suppose you have a collection of v samples and you wish to compare a property of the samples.
1
2
3
v
. . .
A special thanks to the Institute of Quantitative Biology for the use of several hypothetical mice!
Note. However, the samples are compared by running them in the Motivationtron 3000® three-at-a-time. The machine cannot be calibrated from run to run and so the only way two samples can be compared is to run them together in the machine.
Motivation- tron 3000®
1
2
3
1
2
3
The Question: When (and how) can all of the v samples be optimally compared to each other by running the
machine times?
Motivationtron 3000®
Note. The solution to this question is equivalent to finding a K3–decomposition of Kv, where each vertex of Kv represents a sample, an edge joining two vertices represents a comparison of the two corresponding samples, and a copy of K3 represents a run of the machine.
0
1
3
2
0
1
2
3
Definition. A decomposition of a simple graph G with isomorphic copies of graph g is a set
{g1, g2, … , gn}
where gi g and V(gi) V(G) for all i, E(gi) ∩ E(gj) = Ø if i ≠ j, and
gi = G.
Example. There is a decomposition of K5 into 5-cycles:
=
U
Example. There is a decomposition of K7 into 3-cycles:
1
2
5
2
0
1
6
3
4
(0,1,3)
(1,2,4)
(2,3,5)
(3,4,6)
(4,5,0)
(5,6,1)
(6,0,2)
3
Definition. A Steiner triple system of order v, STS(v), is a decomposition of the complete graph on v vertices, Kv , into 3-cycles.
From the Saint Andrews MacTutor History of Mathematics website.
Jakob Steiner
1796-1863
J. Steiner, Combinatorische Aufgabe, Journal für die Reine und angewandte Mathematik (Crelle’s Journal), 45 (1853), 181-182.
v ≡ 1 or 3 (mod 6) is necessary.
M. Reiss, Über eine Steinersche combinatorsche Aufgabe welche in 45sten Bande dieses Journals, Seite 181, gestellt worden ist, Journal für die Reine und angewandte Mathematik (Crelle’s Journal), 56 (1859), 326-344.
Theorem. A STS(v) exists if and only if v ≡ 1 or 3 (mod 6).
Note. Sufficiency follows from Reiss.
Thomas P. Kirkman
1806-1895
From the Saint Andrews MacTutor History of Mathematics website.
T. Kirkman, On a problem in combinations, Cambridge and Dublin Mathematics Journal, 2 (1847), 191-204.
STS(v) iff v ≡ 1 or 3 (mod 6).
Note. So the Motivationtron 3000® can efficiently compare v samples (without duplication or omission) if and only if the number of samples v satisfies: v ≡ 1 or 3 (mod 6).
Motivation- atron 3000®
1
2
3
1
2
3
THIS IS WHAT DECOMPOSITIONS HAVE TO DO WITH EXPERIMENTAL DESIGNS!!!
Note. The Gizmotron 5000® runs with 5 samples inserted, but has the curious property that it does not compare each sample to the others, but instead makes comparisons as given schematically here:
Gizmotron 5000®
Definition. The 4-cycle with a pendant edge is denoted H and is:
= H
The graph H is sometimes called a kite.
We call H, for personal reasons, the Hoser graph.
c
b
e
d
a
(a,b,c,d;e)
A Cyclic H-Decomposition of K11
0
1
2
3
4
5
6
7
8
9
10
(5, 3, 0, 1; 10)
2 3 1
5
4
Theorem. An H-decomposition of Kv exists if and only if v ≡ 0 or 1 (mod 5) and v ≥ 10.
J. C. Bermond, C. Huang, A. Rosa, and D. Sotteau, Decompositions of Complete Graphs into Isomorphic Subgraphs with Five Vertices, Ars Combinatoria 10 (1980), 211-254.
Dominique Sotteau
From: http://www.d.umn.edu/~dfroncek/alex/ and http://www-direction.inria.fr/international/DS/page_personnelle.html
Alex Rosa
Bipartite Graphs:
Two Populations Sampled
. . .
. . .
Note. Suppose you have a collection of m samples from one population (say white mice) and a collection of n samples from a second population (say brown mice). You are interested in comparing the two populations and hence in comparing each white mouse to each brown mouse.
11
21
31
m1
12
22
n2
11
21
31
41
51
12
22
(12, 11, 22 , 21 ; 31)
(22, 41, 12 , 51 ; 31)
Example. An H-decomposition of K5,2
Theorem. An H-decomposition of the complete bipartite graph, Km,n, exists if and only if mn ≡ 0 (mod 5), m ≥ 5, and n ≥ 2.
Brandon Coker, Gary Coker, and Robert Gardner, Decompositions of Various Complete Graphs into Isomorphic Copies of the 4-Cycle with a Pendant Edge, submitted to International Journal of Pure and Applied Mathematics.
Complete Graph with a Hole:
New Samples Added to Old
Note. Suppose you have already performed comparisons on a collection of w samples and then you get additional samples (say, another v – w samples). To analyze the total collection of v samples, you need to compare the new samples to the old and compare the new samples to each other.
11
21
32
w1
12
22
(v-w)2
. . .
42
Definition. The complete graph on v vertices with a hole of size w is the graph with vertex set V(K(v,w))= Vv-w U Vw, where │ Vv-w│= v – w and │Vw│ = w, and edge set
The Complete Graph with a Hole
U
/
E(K(v,w)) = {(a,b) │ a, b ϵ V(K(v,w)), {a,b} Vw }.
. . .
Vw
Vv-w
Example. An H-decomposition of K(7,2).
11
21
(52, 22, 32, 42; 11)
(12, 22, 42, 11; 21)
(32, 11, 22, 21; 12)
(52, 21, 42, 12; 32)
12
22
32
42
52
Theorem. There is an H-decomposition of K(v,w) if and only if │E (K(v,w)│ ≡ 0 (mod 5), v – w ≥ 4, and (v,w) ϵ {(5,1),(6,1)}.
Brandon Coker, Gary Coker, and Robert Gardner, Decompositions of Various Complete Graphs into Isomorphic Copies of the 4-Cycle with a Pendant Edge, submitted to International Journal of Pure and Applied Mathematics.
/
Dr. Bob
G.D. Coker
Ron Bollschweiler
Ronald Reagan’s house
What if a Graph Decomposition Does Not Exist?
Note. If a g-decomposition of G does not exist, then we can ask: “How close to a decomposition can we get?”
For example, the Motivationtron 3000® can only be efficiently used to compare v samples if there exists a Steiner triple system of order v – that is, if v ≡ 1 or 3 (mod 6). What should we do with, say, 8 samples?
?
Note. Since we know there is no Steiner triple system of order 8, we know that we will need to either:
This leads us correspondingly to two ideas related to graph decompositions.
Note. In our first approach, we can try comparing as many of the samples as possible, without repetition of comparisons (it might be that running the Motivationtron 3000® is expensive). In terms of the associated graph theory problem, this means getting as many copies of K3 as possible (based on a vertex set of size 8) without repeating edges. This leads to a packing of K8 with copies of K3.
Graph Packing
Example. A Maximal K3-packing of K8.
Notice that each vertex of K8 is of degree 7 (odd) whereas each vertex of K3 is of degree 2 (even). So in any union of K3’s, each vertex will be of even degree:
DEGREE:
0
2
4
6
Therefore, as we pack copies of K3 into K8 (in which each vertex is of odd degree 7), we will have at least one edge absent from each vertex in the collection of K3’s. This collection of “missing” edges form the leave of the packing. Since each vertex must be an element of at least one edge in the leave, then the leave must consist of at least 4 edges. If we are lucky, the leave of this packing will form a perfect matching of K8. Here is such a packing:
0
1
2
3
4
5
6
7
(0,4)
(1,5)
(2,6)
(3,7)
(0,1,3)
(1,2,4)
(2,3,5)
(3,4,6)
(4,5,7)
(5,6,0)
(6,7,1)
(7,0,2)
Leave
Packing
Definition. A maximal packing of a graph G with isomorphic copies of a graph g is a set {g1, g2, …, gn} where gi ≈ g and V(gi) V(G) for all i, E(gi) ∩ E(gj) = Ø for i ≠ j,
gi G,
and
is minimal. The edges of G not in any gi form the leave of the packing.
Theorem. A maximal H-packing of Kv , v ≥ 5, has leave L where │E(L)│ = │E (Kv)│ (mod 5), except when v ϵ {5,6} in which cases │E(L)│ = 5.
Brandon Coker, Gary Coker, and Robert Gardner, Packings and Coverings of Various Complete Graphs with the 4-Cycle with a Pendant Edge, in preparation.
Brandon Coker, Gary Coker, and Robert Gardner, Packings and Coverings of Various Complete Graphs with the 4-Cycle with a Pendant Edge, in preparation.
We are also exploring H-packings of complete bipartite graphs and complete graphs with a hole.
Note. In our second approach, we insist on comparing every pair of samples. In the event that there is not a decomposition of the corresponding graph, this will require the repetition of some comparisons. We want to minimize the repeated comparisons. In terms of the associated graph theory problem, this means finding a collection of copies of K3 which include all edges of Kv and for which the number of repeated edges is minimized. For example, suppose we want to compare 6 samples on the Motivationtron 3000®. This leads to a K3 covering of K6, as follows:
Graph Covering
Padding
0
1
2
5
3
4
(0,3)
(1,4)
(2,5)
Covering
(0,1,3)
(1,2,4)
(2,3,5)
(5,0,2)
(4,5,1)
(3,4,0)
may not be simple and may be a
multiset).
Definition. A minimal covering of a simple graph G with isomorphic copies of a graph g is a set {g1, g2, … , gn} where gi ≡ g, V(gi) V(G), E(gi) E(G) for all i,
and
is minimal (when considering coverings, the graph
Brandon Coker, Gary Coker, and Robert Gardner, Packings and Coverings of Various Complete Graphs with the 4-Cycle with a Pendant Edge, in preparation.
Theorem. A minimal H-covering of Kv, v ≥ 5, has padding P where |E(P)|=5 − |E(Kv)| (mod 5), except when v ϵ {5,6} in which cases |E(P)|=5.
12
11
21
31
41
51
Can we Cover K5,1 with H?
NO! H is not a subgraph of K5,1!
12
11
21
31
41
51
(12, 11, 41, 21; 31)
(12, 11, 21, 51; 31)
Can we Cover K5,1 with H?
Well… maybe!
12
11
21
31
41
51
(12, 11, 41, 21; 31)
(12, 11, 21, 51; 31)
Can we Cover K5,1 with H?
Well… maybe!
But these edges are not in the original graph.
Note. Most studies of coverings have involved G = Kv, so the condition that the copies of g are subgraphs of G is trivially satisfied. But when G is not a complete graph, there is no obvious reason to impose the subgraph condition. Returning to the testing-of-samples story, we see no reason to disallow, for example, the testing (or re-testing) of two samples in the hole of K(v,w). Therefore, we are motivated to refine the definition of a graph covering into two cases - one case in which edges that are not in G are forbidden from use in the copies of g, and a case in which these edges are not forbidden.
Definition. A minimal unrestricted covering of graph G with isomorphic copies of a graph g is a set {g1, g2, …, gn} where gi ≡ g, V(gi) V(G),
and
is minimal. (Notice that we do not make the restriction
E(gi) E(G).)
12
11
21
31
41
51
(12, 11, 41, 21; 31)
(12, 11, 21, 51; 31)
Padding
{(11,41), (21,41), (21,41), (21,51), (31,12)}
This is an Unrestricted Covering of K5,1 with H
may not be simple and may be a
multiset).
Definition. A minimal restricted covering of a simple graph G with isomorphic copies of a graph g is a set {g1, g2, … , gn} where gi ≡ g, V(gi) V(G), E(gi) E(G) for all i,
and
is minimal (when considering coverings, the graph
A Restricted K3 Covering of K1,2,3
Each degree 3
Need 3 + 3 =6 edges from between these partite sets (need 4 more)
Need 3 more edges from between these sets
So padding must consist of at least 7 edges.
A Restricted K3 Covering of K1,2,3
A Restricted K3 Covering of K1,2,3
So padding does consist of 7 edges.
An Unrestricted K3 Covering of K1,2,3
●11 edges in K1,2,3
Each degree 3, so must add an edge to each in the padding
●Need 2 more edges: 11+2=13
●Must have a multiple of 3 edges; need 2 more edges. The padding must have at least 4 edges.
Padding has exactly 4 edges!
Note. So, there is a difference between minimal restricted and minimal unrestricted coverings, even when graph g is a subgraph of G.
Restricted
Unrestricted
E(P)=7
E(P)=4
Brandon Coker, Gary Coker, and Robert Gardner, Packings and Coverings of Various Complete Graphs with the 4-Cycle with a Pendant Edge, in preparation.
We are exploring minimal restricted and minimal unrestricted H-coverings of complete bipartite graphs and complete graphs with a hole.
Conclusion