# Seminar 2009-2010

Sessions and Abstracts

## Sessions

(Download all abstracts in PDF.)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, UPCRouting in Social Networks Dieter Mitsche, CRM | Thursday June 3, 2010, 12h Aula 005 Modul C3 Campus Nord UPC |

Almost Distance-Regular Graphs Cristina Dalfó, UPCLocal 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, UPCLinear systems over composite moduli Arkadev Chattopadhyay, University of Toronto | 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 Arnau Padrol, UPC | Thursday May 13, 2010, 12h Aula 005 Modul C3 Campus Nord UPC |

Vosperian and superconnected vertex transitive graphs Susana López-Masip, UPCEmpty 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 Universidad de Sevilla | Thursday March 11, 2010, 12h Aula 005 Modul C3 Campus Nord UPC |

Recent progress on the Merino-Welsh Conjecture concerning the Tutte polynomial Steve NobleDepartment 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 |

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 AlonTel 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 SauINRIA, 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

Aula 005 Modul C3

Campus Nord UPC

##### Semiregular cages with odd girth are edge-superconnected

**Julián Salas, UPC**

Abstract

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

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

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

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.

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

Thursday May 27, 2010, 12h

Aula 005 Modul C3

Campus Nord UPC

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.

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

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.

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

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.

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

Thursday May 20, 2010, 12h

Aula 005 Modul C3

Campus Nord UPC

Aula 005 Modul C3

Campus Nord UPC

##### Linear systems over composite moduli

**Arkadev Chattopadhyay, University of Toronto**

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

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

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.

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

Aula 005 Modul C3

Campus Nord UPC

##### Graph Operations and Laplacian Eigenpolytopes

**Arnau Padrol, UPC**

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

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

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

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

Thursday May 6, 2010, 12h

Aula 005 Modul C3

Campus Nord UPC

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.

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

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.

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

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.

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

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.

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

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.

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

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)

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**

Universidad de Sevilla

Universidad de Sevilla

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

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

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.

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

É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''.

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

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.

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

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

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

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

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

Oxford University

*Abstract*

Fix a positive integer $k$, and consider the class of all graphs which do not have $k+1 vertex-disjoint cycles. A classical result of Erd\H{o}s and P\'{o}sa says that each such graph $G$ contains a blocker of size at most $f(k)$. Here a {\em blocker} is a set $B$ of vertices such that $G-B$ has no cycles.

We give a seemingly minor but useful extension of this result, and deduce that almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of size $k$. This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $R_n$ taken uniformly at random from the class: we see for example that the probability that $R_n$ is connected tends to a specified limit as $n \to \infty$.

There are corresponding results when we consider unlabelled graphs with few disjoint cycles.

We consider also variants of the problem involving for example disjoint long cycles.

This is recent joint work with Valentas Kurauskas and Mihyun Kang.

We give a seemingly minor but useful extension of this result, and deduce that almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of size $k$. This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $R_n$ taken uniformly at random from the class: we see for example that the probability that $R_n$ is connected tends to a specified limit as $n \to \infty$.

There are corresponding results when we consider unlabelled graphs with few disjoint cycles.

We consider also variants of the problem involving for example disjoint long cycles.

This is recent joint work with Valentas Kurauskas and Mihyun Kang.

Thursday November 26, 2009, 12h

Aula 005 Modul C3

Campus Nord UPC

##### Large sets in Finite Fields are Sumsets

**Noga Alon**

Tel Aviv University

Tel Aviv University

*Abstract*

I will sketch a proof of the fact that for a prime p, every complement of a set of roughly sqrt p elements of the finite field Z_p is a sumset, that is, is of the form A+A, whereas there are complements of sets of size roughly p^{2/3} which are not sumsets. This improves estimates of Green and Gowers, and can also be used to settle a related problem of Nathanson.

Thursday November 12, 2009, 12h

Aula 005 Modul C3

Campus Nord UPC

##### Small vertex-transitive and Cayley graphs of girth 6 and 5

