# Seminar 2009-2010

Sessions and Abstracts

## Sessions

Semiregular cages with odd girth are edge-superconnected
Julián Salas, UPC

Ascending subgraph decompositions of bipartite graphs
Jordi Moragas, UPC

Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the tree-depth of random graphs
Guillem Perarnau, UPC

Routing in Social Networks
Dieter Mitsche, CRM

Thursday June 3, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Almost Distance-Regular Graphs
Cristina Dalfó, UPC

Local spectrum of the subconstituents
and completely pseudo-regular codes

Marc Càmara, UPC

Thursday May 27, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Tree Automata and the HOM problem
Omer Giménez, UPC

Linear systems over composite moduli

Thursday May 20, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Asymptotic study of subcritical graph classes
Juanjo Rué, Laboratoire d'Informatique,
Ecole Polytechnique, Palaiseau, France

Graph Operations and Laplacian Eigenpolytopes

Thursday May 13, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Vosperian and superconnected vertex transitive graphs
Susana López-Masip, UPC

Empty monochromatic triangles
Clemens Huemer, UPC

Thursday May 6, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Determining the maximal subset of a finite vector space
in which every subset of basis size is a basis

Simeon Ball
UPC

Thursday April 29, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the Number of Local Configurations on Sturmian words
and Discrete Planes

Laurent Vuillon
LAMA, Université de Savoie, CNRS

Thursday April 22, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Cyclic Flats, Sticky Matroids, and Intertwines
Joseph E. Bonin
Department of Mathematics, The George Washington University

Thursday April 15, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the diameter of random planar graphs
Marc Noy
UPC

Thursday March 25, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Most groups are hyperbolic... or most groups are trivial?
Enric Ventura
UPC

Thursday March 18, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Even and quasi-even triangulations of point sets in the plane
Alberto Márquez

Thursday March 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Recent progress on the Merino-Welsh Conjecture
concerning the Tutte polynomial

Steve Noble
Department of Mathematical Sciences, Brunel University

Thursday February 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Pointing, enumeration, and random generation
in unlabelled combinatorial classes

Éric Fusy
Ecole Polytechnique, Paris

Thursday February 4, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
The Colorful Helly Property for Hypergraphs
Jayme L Swarcfiter
Federal University of Rio de Janeiro

Thursday January 28, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Extensions of the Scherck-Kemperman Theorem
Yahya O. Hamidoune
Univ. Paris 6

Wednesday January 20, 2010, 15h
Aula 101 FME
Campus Sud UPC
Shannon capacity and the perfectness of graphs
Ron Holzman
Technion - Israel Institute of Technology

Thursday December 17, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Classification of Construction Techniques of Large Directed Graphs
Slamin
Universitas Jember, Indonesia

Thursday December 10, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Random graphs with few disjoint cycles
Colin McDiarmid
Oxford University

Thursday December 3, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Large sets in Finite Fields are sumsets
Noga Alon
Tel Aviv University

Thursday November 26, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
###### Workshop on Mathematical Aspects of Large Networks (WLAN)

November 18-20, 2009
CRM
Bellaterra
Small vertex-transitive and Cayley graphs of girth 6 and 5
Jozef Siran
Slovak University of Technology in Bratislava and The Open University

Thursday November 12, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Optimal Graphs and Digraphs
Mirka Miller
The University of Newcastle, Australia
University of West Bohemia, Czech Republic
King's College, London, UK

Thursday November 5, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Optimization in Graphs under Degree Constraints.
Application to Telecommunication Networks

Ignasi Sau
INRIA, Nice and UPC, Barcelona

Thursday October 29, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Closed formulae from almost closed formulae
in 3-generated numerical semigroups

Francesc Aguiló
UPC, Barcelona

Thursday October 22, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
A new addition theorem in Z/pZ via the polynomial method
Éric Balandraud
Univ. Paris 6

Thursday October 22, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Enumeration of indecomposable permutations and of topological maps
on orientable surfaces

Robert Cori
Univ. Bordeaux I and Ecole Polytechnique, Paris
Tuesday September 22, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC

## Abstracts

Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Semiregular cages with odd girth are edge-superconnected
Julián Salas, UPC

Abstract

