---

Graph Theory & Combinatorics
Org: I. Gitler (CINVESTAV), L. Goddyn (SFU) and B. Reed (McGill)
[PDF]

---

MATT DEVOS, Simon Fraser University
A generalization of Kneser's addition theorem [PDF]

Two important topics in the study of additive abelian groups are sumsets and subsequence sums. In joint work with B. Mohar and L. Goddyn, we have studied a unification of these two problems.

Let A₁,A₂,...,A_n be a sequence of finite subsets of an (additive abelian) group. Define a group element g to be a k-sum if g can be expressed as a sum of group elements from k distinct terms of this sequence. Our main problem of interest will be finding a (natural) lower bound on the number of (distinct) k-sums.

The study of sumsets is the special case when n = k = 2 and here M. Kneser proved an important lower bound. The study of subsequence sums is the special case when every set A_i has size one. Here there have been a number of interesting lower bounds, due to Hamidoune, Bollobas-Leader, Grynkiewicz, and others. We prove a general lower bound on the number of distinct k-sums which generalizes all of these results.

HORTENSIA GALEANA, Universidad Nacional Autónoma de México
Hypergraph transversals and kernels in digraphs [PDF]

In this work we relate the existence of certain transversals of square hypergraphs with the existence of kernels in digraphs. This method allows us to propose and to prove several results on the existence of kernels in digraphs. In particular we have the following: In 1980, H. Meyniel conjectured that if D is a digraph such that every odd directed cycle has at least two pseudodiagonals, then D has a kernel. Although this conjecture was disproved by Galeana-Sánchez (1982), the following modificationn of Meyniel's Conjecture still holds: If D is a digraph such that every W-odd cycle has at least two W-pseudodiagonals, then D has a kernel. Some open problems are proposed.

ISIDORO GITLER, Department of Mathematics, Cinvestav
On a new class of Mengerian hypergraphs [PDF]

We study the normality of the Rees algebra associated to a clutter and the relations with the conjecture of Conforti and Cornuéjols about the packing properties on clutters. This conjecture states that all the clutters with the packing property have the MFMC property. We show that this conjecture is equivalent to an algebraic statement about the normality of the Rees algebra. Finally we introduce a new infinite class of hypergraphs that verify the conjecture of Conforti and Cornuéjols.

Definition 1 The clutter C satisfies the max-flow min-cut (MFMC) property (or is called Mengerian) if both sides of the LP-duality equation

min {áa,x ñ | x ³ 0; xA ³ 1} = max {áy,1 ñ | y ³ 0; Ay £ a}

(1)

have integral optimum solutions x and y for each non-negative integral vector a.

We denote the smallest number of vertices in any minimal vertex cover of C by a₀ (C) and the maximum number of independent edges of C by b₁ (C).

Definition 2 If a₀ (C) = b₁ (C) we say that the clutter C has the König property.

Definition 3 A clutter C satisfies the packing property (PP) if all its minors satisfy the König property.

Proposition 1 If C has the max-flow min-cut property, then C has the packing property.

Conjecture 1 [Conforti-Cornuéjols]If the clutter C has the packing property, then C has the max-flow min-cut property.

This conjecture continues to be open. The only cases known are for binary matroids (Seymour), and dyadic hypergrphs (Cornuejols, Guenin and Margot).

In this talk we give a new infinite family Q_pq^F of hypergrahs that verify the conjecture of Conforti and Cornuéjols. This new class is neither binary nor dyadic.

LUIS GODDYN, Simon Fraser University
Spanning Trees of Many Different Weights [PDF]

We weight the edges of a graph X with elements of an abelian group G. The weight w(T) of a spanning tree T is the sum of the weights of its edges. In 1990, Seymour and Schrijver conjectured the lower bound

# {w(T): T is a spanning tree of X} ³ |H| æ è 1 - rk(X) + å rk(EQ) ö ø .

Here H is the stabilizer of the set on the left. The sum runs over the H-cosets Q in G. Also rk is the (matroidal) rank function, and E_Q is the set of edges of X whose weight lies in Q.

In fact, they propose an analagous conjecture for any weighted matroid, and they prove it in the case G has prime order. Here we prove the Seymour-Schrijver Conjecture in case G has order pq, where p and q are prime, and also in case G is the cyclic group of order p^k.