**Jozef Siran**

Slovak University of Technology in Bratislava and The Open University

Slovak University of Technology in Bratislava and The Open University

*Abstract*

We examine constructions of the smallest known vertex-transitive graphs of a given degree and girth 6 and 5. Most of these graphs can be described in terms of regular lifts of suitable smaller graphs, and we determine which of these are Cayley graphs. We also investigate higher level of transitivity of the smallest known vertex-transitive graphs of a given degree and girth $6$ and relate their constructions to near-difference sets.

Thursday November 5 2009, 12h

Aula 005, ModulC3

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

The University of Newcastle, Australia

University of West Bohemia, Czech Republic

King’s College London, UK

*Abstract*

We consider three parameters of a graph: the order (number of vertices), maximum degree (or degree in case of a regular graph) and the diameter. Three related problems arise with respect to these parameters by fixing in turn two of the parameter and optimizing the third one. For example, optimizing the order, given the maximum degree and diameter gives the (undirected) degree/diameter problem: find the maximum possible number of vertices in a graph with given diameter and maximum degree. The corresponding problem for directed graphs uses maximum out-degree instead of maximum degree.

In this talk we will give an overview of the progress of the degree/diameter problem for both directed and undirected graphs, and we

consider also the less-studied order/degree and order/diameter problems.

We conclude with a number of related open problems.

In this talk we will give an overview of the progress of the degree/diameter problem for both directed and undirected graphs, and we

consider also the less-studied order/degree and order/diameter problems.

We conclude with a number of related open problems.

Thursday October 29, 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

INRIA, Nice and UPC Barcelona

*Abstract*

This talk will overview some of the results of my thesis, which has been defended on October 16 in Sophia Antipolis (France). The final version of the manuscript can be found here: http://www-sop.inria.fr/members/Ignasi.Sauvalls/PhD_Ignasi.pdf. The first part is devoted to traffic grooming, which is a central problem in optical networks. It refers to packing low-rate signals into higher-speed streams, in order to improve bandwidth utilization and reduce the network cost. The objective is to minimize the number of Add-Drop Multiplexers (ADMs), which are devices that insert/extract low-rate traffic to/from a high-speed stream. In graph-theoretical terms, the problem can be translated into finding a partition of the edges of a request graph into subgraphs with bounded number of edges, the objective being to minimize the total number of vertices of the partition. We first focus in Chapter 1 on a general request graph when the topology is a ring or a path. We provide the first inapproximability result for traffic grooming for fixed values of the grooming factor C, answering affirmatively to a conjecture in the literature. We also provide a polynomial-time approximation algorithm for traffic grooming in rings and paths, with an approximation ratio independent of C. We introduce in Chapter 2 a new model of traffic grooming in unidirectional rings, in order to design networks being able to support any request graph with bounded maximum degree. We show that the problem is essentially equivalent to finding the least integer M(C,D) such that the edges of any graph with maximum degree at most D can be partitioned into subgraphs with at most C edges and each vertex appears in at most M(C,D) subgraphs, and we establish the value of M(C,D) for almost all values of C and D. In Chapter 3 we focus on traffic grooming in bidirectional rings with symmetric shortest path routing and all-to-all unitary requests, providing general lower bounds and infinite families of optimal solutions for C=1,2,3 and C of the form k(k+1)/2. In Chapter 4 we study traffic grooming for two-period optical networks, a variation of the traffic grooming problem for WDM unidirectional ring networks with two grooming factors C and C' that allows some dynamism on the traffic. Using tools of graph decompositions, we determine the minimum number of ADMs for C=4, and C'=1,2,3.