A graph is said to be edge-superconnected if each minimum edge-cut  consists of all the edges incident with some vertex of minimum degree. A graph G is said to  be a (fd; d + 1; g)-semiregular graph if all its vertices have degree either d or d + 1. A  smallest (fd; d + 1; g)- semiregular graph G with girth g is said to be a (fd; d + 1g; g)-cage.

We show that every (fd; d + 1g; g)-cage with odd girth g is edge-superconnected.

Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Ascending subgraph decompositions of bipartite graphs
Jordi Moragas, UPC

Abstract

Let $G$ be a graph of size ${n+1\choose 2}$ for some integer $n\ge 1$. $G$ is said to have an ascending subgraph decomposition (ASD) if can be decomposed into $n$ subgraphs $H_1,\ldots,H_n$ such that $H_i$ has $i$ edges and is isomorphic to a subgraph of $H_{i+1}$, $i=1,\ldots ,n-1$. In this work we deal with ascending subgraph decompositions of bipartite graphs.
In order to do so, we consider ascending subgraph decompositions in which each factor is a forest of stars. We show that every bipartite graph $G$ with ${n+1\choose 2}$ edges such that the degree sequence $d_1\ge\cdots\ge d_k$ of one of the partite sets satisfies $d_1\ge (k-1)(n-k+1)$, and $d_i\ge n-i+2$ for $2\le i<k$, admits an ASD with star forests. We also give a necessary condition on the degree sequence of $G$ to have an ascending subgraph decomposition into star forests that is not far from the above sufficient one. Our results are based on the existence of certain matrices that we call \emph{ascending} and the construction of edge-colorings of some bipartite graphs with parallel edges.

This is joint work with A. Lladó and Slamin.

Thursday June 3, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### On the tree-depth of random graphs
Guillem Perarnau, UPC

Abstract

The  tree-depth of a graph $G$ is a parameter that plays a crucial role in the theory of bounded expansion classes and has been introduced under numerous names. We describe the asymptotic behaviour of this parameter  in the case of dense and of sparse random graphs. The results also provide analogous descriptions for the treewidth of random graphs.

Thursday June 3, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Routing in Social Networks
Dieter Mitsche, CRM

Abstract

Given n+2 vertices with geometric positions on the positive orthant of the sphere, one of them being a source (S), one of them a sink (D), and n vertices that serve as possible hops (we assume n tending to infinity, and asymptotics are with respect to n). We assume that S and D are orthogonal, whereas all other vertices are placed randomly. S wants to send a message M to D, using at most a constant number of hops, and using a constant number of copies of M (always keeping at least one copy). The probability that a vertex v (having 2 or more copies of M) can send M to another vertex w is proportional to the angle between v and w,  i.e., the smaller the angle between v and w, the more likely v sends to w.  More precisely, the probability depends on the intensity of the Poisson point process \lambda_{v,w} between v and w, where \lambda_{v,w}=k*cos(\angle(v,w)) + \delta  (k is some constant > 0, and \delta=\delta(n) accounts for the fact that even two orthogonal points have non-zero intensity. In particular we are interested in the case \delta=o(1) and also \delta=\omega(\log n/n)). We show that a "First Meeting"-routing algorithm (choosing always the first vertex met as recipient of the copy) needs \Omega(\log(1/\delta)) steps, whereas an "Interest-Based" algorithm (choosing the vertex met only if it is "close" to D) needs at most constant time.

Joint work with J. Diaz, A. Marchetti-Spaccamela and P. Santi.

Thursday May 27, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Almost Distance-Regular Graphs
Cristina Dalfó, UPC

Abstract

Distance-regular graphs have been a key concept in Algebraic Combinatorics and have given place to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study almost distance-regular graphs'. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called m-walk-regularity.
Another studied concept is that of m-partial distance-regularity, or informally, distance-regularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of (l,m)-walk-regularity. We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.

This is joint work with E.R. van Dam, M.A. Fiol, E. Garriga, B.L. Gorissen.

Thursday May 27, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Local spectrum of the subconstituents and completely pseudo-regular codes
Marc Càmara, UPC

Abstract