This is joint work with Matt Devos and Bojan Mohar.

PENNY HAXELL, University of Waterloo, Waterloo, Ontario, Canada
Hypergraph intersections [PDF]

We give some sufficient conditions for a pair of hypergraphs to intersect. We also discuss some applications.

VESELIN JUNGIC, Simon Fraser University, 8888 University Drive, Burnaby, Brtish Columbia, Canada
Rainbow Ramsey Theory [PDF]

The rainbow Ramsey theory could be defined as a collection of results which, given a finite coloring of some structure, guarantee the existence of certain rainbow configurations or substructores.

Radoici\'c conjectured in 2001 that every equinumerous 3-coloring of {1,2...,3n} contains a 3-term rainbow arithmetic progression, i.e., an arithmetic progression whose terms are colored with distinct colors. This conjecture initiated a series of results having rainbow structures as the common theme.

In this presentation an overview of the current state in the rainbow Ramsey theory will be given. I will list and describe some of the recent published and unpublished results obtained by Axenovich, Conlon, Fox, Jungi\'c, Mahdian, Martin, Radoici\'c, and Serra.

A few conjectures and open problems will be mentioned.

PETR LISONEK, Simon Fraser University, Burnaby, BC, Canada
Rainbow Graphs in Steganography [PDF]

A k-regular graph is called a "rainbow graph" if it admits a proper vertex colouring with k+1 colours such that, for each vertex v, all neighbors of v receive distinct colors. We survey some constructions of rainbow graphs; in particular we note that the d-dimensional integer lattice graph Z^d is rainbow for each d. We discuss an application of this result in steganography.

LUIS MONTEJANO, UNAM
Colorable Transversal Theory [PDF]

We shall discuss several colorable line and k-plane transversal theorems under the spirit of Barani and Lovasz.

MIGUEL ANGEL PIZAÑA, Universidad Autónoma Metropolitana, San Rafael Atlixco 186, Del. Iztapalapa, 09340, Mexico City, México
Graph Relations and Clique Divergence [PDF]

Given a graph G, its clique graph K(G) is the intersection graph of all its (maximal) cliques. Iterated clique graphs are defined by K⁰(G)=G and Kⁿ⁺¹(G) = K ( Kⁿ(G) ). A graph G is said to be clique divergent if the sequence of orders |G|, |K(G)|, |K²(G)|, ..., |Kⁿ(G)|, ... diverges. A graph relation f : G® H is a relation of sets f Í V(G)×V(H) such that f(X) induces a complete subgraph of H whenever X induces a complete subgraph of G. Here, we introduce a technique for proving clique divergence of graphs using graph relations. As a consequence we prove that every surface admits a (Whitney) triangulation whose underlying graph is clique divergent.

BRUCE REED, McGill University, Montreal; CNRS, Sophia-Antipolis
Erdös-Posa Property for Cycles of Prescribed Length [PDF]

Neumann-Lara proved that the Erdös-Posa property holds for even cycles, i.e., he showed that for all k there is an f(k) such that every graph either has k vertex disjoint odd cycles or contains a set X of at most f(k) vertices intersecting every odd cycle. Here we discuss the Erdös-Posa property for various families of cycles, including odd cycles, cycles length zero mod m for arbitrary m, long cycles, and cycles which are non-zero mod m for odd m.

L. BRUCE RICHMOND, University of Waterloo, Waterloo, ON
Baby-Steps Giant-Steps in Polynomial Factorization [PDF]

The average cost of baby-step/giant-step polynomial factoring algorithms is considered. The distribution of the degrees of the irreducible factors of a random polynomial of degree n is relevant. Consider a partition of [1,2,...,n] into intervals. Intervals that contain more than one irreducible factor degree are called multi-factor intervals. The fastest algorithms so far separate the product of all the irreducible factors of the polynomial with degrees belonging to a given interval from the other factors. If the interval is not multi-factor there is no need of further computation for this interval. If the interval is multifactor the product of the irreducible polynomials with degrees in the interval is computed. One expects to have more factors of lower degrees than higher degrees. One considers therefore partitions with growing interval sizes. The best partitions are what we look for. This was done for polynomials over F₂ by von zur Gauthen and Gerhard. The approach we follow uses generating functions and the asymptotics of their coefficients.

