University of British Columbia, Vancouver, August 13-15, 2009

Combinatorics and Graph Theory
Org: Hortensia Galeana (IMATE-UNAM), Luis Goddyn (SFU) and Miguel Pizaña (UAM-I)

GABRIELA ARAUJO, Universidad Nacional Autónoma de México
Geometric constructions of small regular bipartite graphs of girth 6

In this talk we exhibit some structures in the projective plane of order q which allow us to find q-regular balanced bipartite graphs of girth 6 and 2(q2-1) vertices and k-regular balanced bipartite digraph with 2( qk-2) vertices for all k £ q-1, where k is an integer and q is a prime power with 3 £ k £ q-1. These graphs have the smallest number of vertices known so far among the regular graphs with girth 6 and improve the recent results on this topic.

Joint work with Camino Balbuena, Universidad Politécnica de Cataluña, España.

HORTENSIA GALEANA, Universidad Nacional Autónoma de México, Instituto de Matemáticas, Area de la Investigación Científica 04510, México, D.F.
Cycle pancyclism in digraphs

The subject of pancyclism in digraphs has been studied by several authors meanly in tournaments and nearly tournaments. A digraph is vertex-pancyclism if given a vertex v there are cycles of every length containing v. Similarly, a digraph is arc-pancyclic if given any arc e there are cycles of every length containing e.

In this talk we deal with the concept of cycle-pancyclism to study questions as the following. Given a cycle C, what is the maximum number of arcs which a cycle of length k contained in D has in common with C?

Assuming that g is a hamiltonian cycle of the digraph D; and Ck a directed cycle of length k, we denote Ig (Ck) = |A(g) ÇA(Ck) |. We determine f(n,k,D) = max{Ig(Ck) | Ck Í D}, in case that D is a tournament a bipartite tournament or a multipartite tournament.

This is joint work with S. Rajsbaum.

Toric Ideals Complete Intersection of Oriented Graphs and Generalized-Theta Graphs

Let G be a connected graph with n vertices and q edges and let O be an orientation of the edges of G, i.e., an assignment of a direction to each edge of G. Thus D = (G,O) is an oriented graph. To each oriented edge e = (xi,xj) of D, we associate the vector ve defined as follows: the i-th entry is -1, the j-th entry is 1, and the remaining entries are zero. The incidence matrix AD of D is the n×q matrix with entries in {0,±1} whose columns are the vectors of the form ve, with e an edge of D. For simplicity of notation we set A = AD. The set of column vectors of A will be denoted by A = {v1,...,vq}.

Consider the edge subring k[D] : = k[xv1,...,xvq] Ì k[x1±1,...,xn±1] of the oriented graph D. There is an epimorphism of k-algebras

j: B = k[t1,...,tq] ® k[D],     ti ® xvi,
where B is a polynomial ring. The kernel of j, denoted by PD, is called the toric ideal of D. This ideal was studied in [2], [3]. Notice that PD is no longer a graded ideal, see Proposition ??. The toric ideal PD is a prime ideal of height q-n+1 generated by binomials and k[D] is a normal domain. Thus any minimal generating set of PD must have at least q-n+1 elements, by the principal ideal theorem. If PD can be generated by q-n+1 polynomials it is called a complete intersection. In [3] is shown that any graph has an acyclic orientation such that the corresponding toric ideal is a complete intersection. And a graph G is called complete intersection for all orientation (C.I.O.) if PD is a complete intersection, for all D orientation of G.

We introduce the generalized-theta graph. The theta graphs studied in [1] are generalized-theta graphs. Our main result is: G is C.I.O. if and only if all generalized thetas of G have a special triangle. We obtain a characterization of the ring graphs in term of the generalized theta graph. With this result we recover the characterization of the C.I.O. bipartite graphs given in [3].


M. Chudnovsy and S. Safra, Detecting a theta or a prism. SIAM J. Discrete Math. 22(2008), 1164-1186.

I. Gitler, E. Reyes and R. H. Villarreal, Ring graphs and toric ideals. Electron. Notes Discrete Math. 28C(2007), 393-400.

     , Ring graphs and complete intersection toric ideals. Discrete Math., to appear.