The local spectrum of a set of vertices in a graph has been proven to be of great utility to study several metric properties of sets of vertices.
It also has applications in the area of pseudo-distance-regularity around a set and can be used to obtain quasi-spectral characterizations of completely  (pseudo-)regular codes. In this work we study the relation between the local spectrum of a set and that of its subconstituents.
Moreover, we obtain a characterization for completely pseudo-regular codes, and consequently for completely regular codes, in terms of the relation between the local spectrum of an extremal set and the local spectrum of its antipodal set.

This is a joint work with J. Fàbrega, M.A. Fiol and E. Garriga.

Thursday May 20, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Tree Automata and the HOM problem
Omer Giménez, UPC

Abstract

The HOM problem consists in determining, given a tree homomorphism $H$ and a regular tree language $L$ represented by a tree automaton, whether $H(L)$ is regular. Recently, we have been able to obtain an algorithm deciding the HOM problem, which was a long standing open question. We solve the HOM problem and we obtain several significant intermediate results by means of a new class of tree automata with arbitrary inequality constraints and a particular kind of equality constraints.

This is joint work with Guillem Godoy, Lander Ramos and Carme Alvarez.

Thursday May 20, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Linear systems over composite moduli

Abstract

We study solution sets to systems of 'generalized' linear equations of the form: ell_i (x_1, x_2,..., x_n) in A_i (mod m) where ell_1,..., ell_t are linear forms in n Boolean variables, each A_i is an arbitrary subset of Z_m, and m is a composite integer that is a product of two distinct primes, like 6. Our main technical result is that such solution sets have exponentially small correlation, i.e. with the boolean function MOD_q, when m and q are relatively prime. This bound is independent of the number t of equations. This yields progress on limiting the power of constant-depth circuits with modular gates. We derive the first exponential lower bound on the size of depth-three circuits of type having a MAJORITY gate at the top, AND/OR gates at the middle layer and generalized MOD_m gates at the base, computing the function MOD_q.

