The original Specker–Blatter theorem (1983) was formulated for classes of structures $\mathcal {C}$ of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set $[n]$ is modularly C-finite (MC-finite). In previous work we extended this to structures definable in CMSOL, MSOL extended with modular counting quantifiers. The first author also showed that the Specker–Blatter theorem does not hold for one quaternary relation (2003).

If the vocabulary allows a constant symbol c, there are n possible interpretations on $[n]$ for c. We say that a constant c is hard-wired if c is always interpreted by the same element $j \in [n]$. In this paper we show:

1. (i) The Specker–Blatter theorem also holds for CMSOL when hard-wired constants are allowed. The proof method of Specker and Blatter does not work in this case.

2. (ii) The Specker–Blatter theorem does not hold already for $\mathcal {C}$ with one ternary relation definable in First Order Logic FOL. This was left open since 1983.

Using hard-wired constants allows us to show MC-finiteness of counting functions of various restricted partition functions which were not known to be MC-finite till now. Among them we have the restricted Bell numbers $B_{r,A}$, restricted Stirling numbers of the second kind $S_{r,A}$ or restricted Lah-numbers $L_{r,A}$. Here r is a non-negative integer and A is an ultimately periodic set of non-negative integers.

Let $X$ be a nonempty set and ${\mathcal{P}}(X)$ the power set of $X$. The aim of this paper is to identify the unital subrings of ${\mathcal{P}}(X)$ and to compute its cardinality when it is finite. It is proved that any topology $\unicode[STIX]{x1D70F}$ on $X$ such that $\unicode[STIX]{x1D70F}=\unicode[STIX]{x1D70F}^{c}$, where $\unicode[STIX]{x1D70F}^{c}=\{U^{c}\mid U\in \unicode[STIX]{x1D70F}\}$, is a unital subring of ${\mathcal{P}}(X)$. It is also shown that $X$ is finite if and only if any unital subring of ${\mathcal{P}}(X)$ is a topology $\unicode[STIX]{x1D70F}$ on $X$ such that $\unicode[STIX]{x1D70F}=\unicode[STIX]{x1D70F}^{c}$ if and only if the set of unital subrings of ${\mathcal{P}}(X)$ is finite. As a consequence, if $X$ is finite with cardinality $n\geq 2$, then the number of unital subrings of ${\mathcal{P}}(X)$ is equal to the $n$th Bell number and the supremum of the lengths of chains of unital subalgebras of ${\mathcal{P}}(X)$ is equal to $n-1$.

We study random composite structures considered up to symmetry that are sampled according to weights on the inner and outer structures. This model may be viewed as an unlabelled version of Gibbs partitions and encompasses multisets of weighted combinatorial objects. We describe a general setting characterized by the formation of a giant component. The collection of small fragments is shown to converge in total variation toward a limit object following a Pólya–Boltzmann distribution.

The $W$-operator, $W([n])$, generalises the cut-and-join operator. We prove that $W([n])$ can be written as the sum of $n!$ terms, each term corresponding uniquely to a permutation in $S_{\!n}$. We also prove that there is a correspondence between the terms of $W([n])$ with maximal degree and noncrossing partitions.

We consider sequences of the form $(a_{n}\unicode[STIX]{x1D6FC})_{n}$ mod 1, where $\unicode[STIX]{x1D6FC}\in [0,1]$ and where $(a_{n})_{n}$ is a strictly increasing sequence of positive integers. If the asymptotic distribution of the pair correlations of this sequence follows the Poissonian model for almost all $\unicode[STIX]{x1D6FC}$ in the sense of Lebesgue measure, we say that $(a_{n})_{n}$ has the metric pair correlation property. Recent research has revealed a connection between the metric theory of pair correlations of such sequences, and the additive energy of truncations of $(a_{n})_{n}$. Bloom, Chow, Gafni and Walker speculated that there might be a convergence/divergence criterion which fully characterizes the metric pair correlation property in terms of the additive energy, similar to Khintchine’s criterion in the metric theory of Diophantine approximation. In the present paper we give a negative answer to such speculations, by showing that such a criterion does not exist. To this end, we construct a sequence $(a_{n})_{n}$ having large additive energy which, however, maintains the metric pair correlation property.