CHRIS GODSIL, University of Waterloo, Waterloo, ON, N2L 3G1
Graph spectra and quantum computing

As a graduate student, I was fascinated to learn that the eigenvalues of a graph could actually provide useful information about its structure. I started work on this topic, and never outgrew my interest in it-it seemed a harmless enough amusement. But recently I have been surprised to find that a number of questions arising in quantum computing could be profitably attacked using results and techniques from the theory of graph spectra. In my talk I will present some of these problems (in graph theoretic terms), and discuss what progress has been made.

BERTRAND GUENIN, University of Waterloo, 200 University Avenue West, Ontario, Canada N2L 3G1
Flows in binary matroids

The max-flow min-cut theorem in graphs does not extend to binary matroids in general. However, Seymour conjectured that this minimax relation holds as long as the binary matroids do not contain any one of three special obstructions. We discuss progress on this conjecture.

PAVOL HELL, Simon Fraser University, Burnaby, BC, V5A 1S6
Variants of interval digraphs

I will discuss various directed analogues of interval graphs and proper interval graphs, their forbidden structure characterizations, and polynomial recogniziton algorithms. These concepts are motivated by the relation with graph polymorphisms, which play a role in solving constraint satisfaction problems.

This is joint work with Arash Rafiey, Jing Huang, and Tomas Feder.

ANDREW KING, McGill University, Montreal; Institute for Theoretical Computer Science, Prague
Fractional and integer colourings in claw-free graphs

Chudnovsky and Seymour recently characterized the structure of claw-free graphs, generalizing previous work by Maffray and Reed on Berge claw-free graphs. When the stability number is at least four, a claw-free graph is a particular generalization of a line graph.

In this work, we combine this structure with known results on fractional and integer colourings of line graphs. We previously used this approach to extend a conjecture of Reed (c £ é[ 1/2] (D+1+w) ù for all graphs) from line graphs to claw-free graphs. More recently, we have proved that the fractional and integer chromatic numbers agree asymptotically for claw-free graphs with stability number at least four. This extends a probabilistic result of Kahn on line graphs, using the structural decomposition provided by Chudnovsky and Seymour.

Our proofs lead to polynomial-time algorithms for finding near-optimal colourings of claw-free graphs.

This is joint work with Bruce Reed.

PACO LARRIÓN, UNAM, Ciudad Universitaria, México, D.F. Mexico
The fundamental group of the clique graph

The cliques of a graph G are its maximal complete subraphs or, rather, their vertex sets. The clique graph of G is the intersection graph K(G) of its cliques, so the vertices of K(G) are the cliques of G, and two of them are neighbours in K(G) if they are distinct and share at least one vertex. The iterated clique graphs of G are recursively defined by K0(G) = G and Kn+1(G) = K ( Kn(G) ).

We are interested in the dynamical behaviour of a graph G under the clique graph operator K. For instance, G is K-null if some iterated clique graph Kn(G) is the trivial graph K1. More generally, G is K-convergent if Km(G) @ Kn(G) for some pair m < n. It is easy to see that G is not K-convergent precisely when it is K-divergent, in the sense that the order of Kn(G) tends to infinity with n.

The complete subgraphs of G, viewed as vertex sets, form a simplicial complex. Via the geometric realization of this complex, we can consider the graph G as a topological space. Erich Prisner proved in 1992 that the first modulo two homology group of K(G) is the same as that of G, and we proved recently the stronger statement that the fundamental group of K(G) coincides with that of G. This gives a necessary condition for a graph to be K-null.

The talk is about joint work with M. A. Pizaña and R. Villarroel-Flores.

PETR LISONEK, Simon Fraser University, Burnaby, BC, Canada
Latin bitrades and Eulerian triangulations

Informally, a Latin bitrade is a pair of partial Latin squares obtained by superimposing two Latin squares (of the same order and with the same symbol set) and removing from both squares those cells that contain the same symbol in corresponding positions.

Latin bitrades which satisfy some natural conditions (that can be easily achieved) correspond to vertex 3-colourable Eulerian triangulations of orientable surfaces. This leads to a natural definition of the genus of a Latin bitrade. It was recently shown that all spherical Latin bitrades can be embedded in a finite Abelian group while there exist toroidal Latin bitrades that can be embedded in no group.