The study of the traffic grooming problem leads naturally to the study of a family of graph-theoretical problems dealing with general constraints on the degree. This is the topic of the second part of this thesis. We begin in Chapter 5 by studying the computational complexity of several families of degree-constrained problems, giving hardness results and polynomial-time approximation algorithms. We then study in Chapter 6 the parameterized complexity of finding degree-constrained subgraphs, when the parameter is the size of the subgraphs. We prove hardness results in general graphs and provide explicit fixed-parameter tractable algorithms for minor-free graphs. We obtain in Chapter 7 subexponential parameterized and exact algorithms for several families of degree-constrained subgraph problems on planar graphs, using bidimensionality theory combined with novel dynamic programming techniques. Finally, we provide in Chapter 8 a framework for the design of dynamic programming algorithms for surface-embedded graphs with single exponential dependence on branchwidth. Our approach is based on a new type of branch decomposition called surface cut decomposition, which generalizes sphere cut decompositions for planar graphs. The existence of such algorithms is proved using diverse techniques from topological graph theory and analytic combinatorics.

The study of the traffic grooming problem leads naturally to the study of a family of graph-theoretical problems dealing with general constraints on the degree. This is the topic of the second part of this thesis. We begin in Chapter 5 by studying the computational complexity of several families of degree-constrained problems, giving hardness results and polynomial-time approximation algorithms. We then study in Chapter 6 the parameterized complexity of finding degree-constrained subgraphs, when the parameter is the size of the subgraphs. We prove hardness results in general graphs and provide explicit fixed-parameter tractable algorithms for minor-free graphs. We obtain in Chapter 7 subexponential parameterized and exact algorithms for several families of degree-constrained subgraph problems on planar graphs, using bidimensionality theory combined with novel dynamic programming techniques. Finally, we provide in Chapter 8 a framework for the design of dynamic programming algorithms for surface-embedded graphs with single exponential dependence on branchwidth. Our approach is based on a new type of branch decomposition called surface cut decomposition, which generalizes sphere cut decompositions for planar graphs. The existence of such algorithms is proved using diverse techniques from topological graph theory and analytic combinatorics.

Thursday October 22, 2009, 12h

Aula 005 Modul C3

Campus Nord UPC

##### Closed formulae from almost closed formulae in 3-generated numerical semigroups

**Francesc Aguiló**

UPC, Barcelona

UPC, Barcelona

*Abstract*

Let $S=<a,b,N>$ be a numerical 3-semigroup, that is $a<b<N$, $\gcd(a,b,N)=1$ and the generating set of $\{a,b,N\}$ of $S$ is minimal.

Let us consider the weighted double-loop digraph $G(N;a,b;a,b)$ and a related minimum distance diagram $H=L(l,h,w,y)$. We say that the 2D periodic tessellation by $H$ is related to the semigroup $S$.

From the numerical point of view, it is a known fact that several properties of $S$ can be efficiently derived from $H$: The Frobenius' number, the ApÃ©ry set $Ap(N;S)$, the set of gaps (and its cardinal) and the set of factorizations of any $m\in S$

\[

F(S;m)=\{(x,y,z)\in\Nat3~|~xa+yb+zN=m\}

\] and the related denumerant $d(S;m)=|F(S;m)|$.

From the symbolical point of view, we can derive closed formulae from the previous numerical information. Symbolical questions arise from the need of closed formulae for a sequence of semigroups $\{S_n\}_{n\geq n_0}$, usually for sequences of some interest.

This talk focuse the main goal on the sequence $S_n=<n-2,n-1,n>$, for even $n\geq6$, which are the only 3-generated critical semigroups attaining the optimal value for the Frobenius' number. That is, set

\[

G(n)=\max_{1<a<n,\gcd(a,b,n)=1}f(<a,b,n>).

\]

Then Lewin gave the expression of $G(n)$ and all the critical semigroups: $<n/2,n-1,n>$ and $<n-2,n-1,n>$ for even $n$, and $<(n-1)/2,n-1,n>$ when $n$ is odd.

For this sequence of semigroups, we will study the distribution of the denumerants between the pair of maximal gaps of $S_n$. We will give the critical values $m^*$ for the maximal denumerant and the related factorization sets $F(S_n;m^*)$ as well.

