December 16, 2014

Auditorium of NUMEC (Núcleo de Apoio à Pesquisa em Modelagem Estocástica e Complexidade)
at the Institute of Mathematics and Statistics of the University of São Paulo – IME-USP

Abstracts of the Talks

• Graph Embeddings and Crossing Number
  Rafael Veiga Pocai
  Instituto de Matemática e Estatística, Universidade de São Paulo

  Abstract: In this talk, we will discuss two optimization problems relating graphs and surfaces: the genus problem and the crossing number problem. These problems ask for “the best”, or “the simplest” way of drawing a graph on a surface. We will present their definitions, some special cases and intractability results.

• Permutations and book embeddings of graphs
  Gelasio Salazar
  Instituto de Física, Universidad Autónoma de San Luis Potosí

  Abstract: Some of the most natural and basic questions in combinatorics can be posed as problems on (decompositions of) permutations. For instance: given a permutation, how can it be efficiently decomposed into (many) subpermutations with certain properties? Or, given several permutations: which are the longest subpermutations (or subpatterns) that they have in common? In this talk we’ll review some of these problems, and explore their relationship to another hard combinatorial problem: how to embed a graph into a book with “few” pages. This is joint work with Jozsef Balogh.

• Pseudolinear crossing number and rectilinear crossing number
  César Hernández-Vélez
  Instituto de Matemática e Estatística, Universidade de São Paulo

  Abstract: A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph G is the minimum number of pairwise crossings of edges in a pseudolinear drawing of G. We establish several facts on the pseudolinear crossing number, including its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph. Joint work with Jesús Leaños and Gelasio Salazar.

• Upperbounds for crossing numbers of the \(n\)-cube
  Luerbio Faria
  Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro

  Abstract: The crossing number \(cr(G)\) of \(G\) is the minimum number of crossings in a drawing of \(G\) in the plane. The rectilinear crossing number \(\overline{cr}(G)\) of \(G\) is the minimum number of crossings in a drawing of \(G\) in the plane with straight line segments at the place of the edges of \(G\). The 2-page crossing number \(cr_2(G)\) of \(G\) is the minimum number of crossings in a drawing of \(G\) into 2 semiplanes where the vertices of \(G\) belong to a straight line bounding the semiplanes. Very little is known about crossing numbers of classes of graphs. The \(n\)-cube graph \(Q_n\) has \(|V(Q_n)| = 2^n\), there is a 1-1 function between \(V(Q_n)\) and the set of binary \(n\)-tuples. An edge \(uv\) is in \(E(Q_n)\) iff the difference, \(diff(u,v)=1\), between \(u\) and \(v\) has exactly one bit. The only known values for crossing numbers of cubes are \(cr(Q_i)=\overline{cr}(Q_i)=cr_2(Q_i)=0, i=0,1,2,3\) and \(cr(Q_4)=\overline{cr}(Q_4)=cr_2(Q_4)=8\). It is known that \(cr(Q_n)=\overline{cr}(Q_n)=cr_2(Q_n)=\Theta(4^n)\). And the remaining are upperbounds. In this talk we present some results about upperbounds for some crossing numbers of the \(n\)-cube graph.

Acknowledgements

We gratefully acknowledge the support of MaCLinC and NUMEC for hosting this event.