Seminar 2009-2010

Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC

Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC

Thursday June 3, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC

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

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

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

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

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

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

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

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

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

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.

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

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.

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.

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)

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.