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.

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.

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

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.

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

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.

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

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.

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.

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

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.

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.

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.

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.

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.

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

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.

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

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.

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.