Longest run of equal parts in a random integer composition

This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the longest run of consecutive equal parts in a composition of size n$n$. The problem was posed by Herbert Wilf at the Analysis of Algorithms conference in July 2009 (see arXiv:0906.5196).     

On linear forbidden submatrices

In this paper we study the extremal problem of finding how many 1 entries an n by n 0-1 matrix can have if it does not contain certain forbidden patterns as submatrices. We call the number of 1 entries of a 0-1 matrix its weight. The extremal function of a pattern is the maximum weight of an n by n 0-1 matrix that does not contain this pattern as a submatrix. We call a pattern (a 0-1 matrix) linear if its extremal function is O(n). Our main results are modest steps towards the elusive goal of characterizing linear patterns. We find novel ways to generate new linear patterns from known ones and use this to prove the linearity of some patterns. We also find the first minimal non-linear pattern of weight above 4. We also propose an infinite sequence of patterns that we conjecture to be minimal non-linear but have Ω(nlogn) as their extremal function. We prove a weaker statement only, namely that there are infinitely many minimal not quasi-linear patterns among the submatrices of these matrices. For the definition of these terms see below.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

Polyhedral results on single node variable upper-bound flow models with allowed configurations

In this paper we investigate the convex hull of single node variable upper-bound flow models with allowed configurations. Such a model is defined by a set , where ρ is one of , = or , and Z{0,1}ⁿ consists of the allowed configurations. We consider the case when Z consists of affinely independent vectors. Under this assumption, a characterization of the non-trivial facets of the convex hull of X_ρ(Z) for each relation ρ is provided, along with polynomial time separation algorithms. Applications in scheduling and network design are also discussed.     

Enumeration and limit laws of dissections on a cylinder

We compute the generating function for triangulations on a cylinder, with the restriction that all vertices belong to its boundary and that the intersection of a pair of different faces is either empty, a vertex or an edge. We generalize these results to maps with either constant ({k}-dissections) or unrestricted (unrestricted dissections) face degree. We apply singularity analysis to the resulting generating functions to obtain asymptotic estimates for their coefficients, as well as limit distributions for natural parameters.     

On packing and covering polyhedra of consecutive ones circulant clutters

Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehman’s work or blocker/antiblocker duality, as is traditional in the field.     

TANGENT UNIT-VECTOR FIELDS:NONABELIAN HOMOTOPY INVARIANTS AND THE DIRICHLET ENERGY

Let O be a closed geodesic polygon in S~2 . Maps from O into S~2 are said to satisfy tangent boundary conditions if the edges of O are mapped into the geodesics which contain them. Taking O to be an octant of S 2,we compute the infimum Dirichlet energy E(H) for continuous maps satisfying tangent boundary conditions of arbitrary homotopy type H . The expression for E (H ) involves a topological invariant - the spelling length - associated with the (non-abelian) fundamental group of the n-times punctured two-sphere, π 1 (S 2 ? {s 1 , ··· , s n }, ?). The lower bound for E(H) is obtained from combinatorial group theory arguments, while the upper bound is obtained by constructing explicit representa- tives which, on all but an arbitrarily small subset of O, are alternatively locally conformal or anticonformal. For conformal and anticonformal classes (classes containing wholly con- formal and anticonformal representatives respectively), the expression for E (H ) reduces to a previous result involving the degrees of a set of regular values s 1 , ··· , s n in the target S 2 space. These degrees may be viewed as invariants associated with the abelianization of π 1 (S 2 ? {s 1 , ··· , s n }, *). For nonconformal classes, however, E(H) may be strictly greater than the abelian bound. This stems from the fact that, for nonconformal maps, the number of preimages of certain regular values may necessarily be strictly greater than the absolute value of their degrees.This work is motivated by the theoretical modelling of nematic liquid crystals in confined polyhedral geometries. The results imply new lower and upper bounds for the Dirichlet energy (one-constant Oseen-Frank energy) of reflection-symmetric tangent unit- vector fields in a rectangular prism.     

Tautologies over implication with negative literals

We consider logical expressions built on the single binary connector of implication and a finite number of literals (Boolean variables and their negations). We prove that asymptotically, when the number of variables becomes large, all tautologies have the following simple structure: either a premise equal to the goal, or two premises which are opposite literals (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Generating unlabeled connected cubic planar graphs uniformly at random

We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted connected cubic planar graphs, i.e., we count connected cubic planar graphs up to isomorphisms that fix a certain directed edge. Based on decompositions along the connectivity structure, we derive recurrence formulas for the exact number of rooted cubic planar graphs. This leads to rooted 3‐connected cubic planar graphs, which have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a sense‐reversing automorphism. Therefore we introduce the concept of colored networks, which stand in bijective correspondence to rooted 3‐connected cubic planar graphs with given symmetries. Colored networks can again be decomposed along the connectivity structure. For rooted 3‐connected cubic planar graphs embedded in the plane, we switch to the dual and count rooted triangulations. Since all these numbers can be evaluated in polynomial time using dynamic programming, rooted connected cubic planar graphs can be generated uniformly at random in polynomial time by inverting the decomposition along the connectivity structure. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008