Home
Address
Schedule
Personal
Research
Publications
Supervised MSc Theses
Ph D Students
Master Students
Reports
Talks
Downloads
Projects
Helium
Holmes
Marble
Neon
Top
Open projects
Master projects
Experimentation projects
Teaching
FP | SP
APA | COSC Coll
EA | B3SO
My other websites
IFL Symposia Axiom of Choice
iO Pages
Master OAC
Center
Master Program
Stc
Switching Classes
Hage
I wrote my Ph D on the subject of switching classes.
My view points were alternately
the combinatorial, algorithmic and algebraic one, including combinations of these.
The results in the Ph D are mostly based on the switching classes papers listed
in my publication list, but include some new
results as well.
In the thesis, the proofs are sometimes more detailed and there
are quite a few examples to explain the results.
What are switching classes?
Concisely put: switching classes are equivalence classes of undirected graphs. Two graphs are equivalent if they can be switched into each other. Given a graph G on a vertex set V, one can obtain a switch of G by selecting a subset of the vertices, call that set S, and by then removing all edges between S and V-S in G that exist, and by inserting all edges between S and V-S that do not. Much more general models exist in which we consider directed graphs labelled with elements of a group, under a certain "reversibility" constraint. This is the subject of the second part of my thesis.Publications in this area
Consult my publication list (those including the word switching and the publication about enumerating submultisets are related to switching classes). Of course, there are many more such publications by other authors. A comprehensive listing can be found in the form of Zaslavsky's dynamic library which can be obtained through here.Another useful link is the following link to the site of Ted Spence which has files listing generators of switching classes up to isomorphism and complementation.
My Ph D thesis
You can download the complete book (152 pages) in PDF-format by clicking here. I appreciate it if you e-mail me when you download it. The printed version contains a few mistakes, hence the errata below. If you have found any errors, then please let me know by e-mail jur@cs.uu.nl. If you see something that you suspect might be wrong, then it is wise to check here to see whether anybody has had the same problem. I have omitted a few very innocent mistakes, typo's like fnuction instead of function. It goes without saying that in the dowloadable version of the thesis, all listed mistakes have been corrected.- p.29, first line of Section 3.1. "iniators" ==> "initiators"
- p.30,-7. X is not constant on \sigma, but \sigma is constant on X
- p.35,+5. Lemma 3.13 ==> Theorem 3.13
- p.35, in Example 3.16 replace "We obtain....respectively" with "We obtain a triangle with two leaves at one of its vertices, an edge with three isolated vertices, and a $C_4$ with a leaf at one of its vertices, respectively."
- p.35, 2nd line of the proof of Thm.3.17. "odd order" ==> "odd degree"
- p.36,+2. put the intersection between | and |
- p.36,+4. "A is even" ==> "|A| is even".
- p.37,+14. Lemma 3.13 ==> Theorem 3.13
- p.37,+22. "u \in T" ==> "u \in V"
- p.38, first line of Section 3.4.1. "Lemma 3.8" ==> "Corollary 3.8"
- p.40, Corollary 3.25, "(n-d(n))+1+" ==> "(n-1-d(n))+1+"
- p.41, line 7 of the proof of Thm.3.29. "NP-complete by" ==> "NP-complete and so the problem is NP-complete by"
- p.45, Corollary 3.39. "NP-complete" ==> "NP-hard"
- p.49, line before Corollary 4.3. K_{n,n} ==> K_{n/2,n/2}
- p.49, proof of Corollary 4.4. "Theorem 3.13" ==> "Theorem 3.14" which is clearer
- p.50, Lemma 4.6. "an acyclic graph" ==> "acyclic graphs"
- p.54, proof of Theorem 4.8. This proof has been optimized quite a bit, by explicitly taking care of the case p=n+2 so that a number of special cases can be dropped.
- p.55, sentence above Figure 4.7. "rightmost" ==> "leftmost"
- p.57, last line. Add "see Figure 4.8(b) and Figure 4.8(c) respectively"
- p.67,-2. add the line "Let the selector \tau be such that (G-u)^\tau is acyclic" before the line starting with "Without restriction..."
- p.68,+15. "induced (6-1)" ==> "induced (6-1')"
- p.70,+9. "case (i)" --> "Claim (i) and Claim (ii)"
- p.77,+7. "A. Tijdeman" ==> "R. Tijdeman"
- p.85,+9 of Example 5.14. Twice "(1,0)" -> "(0,1)"
- p.91,+12. "horizon" ==> "horizon u"
- p.91,+13. "Lemma 3.9" -> "Lemma 5.18"
- p.93, Lemma 6.3(iv). "\delta\neq id" ==> "\delta is not the identity on Z(\Gamma)"
- p.94,+12. "take a = 1_\Gamma" ==> "take g(uv) = 1_\Gamma"
- p.94,-4. "thus \alpha_g(\tau) is uniquely" ==> "thus \tau is uniquely"-->
- p.94-95. Theorem 6.6 is incorrect. It has been modified.
- p.96, line 1 of the proof of Theorem 6.10. "Lemma 5.18" ==> "Lemma 6.5"
- p.99,-10. "also g^\sigma = g" ==> "also g_T^\sigma = g_T"
- p.100, last sentence of the proof. For clarity, "Thus," ==> "Thus, Stab(\hat{g}) = "
- p.100,-15. "A^2(\hat{g})" ==> "A(\hat{g}-2)"
- p.100,-14. "[\hat{g}]" ==> "|[\hat{g}]|"
- p.100,-13. "[g]" ==> "|[g]|"
- p.100,-2. "A^2(\hat{g})" ==> "A(\hat{g}-2)"
- p.103,+13. "Lemma 5.18" ==> "Corollary 5.19"
- p.112, Example 7.27. Add "(see also Example 6.18)" at the end of the line ending with "is indeed the case"
- p.114,-6. "\Gamma" ==> "\gamma"
- p.114,-2. "In that sense Theorem 7.30" ==> "In that sense the proof of Theorem 7.30"
- p.114,-1. "the one corresponding" ==> "the corresponding"
- p.121, last line of the proof of Lemma A.3. Remove the superfluous "|" following "m^{p+1}"
- p.129, 11 of Section A.4. "S^k_q" ==> "S(k,q)"
- p.129, 12 of Section A.4. "to indicate the value x_j" ==> "to indicate the value x_{j+1}"
- p.130,+10. "Because 1 = \rho(6,54)" ==> "Because 1=\rho(6,48) (note that 130 is the 48th leaf in the tree of Figure A.6)"
- p.130,-6, "p=\rho(k,l)" ==> "p=\rho(k,l+1)"
- p.131,-5, add "(in fact, they would be number 47 and 48 in that sequence)"