We answer two questions of Hindman, Steprāns, and Strauss; namely, we prove that every strongly summable ultrafilter on an abelian group is sparse and has the trivial sums property. Moreover, we show that in most cases the sparseness of the given ultrafilter is a consequence of its being isomorphic to a union ultrafilter. However, this does not happen in all cases; we also construct (assuming Martin's Axiom for countable partial orders, i.e., $\operatorname{cov}\left( \text{M} \right)=\mathfrak{c})$, a strongly summable ultrafilter on the Boolean group that is not additively isomorphic to any union ultrafilter.

Let $\mathcal{A}$ be a line arrangement in the complex projective plane ${{\mathbb{P}}^{2}}$ and let $M$ be its complement. A rank one local system $\mathcal{L}$ on $M$ is admissible if, roughly speaking, the cohomology groups ${{H}^{m}}\left( M,\,\mathcal{L} \right)$ can be computed directly from the cohomology algebra ${{H}^{*}}\left( M,\,\mathbb{C} \right)$. In this work, we give a sufficient condition for the admissibility of all rank one local systems on $M$. As a result, we obtain some properties of the characteristic variety ${{\mathcal{V}}_{1}}\left( M \right)$ and the Resonance variety ${{\mathcal{R}}_{1}}\left( M \right)$.

The $q$-semicircular distribution is a probability law that interpolates between the Gaussian law and the semicircular law. There is a combinatorial interpretation of its moments in terms of matchings, where $q$ follows the number of crossings, whereas for the free cumulants one has to restrict the enumeration to connected matchings. The purpose of this article is to describe combinatorial properties of the classical cumulants. We show that like the free cumulants, they are obtained by an enumeration of connected matchings, the weight being now an evaluation of the Tutte polynomial of a so-called crossing graph. The case $q=0$ of these cumulants was studied by Lassalle using symmetric functions and hypergeometric series. We show that the underlying combinatorics is explained through the theory of heaps, which is Viennot's geometric interpretation of the Cartier–Foata monoid. This method also gives a general formula for the cumulants in terms of free cumulants.

We prove that a stochastic process of pure coagulation has at any time t ≥ 0 a time-dependent Gibbs distribution if and only if the rates ψ(i, j) of single coagulations are of the form ψ(i; j) = if(j) + jf(i), where f is an arbitrary nonnegative function on the set of positive integers. We also obtain a recurrence relation for weights of these Gibbs distributions that allow us to derive the general form of the solution and the explicit solutions in three particular cases of the function f. For the three corresponding models, we study the probability of coagulation into one giant cluster by time t > 0.

In this paper we derive congruences expressing Bell numbers and derangement numbers in terms of each other modulo any prime.

The partition monoid is a salient natural example of a *-regular semigroup. We find a Galois connection between elements of the partition monoid and binary relations, and use it to show that the partition monoid contains copies of the semigroup of transformations and the symmetric and dual-symmetric inverse semigroups on the underlying set. We characterize the divisibility preorders and the natural order on the (straight) partition monoid, using certain graphical structures associated with each element. This gives a simpler characterization of Green’s relations. We also derive a new interpretation of the natural order on the transformation semigroup. The results are also used to describe the ideal lattices of the straight and twisted partition monoids and the Brauer monoid.

We introduce a natural Hopf algebra structure on the space of noncommutative symmetric functions. The bases for this algebra are indexed by set partitions. We show that there exists a natural inclusion of the Hopf algebra of noncommutative symmetric functions in this larger space. We also consider this algebra as a subspace of noncommutative polynomials and use it to understand the structure of the spaces of harmonics and coinvariants with respect to this collection of noncommutative polynomials and conclude two analogues of Chevalley’s theorem in the noncommutative setting.

Non-singular toric embeddings with dual defect are classified. The associated polytopes, called defect polytopes, are proven to be the class of Delzant integral polytopes for which a combinatorial invariant vanishes. The structure of a defect polytope is described.

Let $n$ and $r$ be positive integers with $1\,{<}\,r\,{<}\,n$, and let $X_n\,{=}\break\{1,2,\ldots,n\}$. An $r$-set $A$ and a partition $\pi$ of $X_n$ are said to be orthogonal if every class of $\pi$ meets $A$ in exactly one element. We prove that if $A_{1},A_{2},\ldots, A_{\binom n r}$ is a list of the distinct $r$-sets of $X_ n$ with $|A_{i}\cap A_{i+1}|\,{=}\,r-1$ for $i=1,2,\ldots, \binom n r$ taken modulo $\binom n r$, then there exists a list of distinct partitions $\pi_{1},\pi_{2},\ldots, \pi_{\binom n r}$ such that $\pi_{i}$ is orthogonal to both $A_{i}$ and $A_{i+1}$. This result states that any constant weight Gray code admits a labeling by distinct orthogonal partitions. Using an algorithm from the literature on Gray codes, we provide a surprisingly efficient algorithm that on input $(n,r)$ outputs an orthogonally labeled constant weight Gray code. We also prove a two-fold Gray enumeration result, presenting an orthogonally labeled constant weight Gray code in which the partition labels form a cycle in the covering graph of the lattice of all partitions of $X_n$. This leads to a conjecture related to the Middle Levels Conjecture. Finally, we provide an application of our results to calculating minimal generating sets of idempotents for finite semigroups.