## Archivos EMALCA

Aquí voy a poner los archivos relativos al curso de Matemáticas discretas que estoy impartiendo en la EMALCA.

## Using naquadah theme in Emacs

I have been using Naquadah theme in Emacs for some time now, and I think it will be a while until I decide to change. I put the following code in my .emacs after requiring it to modify it a little:

(custom-theme-set-faces
(mode-line ((t (:height 0.7 :background "gray20"))))
(mode-line-inactive ((t (:height 0.7))))
(gnus-header-name ((t (:height 1.2 :bold t :foreground "sky blue"))))
(gnus-header-from ((t (:height 1.2 :bold t :foreground "orange3"))))
(gnus-header-subject ((t (:height 1.2 :foreground "cyan3"))))
(gnus-header-to ((t (:height 1.2))))
(font-lock-function-name-face ((t (:foreground "MediumOrchid1" :bold t))))
'(ido-first-match ((t (:foreground "orange" :bold t))))
'(ido-only-match ((t (:foreground "yellow"))))
'(ido-subdir ((t (:foreground "magenta1"))))
'(minibuffer-prompt ((t (:background "magenta4" :foreground "orange1"))))
)


After this, my Emacs looks like:

## Replacing characters in math mode only

Recently I had to change notation in a LaTeX document: a graph I had named $H$ had now to be named $L$. The post Replace something in math mode only by Ralf Angeli (from January 2007), helps with that. However the function query-replace-regexp-eval mentioned there, is obsoleted since Emacs 22.1, (or so says C-h f). The following works for me in Emacs 23.2 (requires the function texmathp from AUCTeX):

M-x query-replace-regexp RET H RET \,(if (texmathp) "L" "H") RET

The idea behind it, is that the regular expression H has to be replaced with the result of evaluating (if (texmathp) "L" "H"), which is L inside math mode and H not inside math mode.

Note that after the last RET, the first question can be answered ! to make all replacements without further questions.

## Support for 4 font families in LaTeX

Mohamed El Morabity has recently provided support for four beautiful font families in LaTeX. I was specially pleased to have Droid Sans, which is the one I use for my GNOME window titles. I tested these families for the special characters in Spanish:

So they are all included, except that Cantarell has a very funny ¿.

## Graph theory in Sage

Even though there are already fine guides in the web to start using the Sage software for graph theory, such as this, a video, and this, I wanted to write a simple one for my students. We have been studying the cubic graphs with eight vertices. And we already know the answer, but we want to ask the computer which of those graphs are vertex transitive.

We obtain the first graph putting together two copies of $K_4$:

sage: k4=graphs.CompleteGraph(4)
sage: g1=k4+k4
sage: g1.is_vertex_transitive()
True



We can get a picture of the graph g1:

sage: g1.show()



gives:

Now, the cube graph is easy, it is already defined in the Sage library of graphs:

sage: g2=graphs.CubeGraph(3)
sage: g2.is_vertex_transitive()
True



In this case it is nicer to draw the graph in 3d!

sage: g2.show3d()



which should result in something like:

Now for the third graph, we use “LCF notation”. Basically, we note that from vertex 0, we have a cord to the second vertex, then from 1 again to the second vertex. Then the cord from the next vertex (number 2) goes two steps backward, and also the next. This recipe repeats for the next four vertices, hence:

sage: g3=graphs.LCFGraph(8, [2,2,-2,-2], 2)
sage: g3.is_vertex_transitive()
False



For the fourth, we use again the LCF notation:

sage: g4=graphs.LCFGraph(8, [4,-2,4,2], 2)
sage: g4.is_vertex_transitive()
False



For the fifth, we use another strategy. We will add edges to a cycle of length 8:

sage: g5=graphs.CycleGraph(8)
sage: g5.is_vertex_transitive()
False



The last graph is an example of a “circulant graph”: 8 vertices with “steps” of 1 and 4 vertices:

sage: g6=graphs.CirculantGraph(8,[1,4])
sage: g6.is_vertex_transitive()
True



## Simple Beamer animation

The following LaTeX document shows a simple usage of the animate package. I used it once for the final frame of a Beamer presentation.

\documentclass{beamer}

\usepackage{tikz}
\usepackage{animate}

\newcommand{\mancommon}[1]{%
\begin{tikzpicture}[ultra thick,scale=0.25]
\draw (0,0) -- (1,2) -- (2,0); %legs
\draw (1,2) -- (1,4);          %trunk
#1
\end{tikzpicture}}