EDUARDO RIVERA CAMPO, Universidad Autónoma Metropolitana-Iztapalapa
Partitions of complete geometric graphs into plane trees [PDF]

We give a sufficient condition for a complete geometric graph with 2n vertices to have a partition into n plane spanning trees. For the case where the vertices are in convex position, we characterise all such partitions.

This is joint work with P. Bose, F. Hurtado and D. R. Wood.

GELASIO SALAZAR, Instituto de Física, Universidad Autónoma de San Luis Potosí, San Luis Potosí, SLP, México 78000
On pseudolinear crossing numbers [PDF]

We will talk about the pseudolinear crossing number of a graph, a parameter which lies between the usual and the rectilinear crossing number. The pseudolinear crossing number is a natural generalization of the rectilinear crossing number, and has the advantage that its computation is a purely combinatorial problem. We will present some recent results regarding the pseudolinear crossing number of the complete graphs.

CARLOS VALENCIA, CINVESTAV, Departamento de Matemáticas, Apartado Postal 14-740, 07000 México City, DF; UNAM, Instituto de Matemáticas, Circuito Exterior, Ciudad Universitaria, México City, DF, 04510
Connected graphs with a minimal number of edges [PDF]

In this talk we will give a lower bound for the number of edges of a connected graph as a function of the stability number a and the covering number t. More precisely we will show that

q(G) ³ a(G) - c(G) + G æ è a(G), t(G) ö ø ,

where c(G) is the number of connected components of G and

G(a,t) = min ì í î a å i=1  \binomzi2 ê ê z1 + ¼+ za = a + t and zi ³ 0  " i = 1,...,a ü ý þ ,

for a and t two arbitrary natural numbers.

This result is a variant for connected graphs from a Turán's theorem for the minimal number of edges of a graph with fixed stability number and order. We will also discuss the generalization of this result for k-connected graphs with k ³ 2.

JACQUES VERSTRAETE, University of Waterloo and McGill University
Cycles in sparse graphs [PDF]

The central theme of this talk is to study the largest possible average degree d(n,S) of an n-vertex graph with no cycle of length from a given set of positive integers S.

When S contains only odd numbers, the extremal graphs are complete bipartite graphs, so d(2n,S) = n in this case. When S contains even numbers, the problem becomes notoriously difficult. The case S = {2k} is Erdös' Even Cycle Theorem. In this talk I will give a short proof of this theorem, which states d(n,S) is at most about n^1/k. The method used to prove this allows us to consider any set S of forbidden even cycle lengths: a general theorem will be presented which shows that apart from chaotic looking sets S, d(n,S) is at most about exp(log*n). This is motivated by a conjecture of Erdös that d(n,S) is a constant when S is the set of powers of two. Very surprisingly, our result is tight: there exist sets S for which d(n,S) is roughly exp(log*n).

RAFAEL VILLARREAL, CINVESTAV-IPN, Departamento de Matemáticas, Apartado Postal 14-740, 07000 México DF
Ring graphs and complete intersection toric ideals [PDF]

We study the family of simple graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is "constructible" and that it is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of simple and oriented graphs.

KERRI WEBB, University of Lethbridge, 4401 University Drive, Lethbridge, Alberta
Balanced Graphs [PDF]

A bipartite graph in which every induced circuit has length divisible by four is said to be balanced. Balanced graphs were introduced by Berge, and have an important role in linear programming. We discuss structural results for vertex transitive balanced graphs.

FRANCISCO JAVIER ZARAGOZA MARTÍNEZ, Universidad Autónoma Metropolitana Azcapotzalco, Departamento de Sistemas, Mexico City
Irreducible triangulations of surfaces [PDF]

Let S be a closed surface with Euler genus g(S). An irreducible triangulation of S is a simple graph G without contractible edges embedded on S so that each face is a triangle and any two faces share at most two vertices. Nakamoto and Ota proved that the number n of vertices of an irreducible triangulation of S is bounded above by 171 g(S) - 72. This bound was improved by Cheng, Dey, and Poon to n £ 120 g(S) for orientable surfaces. We improve these bounds to n £ 106.5 g(S) - 33 for any closed surface S.

This is joint work with Gloria Aguilar Cruz at the Department of Mathematics of CINVESTAV.