Let us consider the weighted double-loop digraph $G(N;a,b;a,b)$ and a related minimum distance diagram $H=L(l,h,w,y)$. We say that the 2D periodic tessellation by $H$ is related to the semigroup $S$.

From the numerical point of view, it is a known fact that several properties of $S$ can be efficiently derived from $H$: The Frobenius' number, the ApÃ©ry set $Ap(N;S)$, the set of gaps (and its cardinal) and the set of factorizations of any $m\in S$

\[

F(S;m)=\{(x,y,z)\in\Nat3~|~xa+yb+zN=m\}

\] and the related denumerant $d(S;m)=|F(S;m)|$.

From the symbolical point of view, we can derive closed formulae from the previous numerical information. Symbolical questions arise from the need of closed formulae for a sequence of semigroups $\{S_n\}_{n\geq n_0}$, usually for sequences of some interest.

This talk focuse the main goal on the sequence $S_n=<n-2,n-1,n>$, for even $n\geq6$, which are the only 3-generated critical semigroups attaining the optimal value for the Frobenius' number. That is, set

\[

G(n)=\max_{1<a<n,\gcd(a,b,n)=1}f(<a,b,n>).

\]

Then Lewin gave the expression of $G(n)$ and all the critical semigroups: $<n/2,n-1,n>$ and $<n-2,n-1,n>$ for even $n$, and $<(n-1)/2,n-1,n>$ when $n$ is odd.

For this sequence of semigroups, we will study the distribution of the denumerants between the pair of maximal gaps of $S_n$. We will give the critical values $m^*$ for the maximal denumerant and the related factorization sets $F(S_n;m^*)$ as well.

Thursday October 1, 12h

Aula 005 Modul C3

Campus Nord UPC

##### A new addition theorem in Z/pZ via the polynomial method

**Éric Balandraud**

Univ Paris 6

Univ Paris 6

*Abstract*

Following the classical addition theorems in Z/pZ: Cauchy-Davenport Theorem, Hamidoune Da Silva Theorem (known as Erdos-Heilbronn Conjecture), we will present a new addition theorem, that express the minimal size of the set of subsums of a set.

The proof is based on the polynomial method and is very similar of Alon Nathanson Rusza's proof of Hamidoune-Da Silva's Theorem. We will expose the ideas of this proof and some consequences of this new addition theorem.

The proof is based on the polynomial method and is very similar of Alon Nathanson Rusza's proof of Hamidoune-Da Silva's Theorem. We will expose the ideas of this proof and some consequences of this new addition theorem.

Tuesday September 22, 12h

Aula 005 Modul C3

Campus Nord UPC

##### Enumeration of indecomposable permutations and of topological maps

on orientable surfaces

**Robert Cori**

Uni. Bordeaux I and Ecole Polytechnique, Paris

Uni. Bordeaux I and Ecole Polytechnique, Paris

*Abstract*

A permutation $a_1a_2\ldots a_n$ is indecomposable if there does not exist $p<n$ such that $a_1a_2\ldots a_p$ is a permutation of $\{ 1,2,\ldots ,p\}$. We give a formula for the number of indecomposable permutations of of ${\mathbb S}_n$ with $m$ cycles and compute the asymptotic probability that a permutation is indecomposable as $n$ goes to infinity with $m/n$ fixed. The asymptotic probability is monotone in $m/n$, and there is no threshold phenomenon: it degrades gracefully from 1 to 0.

When $n=2m$, a slight majority ($51.1\ldots$ percent) of the permutations are indecomposable. We also consider indecomposable fixed point free involutions which are in bijection with maps of arbitrary genus on orientable surfaces, for these involutions with $m$ left-to-right maxima we obtain a lower bound for the probability of being indecomposable.

When $n=2m$, a slight majority ($51.1\ldots$ percent) of the permutations are indecomposable. We also consider indecomposable fixed point free involutions which are in bijection with maps of arbitrary genus on orientable surfaces, for these involutions with $m$ left-to-right maxima we obtain a lower bound for the probability of being indecomposable.