\newcommand{\mananimated}{\begin{animateinline}[autoplay,loop]{3}
\mancommon{\draw (-1,3.5) -- (1,3) -- (3,3.5);}
\newframe
\mancommon{\draw (-1,3) -- (3,3);}
\newframe
\mancommon{\draw (-1,2.5) -- (1,3) -- (3,2.5);}
\newframe
\mancommon{\draw (-1,3) -- (3,3);}
\end{animateinline}}

\begin{document}
\begin{frame}
\begin{center}
\mananimated\hspace{0.4cm}
\mananimated\hspace{0.4cm}
\mananimated\hspace{0.4cm}
\mananimated
\end{center}
\end{frame}
\end{document}


Posted in LaTeX | Tagged , | 2 Comments

## Is the Franklin graph a Cayley graph?

The Franklin graph is one of the four vertex-transitive cubic graphs on 12 vertices. From its drawing it is easy to see it is actually vertex-transitive, but I wanted to check whether it is a Cayley graph. I would use GAP together with GRAPE for that, but this time I wanted to use Sage, since it can immediately draw a graph, and I imagine that would appeal to my students.

I will use the well-known fact that a graph is a Cayley graph if and only if there is a subgroup of its automorphism group that acts regularly on the set of vertices.

First, I define the Franklin graph in LCF notation, since apparently it is not included in the graphs already defined by Sage:

sage: fr=graphs.LCFGraph(12,[5,-5],6)



I then calculate the automorphism group of the Franklin graph, considering that while the vertices of the graph are indexed from 0 to 11, in the automorphism group they are indexed from 1 to 12. So we checked that 0 is mapped to 12 and the rest are mapped to the same.

sage: aut=fr.automorphism_group(translation=True)
sage: aut[1]
{0: 12, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11}



The automorphism group of the graph is called gaut, and we store in conj a list of representatives of the conjugacy classes of its subgroups. We then check the order of such representatives:

sage: gaut=aut[0]
sage: conj=gaut.conjugacy_classes_subgroups()
sage: [(i,conj[i].order()) for i in range(len(conj))]
[(0, 1), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 3), (7, 4), (8,4), (9, 4), (10, 4),
(11, 4), (12, 4), (13, 4), (14, 4), (15, 4), (16,6), (17, 6), (18, 6), (19, 8), (20, 8),
(21, 8), (22, 8), (23, 8), (24, 8), (25, 8), (26, 12), (27, 12), (28, 16), (29, 24), (30, 24),
(31, 24), (32, 48)]



This says that the subgroups with index 26 and 27 have 12 elements, and so are candidates for subgroups acting regularly. We check an orbit of the 26th:

sage: conj[26].orbit(1)
[1, 3, 7, 5, 9, 11]



Since the orbit does not have 12 elements, this group does not act transitively. We then check the 27th subgroup:

sage: conj[27].orbit(1)
[1, 7, 3, 9, 5, 11, 12, 6, 4, 10, 2, 8]
sage: len(_)
12



So this is the subgroup we were looking for, and this proves that the Franklin graph is actually a Cayley graph!

We now look for generators. For this, we name reg the subgroup we found, and we seek to obtain the elements of reg, sending the 0-th vertex to its neighbors.

sage: reg=conj[27]
sage: fr[0]
[1, 11, 5]



This means the neighbors of 0 are 1,11,5. One should probably write a function to obtain then the elements of reg sending 0 to 1, 0 to 11 and 0 to 5. This is how I do it interactively:

sage: def f(x): return x(12)==1
....:
sage: filter(f,reg.list())
[(1,12)(2,5)(3,4)(6,7)(8,11)(9,10)]
sage: a=_[0]
sage: def f(x): return x(12)==11
....:
sage: filter(f,reg.list())
[(1,10)(2,9)(3,8)(4,7)(5,6)(11,12)]
sage: b=_[0]
sage: def f(x): return x(12)==5
....:
sage: filter(f,reg.list())
[(1,4)(2,3)(5,12)(6,11)(7,10)(8,9)]
sage: c=_[0]



Finally, we construct the Cayley graph in sage, and check it is actually isomorphic to the Franklin graph. Note that we need to convert the Cayley graph to a simple graph, since Cayley graphs are directed in sage by default.

sage: cayl=reg.cayley_graph(generators=(a,b,c)).to_simple()
sage: cayl.is_isomorphic(fr)
True



Done!