This settles an open problem of Beigel and Maciel (Complexity'97) for the case of such modulus m. Our technique makes use of the work of Bourgain on estimating exponential sums involving a low-degree polynomial and ideas involving matrix rigidity from the work of Grigoriev and Razborov on arithmetic circuits over finite fields.

Thursday May 13, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Asymptotic study of subcritical graph classes
Juanjo Rué, Laboratoire d'Informatique, Ecole Polytechnique, Palaiseau, France

Abstract

We present a unified general method for the asymptotic study of graphs from the so-called "subcritical" graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works both in the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number $g_n/n!$ (resp. $g_n$) of labelled (resp. unlabelled) graphs on $n$ vertices from a subcritical graph class ${\cG}=\cup_n {\cG_n}$ satisfies asymptotically the universal behaviour $$g_n = c n^{-5/2} \gamma^n\ (1+o(1))$$ for computable constants $c,\gamma$, e.g. $\gamma\approx 9.38527$ for unlabelled series-parallel graphs, and that the number of vertices of degree $k$ ($k$ fixed) in a graph chosen uniformly at random from $\cG_n$, converges (after rescaling) to a normal law as $n\to\infty$.

This is a joint work with Michael Drmota, Eric Fusy Mihyun Kang and Veronika Kraus.

Thursday May 13, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Graph Operations and Laplacian Eigenpolytopes

Abstract

We introduce the Laplacian eigenpolytopes (L-polytopes'') associated to a simple undirected graph G, investigate how they change under basic operations such as taking the union, join, complement, line graph and cartesian product of graphs, and show how several famous'' polytopes arise as L-polytopes of famous'' graphs.

Eigenpolytopes have been previously introduced by Godsil, who studied them in detail in the context of distance-regular graphs. Our focus on the Laplacian matrix, as opposed to the adjacency matrix of G, permits simpler proofs and descriptions of the result of operations on not necessarily distance-regular graphs. Additionally, it motivates the study of new operations on polytopes, such as the Kronecker product.

Thus, we open the door to a detailed study of how combinatorial properties of G are reflected in its L-polytopes. Subsequent papers will use these tools to construct interesting polytopes from interesting graphs, and vice versa.

Thursday May 6, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Vosperian and superconnected vertex transitive graphs
Susana López-Masip, UPC

Abstract

We investigate the structure of a digraph  having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We improve most of the existing results in this area.

This is joint work with Yahya Hamidoune and Anna Lladó.

Thursday May 6, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Empty monochromatic triangles
Clemens Huemer, UPC

Abstract

We consider a variation of a problem stated by Erd\"os and Guy in 1973 about the number of convex $k$-gons determined by any set $S$ of $n$ points in the plane. In our setting the points of $S$ are colored and we say that a spanned polygon is monochromatic if all its points are colored with the same color. As a main result we show that any bi-colored set of $n$ points in $\mathbb{R}2$ in general position determines a super-linear number of empty monochromatic triangles, namely $\Omega(n^{5/4})$. We also discuss the subsequent improvement of J. Pach and G. Tóth to $\Omega(n^{4/3})$.

This is a joint work with Oswin Aichholzer, Ruy Fabila, David Flores, Thomas Hackl and Jorge Urrutia.

Thursday April 29, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Determining the maximal subset of a finite vector space in which every subset of basis size is a basis
Simeon Ball
UPC

Abstract

In 1947 Bose proved that in a $3 \times (p+2)$ matrix, with entries from ${\mathbb F}_p$, $p \geq 3$, there are 3 columns which are linearly dependent, He knew that the matrix whose columns are $(1,x,x^2)$, for each $x \in {\mathbb F}_p$, and $(0,0,1)$ is a $3 \times (p+1)$ matrix in which no 3 columns are linearly dependent.
In 1955 Segre, proved, up to a change of basis, that for $p \geq 3$, this is the only $3 \times (p+1)$ matrix in which no 3 columns are linearly dependent.

Segre asked if a $k \times (p+2)$ matrix, $k \leq p$, always has $k$ columns that are linearly dependent. For $k \geq p+1$, it is easy to see that this cannot be true.

In 1955 Segre proved that it is indeed the case for $k=4,5,p-3,p-2,p-1,p$ and in 1967 proved his conjecture'' for $k < \sqrt{p}/2+c$. In 1990 Voloch proved the conjecture for $k<p/45+c$.

The row space of the $k \times n$ matrix, in which no $k$ columns are linearly dependent, is a linear maximum distance separable code and the conjecture $n \leq p+1$, become known as the main conjecture for maximum distance separable codes (over prime fields). The conjecture is similar over non-prime fields.

In this talk I shall discuss how to prove the conjecture and moreover, how to prove that a $k \times (p+1)$ matrix, $p \geq k$, in which no $k$ columns are linearly dependent, is equivalent, up to a change of basis, to the matrix whose columns are $(1,x,x^2,\ldots,x^{k-1})$, for each $x \in {\mathbb F}_p$, and $(0,\ldots,0,1)$.

Time permitting I shall also discuss the non-prime case.

Thursday April 22, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### On the Number of Local Configurations on Sturmian words and Discrete Planes
Laurent Vuillon
LAMA, Université de Savoie, CNRS

Abstract

In this talk, we recall the nice enumerative properties of Sturmian words (words given by discretization of lines with non rational slopes). We propose to generalize several results from dimension two to dimension three. That is to count the number of local configurations on discrete planes.

We will see that the problem is very difficult and we have only a solution for the enumeration of the rectangular factors of size 1*n and 2 * n, with n in N , occurring in at least one discrete plane.  This allows us to enumerate the number of planar discrete configurations of size 2 * n and extends to discrete planes several works on discrete lines. The general  enumeration of the rectangular factors of size m*n , with m and n  in N, occurring in at least is still an open problem.

Thursday April 15, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Cyclic Flats, Sticky Matroids, and Intertwines
Joseph E. Bonin
Department of Mathematics, The George Washington University

Abstract

There are many perspectives that one can take on matroids. This talk uses recent progress on two problems to illustrate the merits of the approach to matroid theory via cyclic flats and their ranks, which was developed independently by Julie Sims and by J. Bonin and Anna de Mier. (Sufficient background in matroid theory will be provided to make this talk accessible.)

The first problem we consider is the sticky matroid conjecture. Given a matroid, can each pair of extensions by disjoint sets be glued together'? Matroids with this property are called sticky. It is
conjectured that sticky matroids are precisely modular matroids (which are direct sums of projective geometries). For a wide class of non-modular matroids, we use cyclic flats to construct pairs of extensions that contain incompatible geometric structures and so cannot be glued together, thus showing that these non-modular matroids are not sticky.

The second problem is that of intertwines. An intertwine of a pair of matroids (or graphs) is a matroid (or graph) such that it, but none of its proper minors, has minors that are isomorphic to each matroid (or graph) in the pair. Intertwines arise naturally when considering the unions of minor-closed classes of matroids or graphs. A corollary of Robertson and Seymour's graph minors theorem is that any pair of graphs has only finitely many intertwines. We show that the situation is very different for matroids: we use cyclic flats to construct infinite sets of intertwines for a broad class of pairs of matroids.

Thursday March 25, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### On the diameter of random planar graphs
Marc Noy
UPC

Abstract

We show that the diameter Diam(G_n) of a random labelled connected planar graph with n vertices is asymptotically almost surely of order n^{1/4} with exponential probability.

More precisely, there exists a constant c > 0 such that

Prob(n^{1/4 - epsilon} < Diam(G_n)< n^{1/4 + epsilon}) > 1-exp(-n^{c*epsilon})

for epsilon small enough and n large enough (depending on epsilon).

This is in contrast with other families of graphs, like trees or series-parallel graphs, where the diameter is a.a.s. of order n^{1/2}.

The starting point of our proof is a similar (but much more precise) result by Chassaing and Schaeffer for planar quadrangulations. We prove the result first for planar maps, and then for 2-connected maps, using the fact that a random map  has a 2-connected component of linear size a.a.s. A similar argument allows us  to extend the result to 3-connected maps, which proves it also for 3-connected  planar graphs, because they have a unique embedding in the sphere. We then reverse  the previous arguments and go first to 2-connected and then connected planar graphs.

Our approach uses generating functions in a fundamental way, together large deviation estimates, saddle-point bounds, and other tools.

We'll keep the talk at a non-technical level showing the main ideas in the proof.

This is joint work with Guillaume Chapuy, Eric Fusy and Omer Giménez.

Thursday March 18, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Most groups are hyperbolic... or most groups are trivial?
Enric Ventura
UPC

Abstract

The sentence "Most groups are hyperbolic" was claimed by  Gromov in 1987 without proof.

Later, the statement was made precise and was proved by Ol'shanski.

We adopt a different point of view and introduce a different and equaly natural way of enumerating group presentations. It happens that, with respect to this new enumeration, the result is surprisingly different: "most groups are trivial". The proof uses Stallings graphs, to represent subgroups of the free group, and partial permutations to enumerate such graphs.

(this is joint work with F. Bassino, C. Nicaud, A. Martino and P. Weil)

Thursday March 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Even and quasi-even triangulations of point sets in the plane
Alberto Márquez

Abstract

Given a point set in the plane, we consider to different kind of triangulations, those with all the vertices with even degree (even triangulations or e-triangulations for short) and those with all non-extreme points with even degree (quasi-even triangulations or q-e-triangulations for short). These particular cases of triangulations are interesting by the following reason:

It is known form the four colors theorem that any triangulation of a point set can be colored using at most four colors. It is not difficult to see that q-e-triangulations are exactly those that can be colored with 3 colors. Aditionally, e-triangulations are, of course eulerian.

In this talk, we study e-triangulations for a point set in convex position, and q-e-triangulations for point sets in general position.

Thursday February 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Recent progress on the Merino-Welsh Conjecture concerning the Tutte polynomial
Steve Noble
Department of Mathematical Sciences, Brunel University

Abstract

Merino and Welsh conjectured that for any 2-connected loopless graph, either the number of acyclic orientations or the number of totally cyclic orientations is at least the number of spanning trees. Equivalently max {T(G;2,0), T(G;0,2)} >=3D T(G;1,1).
Jackson has shown that max {T(G;3,0), T(G;0,3)} >=3D T(G;1,1).

We simplify and extend Jackson's method to give sufficient conditions on G for when max {T(G;x,y), T(G;y,x)} >=3D T(G;z,z).
We also show that max {T(G;4,0), T(G;0,4)} >=3D T(G;2,2) and that for some large classes of graphs max {T(G;2a,0), T(G;0,2a)} >=3D T(G;a,a) providing a>=3D2. Finally we show = that for paving matroids the Tutte polynomial is convex along the portion of any line x+y=3Dc lying in the positive quadrant.

This is joint work with Bill Jackson, Laura Chavez, Criel Merino, Marcelino Ramirez and Dave Wagner.

Thursday February 4, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Pointing, enumeration, and random generation in unlabelled combinatorial classes
Éric Fusy
École Polytechnique, Paris

Abstract

Pointing is a very efficient tool to perform enumeration and random generation in a combinatorial class, as it gives a way to start a recursive decomposition. In the labelled case, the approach works fine because all atoms are distinguishable, hence pointing multiplies by $n$ the $n$th counting coefficient and preserves the fixed-size uniform distribution. In contrast, in the unlabelled case, the pointing approach does not adapt straightforwardly because a structure of size n can give rise to less than n pointed structures (rooting at two vertices in symmetric position gives the same rooted object).

In this talk, we present a pointing operator, called cycle-pointing'',  such that each unlabelled unrooted structure of size n gives rise to n unlabelled pointed structures. This yields an automatic exact/asymptotic enumeration method for unlabelled combinatorial classes (such as trees and graph families), and it gives rise to  very efficient random generators, which rely on the principles of Boltzmann samplers''.

Thursday January 28, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
##### The Colorful Helly Property for Hypergraphs
Jayme L Swarcfiter
Federal University of Rio de Janeiro

Abstract

The definition of the Helly property for hypergraphs was motivated by Helly's theorem for convex sets. Similarly, we define the colorful Helly property for a family of hypergraphs, motivated by the colorful Helly theorem for collections of convex sets, by Lov\'asz. We describe some general facts about the colorful Helly property and prove complexity results. In particular, we show that it is Co-NP-complete to decide if a family of $p$ hypergraphs is colorful Helly, even if $p = 2$. However, for any fixed $p$, we describe a polynomial time algorithm to decide if such family is colorful Helly, provided at least $p-1$ of the hypergraphs are $p$-Helly.

Joint work with R. Barbosa, E. Martins and M. Dourado.

Wednesday January 20, 2010, 15h
Aula 101 FME
Campus Sud UPC
##### Extensions of the  Scherck-Kemperman Theorem
Yahya O. Hamidoune
Univ. Paris 6

Abstract

Let $\Gamma =(V,E)$  be a  directed graph with a transitive automorphisms group. Let $v\in V$ and let $F$ be a finite subset of $V$ with $v\in F.$ As usual we denote by $\Gamma (F)$ the image of $F.$

We prove that the size of $\Gamma (F)$ is at least  $$|F|+ |\Gamma (v)|-|\Gamma ^- (v)\cap F|.$$

Let  $A,B$ be finite subsets of a group $G.$ Applied to Cayley graphs, our result reduces to the following extension of the Scherk-Kemperman Theorem, proved by Kemperman: $$|AB|\ge |A|+|B|-|A\cap (cB^{-1})|,$$ for every  $c\in AB.$

Thursday December 17, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Shannon capacity and the perfectness of graphs
Ron Holzman
Technion - Israel Institute of Technology

Abstract

The Shannon capacity of a graph measures the maximal volume of error-free communication on a noisy channel described by the graph. This is a fundamental notion in information theory, and it has motivated some challenging problems in graph theory. In particular, it prompted the study of perfect graphs, which deals with the relation between the chromatic number and the size of a maximum clique. In the talk I will present these concepts and the connection between them, highlighting some of the remarkable mathematical achievements in this area.

Thursday December 10, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Classification of Construction Techniques of Large Directed Graphs
Slamin
Universitas Jember, Indonesia

Abstract

We classify the construction techniques of large directed graphs. We first present the construction techniques that have been established, namely, the generalised de Bruijn digraphs, generalised Kautz digraphs, line digraphs, digon reduction, generalised digraphs on alphabets, partial line digraphs, digraphs constructed by the use of voltage assignments and vertex deletion scheme. Then we classify the construction techniques according to the general method of generating new digraphs; the diregularity of generated digraphs; and the range of orders of the generated digraphs.

Thursday December 3, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
##### Random graphs with few disjoint cycles
Colin McDiarmid
Oxford University

Abstract