We show that spherical Latin bitrades correspond to spherical Eulerian triangulations (that is, the vertex 3-colourability is implied in this case). We prove that the algorithm for inductive generation of spherical Eulerian triangulations (due to Batagelj, Brinkmann and McKay) can be simplified by removing one of the two local transformations that it uses. We discuss an analogous algorithm for generation of toroidal Latin bitrades.

This is joint work with N. Cavenagh and A. Drapal.

MARTÍN MANRIQUE, Universidad Nacional Autónoma de México, Ciudad Universitaria, D.F., México
Level Hypergraphs

Given a hypergraph H = (Ex,...,Em), its level-hypergraph LH is the result of identifying all vertices which belong to exactly the same edges. This new hypergraph has the same edge-structure as the original one, but may have less vertices. The tool makes it possible to emulate known theorems given in terms of order or rank; the new results are stated in terms of edge-structure, and usually apply to different classes of hypergraphs than the original statements, though there are some improvements on known results.

On the other hand, the study of several characteristics of a given hypergraph H is simplified, since many hypergraph invariants are preserved. For example: H is simple if, and only if, LH is simple; H has repeated edges if, and only if, LH does too; n(H) = n(LH), where n(H) is the maximum cardinality of a matching in H; the minimum cardinality of a transversal set, the maximum cardinality of a transversal set not contained properly in other transversal, and the minimum cardinality of a strongly stable set are also equal in both H and LH. Moreover, H is balanced (respectively totally balanced) if, and only if, LH is balanced (respectively totally balanced); H is unimodular (respectively strongly unimodular) if, and only if, LH is unimodular (respectively strongly unimodular), and L(H) = L(LH), l(H) = l(LH).


B. D. Acharya, unpublished Manuscript, MRI, 1979.

C. Berge, The Theory of Graphs. Dover Publications, New York, 2001.

     , Hypergraphs. Combinatorics of Finite Sets. Elsevier Science Publishers, Amsterdam, 1989.

SEAN McGUINNESS, Thompson Rivers University, Kamloops, BC
A Base Exchange Property for Regular Matroids

In 1980, White conjectured that for any two bases B and B¢ of a regular matroid, there is an element e Î B such that there is a unique element f Î B¢ for which both (B\{e}) È{f} and (B¢\{f}) È{e} are bases of M. In this talk, we outline a proof of this conjecture.

BOJAN MOHAR, Simon Fraser University
Chromatic number and complete graph substructures for degree sequences

Given a graphic degree sequence D, let c(D) (respectively w(D), h(D), and H(D)) denote the maximum value of the chromatic number (respectively, the size of the largest clique, largest clique subdivision, and largest clique minor) taken over all graphs whose degree sequence is D. It is proved that c(D) £ h(D). Moreover, it is shown that a subdivision of a clique of order c(D) exists where each edge is subdivided at most once and the set of all subdivided edges forms a collection of disjoint stars. This bound is an analogue of the Hajós Conjecture for degree sequences and, in particular, settles a conjecture of Neil Robertson that degree sequences satisfy the bound c(D) £ H(D) (which is related to the Hadwiger Conjecture). It is also proved that c(D) £ [ 6/5] w(D) + [ 3/5] and that c(D) £ [ 4/5] w(D) + [ 1/5]D(D) + 1, where D(D) denotes the maximum degree in D. The latter inequality is a strengthened version of a conjecture of Bruce Reed. All derived inequalities are best possible.

This is a joint work with Zdenek Dvorak.

JUAN JOSÉ MONTELLANO, Universidad Nacional Autonoma de Mexico, Instituto de Matematicas, U.N.A.M., Area de la investigacion cientifica, Circuito Exterior, Ciudad Universitaria Coyoacan, 04510 Mexico D.F., Mexico
Some Turan and anti-Ramsey numbers

