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(q²-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.

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 C_k a directed cycle of length k, we denote I_g (C_k) = |A(g) ÇA(C_k) |. We determine f(n,k,D) = max{I_g(C_k) | C_k Í D}, in case that D is a tournament a bipartite tournament or a multipartite tournament.

This is joint work with S. Rajsbaum.

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 = (x_i,x_j) of D, we associate the vector v_e defined as follows: the i-th entry is -1, the j-th entry is 1, and the remaining entries are zero. The incidence matrix A_D of D is the n×q matrix with entries in {0,±1} whose columns are the vectors of the form v_e, with e an edge of D. For simplicity of notation we set A = A_D. The set of column vectors of A will be denoted by A = {v₁,...,v_q}.

Consider the edge subring k[D] : = k[x^v₁,...,x^v_q] Ì k[x₁^±1,...,x_n^±1] of the oriented graph D. There is an epimorphism of k-algebras

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].

References

[1]

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

[2]

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

[3]

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

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.

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.

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.

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.

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 K⁰(G) = G and Kⁿ⁺¹(G) = K ( Kⁿ(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 Kⁿ(G) is the trivial graph K₁. More generally, G is K-convergent if K^m(G) @ Kⁿ(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 Kⁿ(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.

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.

Given a hypergraph H = (E_x,...,E_m), its level-hypergraph L_H 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, L_H is simple; H has repeated edges if, and only if, L_H does too; n(H) = n(L_H), 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 L_H. Moreover, H is balanced (respectively totally balanced) if, and only if, L_H is balanced (respectively totally balanced); H is unimodular (respectively strongly unimodular) if, and only if, L_H is unimodular (respectively strongly unimodular), and L(H) = L(L_H), l(H) = l(L_H).

References

[1]

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

[2]

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

[3]

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

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.

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.

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 (C₄ with a chord), then

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.

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.

We shall sketch the proof of the following theorem:

Theorem 1 If G₁ and G₂ are both locally H and |H| £ 6, then G₁ and G₂ 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 K⁰(G) = G and Kⁿ(G) = K ( K^n-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.

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.