Switching Classes

Hage
%TOC%

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 [[Publications][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 
<A HREF="http://www.math.binghamton.edu/zaslav/Bsg/index.html">here</A>.

<P>Another useful link is the following link to 
<A HREF="http://www.maths.gla.ac.uk/~es/twograph/twograph.html">the site of Ted Spence</A> 
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
<A HREF="http://www.cs.uu.nl/~jur/phd.pdf">here</A>. I appreciate it if you 
<A HREF="mailto:jur@cs.uu.nl">e-mail me</A> 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.95, sentence after Theorem 6.7. 
  verwijder "since the stabilizers Stab(g) and Stab(h) are conjugate"
  (dat kun je beter op regel 3 zeggen)-->
   * 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)"

Whether you have a copy of the Stellingen or not, you still might want
to download this <A HREF="stellingen.pdf">version</A>.
It is the same file as I sent to the company which printed the book, but they 
used buggy software on an older version and it came out without the necessary 
math minus signs.

---++ Switching in practice

I built a small applet years ago to do some interactive switching.[[http://www.cs.uu.nl/people/jur/switching.html][Click]]

-- Main.JurriaanHage - 06 Dec 2004