Let G be a graph obtained by adding a chord to a cycle, and let C(G) be the set of cycles which are subgraphs of G. Here we study the relation between ex( n,C(G) ) and f(n,G), where ex( n,C(G) ) is the maximum number of edges of a graph on n vertices with no subgraph isomorphic to an element of C(G); and f(n,G) is the minimum integer k such that for every edge-coloring of the complete graph of order n which uses exactly k colors, there is at least one copy of G all whose edges have different colors.

In particular we show that if G is the diamond (C4 with a chord), then

ex(n, {C3,C4}) + 2 £ f(n,G) £ ex(n, {C3,C4}) + (n+1).

JOY MORRIS, University of Lethbridge, Lethbridge, AB, T1K 3M4
Structure of strongly regular vertex- and edge-transitive graphs

I will discuss the use of normal quotient reduction to analyse families of vertex-transitive, edge-transitive graphs. This method has been used extensively by Cheryl Praeger and others. In this talk, we apply the method to strongly regular graphs that are vertex- and edge-transitive.

In this talk, I will present some analysis of graphs in this family whose normal quotient is a complete graph, and the result that irreducible graphs in this family have quasiprimitive groups of automorphisms. Our main result is that no graph in this family can have a holomorphic simple group of automorphisms.

This is joint work with Cheryl Praeger and Pablo Spiga.

MIKE NEWMAN, University of Ottawa
Matroid Asymptotics

We consider the properties of a random matroid: what does it look like? It turns out that very little is known, in stark contrast to random graphs, or even random matroids over a fixed finite field.

We show that asymptotically at least half of all matroids are connected, and outline some ideas that might be able to prove the "truth", that is that a.a.s. all matroids are connected, or even highly connected. We make several conjectures on properties that should hold a.a.s. for all matroids. We also describe a possible approach to generating a random matroid that is work in progress.

This is joint work with Dillon Mayhew, Dominic Welsh and Geoff Whittle.

MIGUEL PIZAÑA, Universidad Autonoma Metropolitana-Iztapalapa, Av. San Rafael Atlixco 186, Mexico City, 09340, Mexico
On the clique behavior of locally small graphs

We shall sketch the proof of the following theorem:

Theorem 1 If G1 and G2 are both locally H and |H| £ 6, then G1 and G2 have the same clique behavior.

We say that a graph G is locally H if the neighbors of every vertex induce a subgraph isomorphic to H. Hall classified in 1985 the graphs H with at most 6 vertices, such that there exist at least one finite graph G which is locally H. The clique graph K(G) of G is the intersection graph of all the (maximal) cliques of G. Iterated clique graphs are then defined recursively by K0(G) = G and Kn(G) = K ( Kn-1(G) ). When the sequence of orders of the iterated clique graphs of G is unbounded, we say that G is clique divergent, otherwise it is clique convergent. We say that two graphs have the same clique behavior when both graphs are clique divergent or both graphs are clique convergent.

Joint work with Paco Larrión and Rafael Villarroel-Flores.

EDUARDO RIVERA, Universidad Autónoma Metropolitana, Iztapalapa, Av. San Rafael Atlixco 186, México D.F. 09340, México
Variations on the heterochromatic number

Let H be a hypergraph and c be a colouring of the vertex set V(H) of H. An edge e of H is a heterochromatic edge if c assigns different colours to different vertices of e. The heterochromatic number of H is the smallest integer k such that every colouring of V(H) with k or more colours produces at least one heterochromatic edge. In this talk we give bounds for the heterochromatic number of certain hypergraphs associated to abstract graphs and to geometric graphs.

This is joint work with Juan José Montellano-Ballesteros.

RICARDO STRAUSZ, Instituto de Matematicas, Universidad Nacional Autonoma de Mexico
On the pseudoachromatic index of the complete graph

Let n = q2+q+1, where q=2p. It will be shown that the pseudoachromatic index of the complete graph of order n+q+1 equals q3+2q2+3q. Besides this result, it will be discussed the state-of-the-art on the problem of calculating such a parameter for all complete graphs.

Event Sponsors

Canadian Mathematical Society      Sociedad Matemática Mexicana      Pacific Institute for the Mathematical Sciences      Centre de recherches mathématiques Fields Institute MITACS

© Canadian Mathematical Society :