Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various tree-like data structures, maps, tilings, RNA molecules. They can be adapted to combinatorial specifications with additional parameters, allowing for a more flexible control over the output profile of parametrised combinatorial patterns. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain sub-patterns in generated strings. However, such a flexible control requires an additional and nontrivial tuning procedure. Using techniques of convex optimisation, we present an efficient tuning algorithm for multi-parametric combinatorial specifications. Our algorithm works in polynomial time in the system description length, the number of tuning parameters, the number of combinatorial classes in the specification, and the logarithm of the total target size. We demonstrate the effectiveness of our method on a series of practical examples, including rational, algebraic, and so-called Pólya specifications. We show how our method can be adapted to a broad range of less typical combinatorial constructions, including symmetric polynomials, labelled sets and cycles with cardinality lower bounds, simple increasing trees or substitutions. Finally, we discuss some practical aspects of our prototype tuner implementation and provide its benchmark results.

A set of integers is primitive if it does not contain an element dividing another. Let f(n) denote the number of maximum-size primitive subsets of {1,…,2n}. We prove that the limit α = limn→∞f(n)1/n exists. Furthermore, we present an algorithm approximating α with (1 + ε) multiplicative error in N(ε) steps, showing in particular that α ≈ 1.318. Our algorithm can be adapted to estimate the number of all primitive sets in {1,…,n} as well.

We address another related problem of Cameron and Erdős. They showed that the number of sets containing pairwise coprime integers in {1,…n} is between ${2^{\pi (n)}} \cdot {e^{(1/2 + o(1))\sqrt n }}$ and ${2^{\pi (n)}} \cdot {e^{(2 + o(1))\sqrt n }}$. We show that neither of these bounds is tight: there are in fact ${2^{\pi (n)}} \cdot {e^{(1 + o(1))\sqrt n }}$ such sets.

We present some partial results concerning two conjectures of Schützenberger on evacuations of Young tableaux.

The orthogonal projection of the free associative algebra onto the free Lie algebra is afforded by an idempotent in the rational group algebra of the symmetric group ${{S}_{n}}$, in each homogenous degree $n$. We give various characterizations of this Lie idempotent and show that it is uniquely determined by a certain unit in the group algebra of ${{S}_{n-1}}$. The inverse of this unit, or, equivalently, the Gram matrix of the orthogonal projection, is described explicitly. We also show that the Garsia Lie idempotent is not constant on descent classes (in fact, not even on coplactic classes) in ${{S}_{n}}$.

A general analytic scheme for Poisson approximation to discrete distributions is studied in which the asymptotic behaviours of the generalized total variation, Fortet-Mourier (or Wasserstein), Kolmogorov and Matusita (or Hellinger) distances are explicitly characterized. Applications of this result include many number-theoretic functions and combinatorial structures. Our approach differs from most of the existing ones in the literature and is easily amended for other discrete approximations; arithmetic and combinatorial examples for Bessel approximation are also presented. A unified approach is developed for deriving uniform estimates for probability generating functions of the number of components in general decomposable combinatorial structures, with or without analytic continuation outside their circles of convergence.

It has been conjectured that for any union-closed set there exists some element which is contained in at least half the sets in . It is shown that this conjecture is true if the number of sets in is less than 25. Several conditions on a counterexample are also obtained.

We define an arrangement of pseudohyperplanes as an image of a topological sphere arrangement with appropriate intersections, and prove that the complement components are then homologically trivial. We apply this to extend a formula of Winder and Zaslavsky.

A generalization of the definition of combinatorial species is given by considering functors whose domains are categories of finite sets, with various classes of relations as moronisms. Two cases in particular correspond to species for which one has notions of restriction and quotient of structures. Coalgebras and/or Hopf algebras can be associated to such species, the duals of which provide an algebraic framework for studying invariants of structures.

In this note we will study the following problem. For a given partition regular system of equations, which equations can be added to this system without introducing new variables, such that the new augmented system is again partition regular. It turns that the Hindman system on finite sums as well as the Deuber-Hindman system on finite sums of (m, p, c)-sets are maximal in this sense.