## co.combinatorics – Disappearing Pigeons – MathOverflow

Suppose you have a magic box that, at random points of time, randomly selects objects within it and makes them disappear. We can assume that before each disappearance the box chooses an object with uniform distribution across all remaining objects.

You put in $$x$$ pairs of pigeons (each with its mate) and after some time you open it to discover that $$y$$ pairs of pigeons are still there and $$z$$ single pigeons (with no mate) are still there.

Given $$y$$ and $$z$$, is it possible to calculate the expected value for $$x$$? In other words, given the number of whole pairs and single partners, what is the most likely number of starting pairs? Or equivalently, what is the likely number of lost whole pairs of pigeons.

## co.combinatorics – Is being simply connected very rare?

Essentially, my question is how strong a restriction it is to be simply connected.

Here is a way of making this precise: Let’s say we want to count simplicial complexes (of dimension 2, though that does not matter much, any fixed dimension is fine) on N simplices that are subject to the following restrictions:

A: every vertex is contained only in a bounded number of simplices (say, 10000).

B: the complex is simply connected.

So properly: How many distinct complexes like this are there? In fact, I only want a rough answer: is it exponential in N, or is it superexponential. Note that if I remove either restriction, the answer is superexponential.

## co.combinatorics – Number of 5×5 matrix permutations without repetitions in rows or columns

Context

In the boardgame Azul, your goal is to complete as much as possible of a $$5times5$$ board by placing 25 tiles of 5 different colours (5 tiles of each colour) so that no colour appears twice in a row or column. For the normal mode, the tiles must be placed following a predefined pattern, which can be seen here and that I represent with the following matrix $$P$$, where each letter represents a different colour:

$$P = begin{bmatrix}a & b & c & d & e\ e & a & b & c & d\ d & e & a & b & c \ c & d & e & a & b \ b & c & d & e & aend{bmatrix}$$

The advanced playing mode has no predefined pattern, so you can come up with your own, while respecting the constraint that no colour appears twice in each row or column.

I’ve realised that I can build valid patterns by permutating the rows and columns of the predefined pattern, as these operation preserve the number of different colours in each row or column. The resulting pattern $$P’$$ can be represented by $$R times P times C$$, where $$R$$ and $$C$$ are two permutation matrices indicating the rows and columns to permutate, respectively. For example:

$$P’ = begin{bmatrix} 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 1 & 0 \ 0 & 1 & 0 & 0 & 0end{bmatrix} times begin{bmatrix} a & b & c & d & e\ e & a & b & c & d\ d & e & a & b & c \ c & d & e & a & b \ b & c & d & e & aend{bmatrix} times begin{bmatrix} 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 1end{bmatrix} = begin{bmatrix} a & c & b & d & e\ d & a & e & b & c\ b & d & c & e & a\ c & e & d & a & b\ e & b & a & c & d\end{bmatrix}$$

Which is a valid pattern.

Since there are $$5!$$ permutation matrix, I have managed to create $$(5!)^2 = 14400$$ valid patterns this way, although each pattern appears 5 times, so only 2880 of them are distinct.

Questions

1. Is there a valid pattern that can’t be created by the permutation of
rows and columns of $$P$$?
Does the same answer hold true for matrices of higher order?

For patterns of order 3, I checked and all the valid patterns are permutations of rows and columns of $$P$$, but brute-forcing this doesn’t scale particularly well.

2. Given $$P$$ and $$P’$$, how can I find the permutations matrices $$C$$ and $$R$$ that transform $$P$$ into $$P’$$?

## co.combinatorics – Is there general theory of this type of problem?

Suppose we have a function $$f(x_1 ,x_2 ,x_3 ,x_4).$$ We know that we can factor it int two ways as $$f(x_1 ,x_2 ,x_3 ,x_4)=phi_1 (x_1 ,x_2 )phi_2(x_3 ,x_4 )=psi_1 (x_1,x_3)psi_2(x_2,x_4)$$

Show that we can completely factor the function as: $$f(x_1 ,x_2 ,x_3 ,x_4)=varphi_1(x_1)varphi_2(x_2)varphi_3(x_3)varphi_4(x_4).$$

I stumbled a little bit on this elementary problem as the proof is not as immediate as I think. But eventually I can prove this.

Here the overlap of partition {{1,2} {3,4}} and {{1,3},{2,4}} is {{1},{2},{3},{4}} and indeed satisfying the first two partition implies that we can factor by the overlap of both partitions.

I wonder if there is a general statement/theory of this.

## co.combinatorics – Is matroid realizability computable?

Contra my suspicions, the Internet is telling me that Vámos proved in “A necessary and sufficient condition for a matroid to be linear” (citation below) that it is decidable if a matroid is representable over a field. See quote on pg. 3 of Solving Rota’s Conjecture which says “The first exception is the algorithmic problem of determining when a given matroid is representable over an unspecified field, which was proved to be decidable by Vámos (28).”

Vamos, P., A necessary and sufficient condition for a matroid to be linear, Möbius Algebras, Conf. Proc. Waterloo 1971, 162-169 (1975). ZBL0374.05017.

## co.combinatorics – Does every finite poset have a rigid endomorphism?

Crossposted on Mathematics.

In this post, an order-preserving self-map of a poset $$X$$ will be called an endomorphism of $$X$$, and such an endomorphism $$f$$ will be called rigid if the only automorphism of $$X$$ which commutes with $$f$$ is the identity of $$X$$.

The question is in the title:

Does every finite poset have a rigid endomorphism?

Let us prove

Proposition 1. Every poset of cardinality at most $$9$$ has a rigid endomorphism.

Let $$X$$ be a finite poset and let
$$G=text{Aut}(X)$$
be its group of automorphisms. Say that a set theoretical map $$f:Xto X$$ is orbit preserving is $$f(A)$$ is a subset of $$A$$ for each orbit $$A$$ of $$G$$ in $$X$$.

It will be convenient to prove a slightly stronger version of Proposition 1:

Proposition 2. Every poset of cardinality at most $$9$$ has an orbit preserving rigid endomorphism.

The poset below has no orbit preserving rigid endomorphism: However any constant endomorphism is rigid.

The sequel is dedicated to the proof of Proposition 2.

Write
$$(Sigma(X))$$
for the statement “the poset $$X$$ has an orbit preserving rigid endomorphism”.

Note that $$(Sigma(X))$$ is obvious if the cardinality $$|X|$$ of $$X$$ is $$0,1$$ or $$2$$.

Remark 3. Let $$X$$ be a poset of cardinality $$le9$$. It suffices to prove $$(Sigma(X))$$ under the assumption that $$(Sigma(Y))$$ holds for all poset $$Y$$ of cardinality $$<|X|$$.

For any orbits $$A$$ and $$B$$ of $$G$$ in $$X$$ write
$$nu(A,B)$$
for the number of strict inequalities between elements of $$Acup B$$.

Remark 4. We have $$nu(A,A)=0$$, that is, distinct elements in the same orbit are incomparable. (Indeed, all elements of $$A$$ are maximal in $$A$$.) If $$a,a’in A$$ and $$b,b’in B$$, then the inequalities $$a and $$a’>b’$$ are incompatible. Moreover $$nu(A,B)$$ is a multiple of $$|A|$$ and of $$|B|$$ which cannot exceed $$|A||B|$$.

Let us explain why this technical notion of orbit preservation is introduced.

Lemma 5. Let $$A$$ be an orbit of $$G$$ in $$X$$ such that $$nu(A,B)in{0,|A||B|}$$ for all orbit $$B$$. Then any orbit preserving rigid endomorphism of the poset $$Y:=Xsetminus A$$ extends to an orbit preserving rigid endomorphism of $$X$$.

Proof. The proof is easy but we include it just to show where the orbit preservation assumption is used. Let $$f$$ be our rigid endomorphism of $$Y$$, and let $$g$$ be any set theoretical orbit preserving extension of $$f$$ to a self-map of $$X$$ which induces a rigid self-map $$g_A$$ of $$A$$. It is clear that the only automorphism of $$X$$ which commutes with $$g$$ is the identity, and it only remains to show that $$g$$ is an endomorphism. Let $$x,x’in X$$ satisfy $$x (the case $$x>x’$$ is similar and omitted). We must prove $$g(x)le g(x’)$$. Note that $$x$$ or $$x’$$ is in $$Y$$ (distinct elements in the same orbit are incomparable, see Remark 4). Say $$x$$ is in $$Y$$. If $$x’$$ is also in $$Y$$, the inequality $$g(x)le g(x’)$$ is clear, so that we can assume $$x’in A$$. Letting $$B$$ be the orbit of $$x$$, we have $$Bne A$$. Since $$f$$ is orbit preserving, $$g(x)=f(x)$$ is in $$B$$ (recall that $$x’$$ and $$g(x’)=f_A(x’)$$ are in $$A$$), and the inequality $$x implies by assumption $$g(x). $$square$$

Lemma 6. Let $$A$$ be an orbit of $$G$$ in $$X$$ whose cardinality is coprime to the cardinality of any other orbit, and let $$f$$ be an orbit preserving rigid endomorphism of the poset $$Y:=Xsetminus A$$. Then $$f$$ extends to an orbit preserving rigid endomorphism of $$X$$.

Proof. This follows from the previous lemma and Remark 4. $$square$$

We want to upgrade Remark 3 to

Remark 7. Let $$X$$ be a poset of cardinality $$le9$$. It suffices to prove $$(Sigma(X))$$ under the assumption that $$X$$ is connected and that $$(Sigma(Y))$$ holds for all poset $$Y$$ of cardinality $$<|X|$$.

This will follow from the next two lemmas.

For $$ninmathbb N$$ set $$(n):={1,2,ldots,n}$$, and regard the set $$(n)$$ as a discrete poset. A poset of the form $$Xtimes(n)$$ with $$X$$ connected will be called isotypic.

Lemma 8. Let $$X$$ be a connected poset. If $$X$$ has an orbit preserving rigid endomorphism, then so does $$Y:=Xtimes(n)$$.

Proof. Let $$f$$ be an orbit preserving rigid endomorphism of $$X$$, and define $$g:Yto Y$$ by
$$g(x,i)=begin{cases}(x,i+1),&i
We leave it to the reader to check that $$g$$ is an orbit preserving rigid endomorphism of $$Y$$. $$square$$

Lemma 9. Let $$X_1,ldots,X_n$$ be the isotypic components of the finite poset $$X$$, for $$1le ile n$$ let $$f_i$$ be an orbit preserving rigid endomorphism of $$X_i$$. Then the coproduct of the $$f_i$$ is an orbit preserving rigid endomorphism of $$X$$.

This is clear. $$square$$

Let
$$M(X)$$
be the undirected graph obtained from the Hasse diagram of $$X$$ by forgetting the direction of the edges. By Remark 4 this is a multipartite graph – Wikipedia entry – the parts being the $$G$$-orbits. Note that $$M(X)$$ is connected if and only if $$X$$ is. Also note that the part preserving endomorphisms of $$M(X)$$ coincide with the orbit preserving endomorphisms of $$X$$, and that such an endomorphism is invertible if and only if it is in $$G$$. Say that a part preserving endomorphism $$f$$ of $$M(X)$$ is rigid if the only element of $$G$$ commuting with $$f$$ is the neutral element. Hence the part preserving rigid endomorphisms of $$M(X)$$ coincide with the orbit preserving rigid endomorphisms of $$X$$.

Lemma 10. Assume that $$X$$ is connected, that $$G$$ has two distinct orbits $$A$$ and $$B$$ in $$X$$, that we have $$2=|A|le|B|$$, and that there are no other orbits. Then $$X$$ has an orbit preserving rigid endomorphism.

Proof. If $$|B|$$ is odd this follows from Lemma 6, so that we can assume that $$|B|$$ is even. We have $$nu(A,B)in{|B|,2|B|}$$. If $$nu(A,B)=|B|$$, the poset $$X$$ is not connected. If $$nu(A,B)=2|B|$$, the statement results from Lemma 5. $$square$$

Let us attach to a multipartite graph $$M$$ a graph
$$overline M$$
as follows: The vertices of $$overline M$$ are the parts of $$M$$ and two parts $$A$$ and $$B$$ form an edge of $$overline M$$ if and only if there are $$ain A,bin B$$ such that $$a$$ and $$b$$ form an edge of $$M$$.

Lemma 11. Let $$M$$ be a finite multipartite graph such that $$overline M$$ is a tree. Assume that for all edge $${A,B}$$ of $$overline M$$ and all $$ain A$$ there is an edge of $$M$$ of the form $${a,b}$$ with $$bin B$$. Then the natural morphism $$Mtooverline M$$ has a section, that is, there is a family
$$xinprod_{Ainoverline M}A$$
such that $${x_A,x_B}$$ is an edge of $$M$$ if and only if $${A,B}$$ is an edge of $$overline M$$.

Proof. Let us argue by induction on the number $$n$$ of parts. We can assume that $$nge2$$ and that the statement holds for $$n-1$$. Let $$A,Binoverline M$$ be such that $$B$$ is the only neighbour of $$A$$. In particular $$overline Msetminus{A}$$ is a tree with $$n-1$$ vertices, and there is a family
$$xinprod_{Cinoverline Msetminus{A}}C$$
such that $${x_C,x_D}$$ is an edge of $$M$$ if and only if $${C,D}$$ is an edge of $$overline Msetminus{A}$$. By assumption there is an $$x_Ain A$$ such that $${x_A,x_B}$$ is an edge of $$M$$. $$square$$

Lemma 12. In the above setting, assume that all the parts of $$M$$ have exactly two elements, and that $$overline M$$ is a tree. Then $$M$$ has a part preserving rigid endomorphism.

Proof. There is a family $$(x_A)_{Ainoverline M}$$ as in the statement of Lemma 11, for each $$A$$ there is a $$y_A$$ such that $$A={x_A,y_A}$$, and we can define $$f:Mto M$$ by $$x_Amapsto y_Amapsto y_A$$. $$square$$

Lemma 13. Assume that $$X$$ has exactly two orbits $$A$$ and $$B$$, that these orbits have the same cardinality $$nge2$$, and that each point of $$M(X)$$ is linked to $$n-1$$ points. Let $$f_A$$ be a rigid self-map of $$A$$. Then $$f_A$$ extends to an orbit preserving rigid endomorphism of $$X$$.

Proof. Set
$$A={a_1,ldots,a_n},quad B={b_1,ldots,b_n}.$$
We can assume that $$a_i if and only if $$ine j$$. Clearly $$G$$ is the symmetric group $$S_n$$, and the lemma will result from the following statement:

Given any self-map $$u$$ of $$(n):={1,ldots,n}$$ there is a self-map $$v$$ of $$(n)$$ such that $$ine j$$ implies $$v(i)ne u(j)$$.

Indeed, $$v(1)$$ must be different from $$u(2),u(3),ldots,u(n)$$, so that there are, for $$v(1)$$, at most $$n-1$$ prohibited values out of $$n$$ possible values, and similarly for $$v(2),v(3),ldots,v(n)$$. $$square$$

Lemma 14. Assume that $$G$$ has at most five orbits in $$X$$, and that each such orbit has cardinality two. Then $$X$$ has a rigid endomorphism.

Proof. Let $$E$$ be the set of all edges $${A,B}$$ of $$overline{M(X)}$$ such that $$nu(A,B)=4$$. Let $$overlineGamma$$ be the (undirected) graph obtained from $$overline{M(X)}$$ by removing the edges in $$E$$ (and keeping all the vertices). Similarly let $$Gamma$$ be the multipartite graph obtained from $$M(X)$$ by removing the edges of the form $${a,b}$$ with $$ain A$$, $$bin B$$, $${A,B}in E$$ (and keeping all the vertices).

If $$overlineGamma$$ is a disjoint union of trees, then, by Lemma 13, $$Gamma$$ has a part preserving rigid endomorphism, which is easily seen to be an orbit preserving rigid endomorphism of $$X$$.

Hence we can assume that $$overlineGamma$$ contains at least one cycle. This implies that the cardinality $$|X|$$ of $$X$$ is equal to $$8$$ or $$10$$. We can assume that $$X$$ is connected.

If $$|E|=0$$, then any constant endomorphism is rigid, so that we can assume now $$|E|ge1$$. Since a cycle has at least four vertices, this entails $$|X|=10$$.

Let us consider the case $$|E|=1$$. Set $$E={{A,B}}$$ with $$deg Aledeg B$$, where $$deg$$ denotes the degree in $$overlineGamma$$. Let $$ain A$$, $$bin B$$ and define $$f:Xto X$$ by
$$f(x)=begin{cases}a&text{if }xin A\ b&text{if }xnotin A.end{cases}$$
By looking carefully at Appendix B page 286 of the book

Finite ordered sets: concepts, results and uses by Caspard, Nathalie and Leclerc, Bruno and Monjardet, Bernard, 2012, Cambridge University Press, pdf link,

we see that $$f$$ is a rigid endomorphism of $$X$$.

The same appendix shows that the case $$|E|ge2$$ is incompatible with the assumption that $$overlineGamma$$ contains at least one cycle. This completes the proof. $$square$$

As an illustration, here are two cases with $$E={{A,B}}$$, represented by the Hasse diagram of $$overline X$$: Going back to the general setting where $$X$$ is a finite poset and $$G$$ is its automorphism group, if the $$p_i$$ with $$p_1lecdotsle p_k$$ are the cardinalities of the orbits of $$G$$ in $$X$$, then we say that
$$p_1+cdots+p_k$$
is the partition of $$|X|$$ attached to the poset $$X$$.

In view of the lemmas, it suffices to consider the following partitions:
$$2+2+4,quad4+4,quad3+3+3.$$

$$bullet$$ Partition 2+2+4

The graph $$overline{M(X)}$$ is of the form $$A-B-C$$.

Case 1: $$|A|=|B|=2,|C|=4$$. By Lemma 10 the sub-poset $$Bcup C$$ of $$X$$ has an orbit preserving rigid endomorphism $$f$$, and it is clear that $$f$$ extends to an orbit preserving rigid endomorphism of $$X$$.

Case 2: $$|B|=4$$. We have $$nu(A,B),nu(B,C)in{4,8}$$. If $$nu(B,C)=8$$, arguing as in Case 1 above, we can extend an orbit preserving rigid endomorphism of $$Acup B$$ to an orbit preserving rigid endomorphism of $$X$$. Hence it suffices to consider the case $$nu(A,B)=nu(B,C)=4$$. Write
$$A={a_1,a_2},quad B={b_1,b_2,b_3,b_4},quad C={c_1,c_2}.$$
We can assume that $$M(X)$$ contains the subgraphs $$b_1-a_1-b_2$$ and $$b_3-a_2-b_4$$. If we had $$b_1-c_1-b_2$$ and $$b_3-c_2-b_4$$, the poset $$X$$ would not be connected. Thus we have (perhaps after swapping $$c_1$$ and $$c_2$$) $$b_1-c_1-b_3$$ and $$b_2-c_2-b_4$$. Then it is not hard to check that
$$a_imapsto a_2,quad b_imapsto b_4,quad c_imapsto c_2$$
is an orbit preserving rigid endomorphism of $$X$$.

$$bullet$$ Partition 4+4

Assume that $$X$$ is connected (Remark 7) and say that each point of $$M(X)$$ is linked to $$d$$ points. Then $$d$$ is equal to $$2,3$$ or $$4$$. The cases $$d=3$$ and $$d=4$$ follow respectively from Lemmas 13 and 5. Consider the case $$d=2$$. Setting
$$A={a_1,ldots,a_4},quad B={b_1,ldots,b_4},$$
we can assume that the only strict inequalities are $$a_i if $$j-i$$ is congruent to $$0$$ or $$1$$ modulo $$4$$. Then
$$a_1mapsto a_2mapsto a_3leftrightarrow a_4,quad b_2mapsto b_3mapsto b_4mapsto b_4,quad b_1mapsto b_3$$
is an orbit preserving rigid endomorphism of $$X$$.

$$bullet$$ Partition 3+3+3

The graph $$overline{M(X)}$$ is of the form $$A-B-C$$. Set $$B={b_1,b_2,b_3}$$. Using Lemmas 5 and 13 we see that
$$b_1mapsto b_2mapsto b_3mapsto b_3$$
extends to an orbit preserving rigid endomorphism of $$X$$.

## co.combinatorics – Additional Examples of Classes of Networks whose Hasse diagram of the Poset is a Perfect Graph

This question is very important for my research, which is why I ask it here.
I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to correct me).

Suppose I have a directed acyclic network with a source node $$s$$ and a sink node $$t$$. Suppose I construct a corresponding partially ordered set as follows:

1. The elements of the partially ordered set are edges of the directed acyclic graph.
2. Elements are comparable in the sense that two elements are comparable if there is an $$s-t$$ path between the two edges in the network. For example, $$1 preceq 2 preceq 3$$ means that there is an $$s-t$$ path consisting of edges $$e_{1}$$,$$e_{2}$$, $$e_3$$ in that order.
3. Thus, the maximal chains of the partially ordered set are the $$s-t$$ paths of the directed acyclic network.

Consider the Hasse diagram of the partially ordered set described above. Although, a Hasse diagram is technically a diagram not an undirected graph, we consider it as an undirected graph.

My Question then is: For what general classes or types of networks or directed acyclic graphs (the directed version is acyclic) is the corresponding Hasse diagram, associated with the partially ordered set, a perfect graph?

Recall, a graph is a perfect, by the Strong Perfect Graph Theorem, if is neither is not contains an induced odd cycle or antihole of length $$5$$ or more.

I believe, that series-parallel networks are one type of network which fit the above description. That is, the Hasse diagram is perfect of such networks.

I believe this is the case because there is no fence or zig-zag in the Hasse diagram corresponding to the poset associated with Series-Parallel networks (or at least there is some relation there).
See:https://en.wikipedia.org/wiki/Fence_(mathematics).

Interestingly, as wikipedia describes, a partially ordered set is series-parallel if and only if it does not have four elements forming a fence. Perhaps, the reason then the Hasse diagram is perfect is because it has no induced $$P_4$$. (I think there is a relation between “fence” in the poset and no induced $$P_{4}$$ of the corresponding Hasse diagram).

These are just some thoughts, I am not completely sure if what I have said is correct.

Of course, a graph can be perfect even if it has an induced $$P_4$$ (although if it does not have an induced $$P_4$$ then it is perfect).

My question then remains, what is another example of directed acyclic graphs, or networks, besides series-parallel, where the corresponding Hasse diagram of the poset is a perfect graph?

I feel that there should exist another class of such graphs but I have been unable to find one after a long time scouring the internet. Since I am not a researcher in graph theory, it has been really tough for me to find such a class of dag’s or networks.

If another class of directed acyclic graph or networks does not exist, does there exist an example of a class of directed cyclic graph with the above properties?

Note, in the above questions, I am looking for classes of graphs, not a particular instance.

This question is very crucial for my research and I really appreciate any thoughts, guidance, or just anything at all that could at least point me in the right direction as I have been stuck for quite some time.
thanks.

## co.combinatorics – Transversals and almost transversals of a finite family of sets

The following is a purely combinatorial problem that I came across in the course of research in non-classical logic. It sounds to me like the kind of question that someone may very well have considered at some point, but not being a very combinatorially minded person myself, I have not managed to find it in the literature. Both a positive and a negative answer to the question below, or pointers to some relevant literature, would be of interest to me. For all I know, this may be a piece of cake to a combinatorialist. I should say that I have no particular reason to suspect that the answer should be positive (although I secretly hope against hope that it might be).

Consider a family of disjoint sets $$S_1, dots, S_l$$ where each $$S_i$$ has cardinality at most $$n$$. A transversal is a set $$T$$ which contains exactly one element from each of these sets (and nothing else). An $$i$$-transversal is a set $$T_i$$ which contains exactly one element from each of these sets except for the set $$S_i$$ (and nothing else). In particular, transversals have exactly $$l$$ elements, while $$i$$-transversals have exactly $$l-1$$ elements. An almost tranversal family is an $$n$$-tuple $$(T_1, dots, T_n)$$ such that each of these sets $$T_i$$ is an $$i$$-transversal. A transversal $$T$$ lies $$m$$-locally in this family if each subset of $$T$$ of cardinality $$m$$ is a subset of some $$T_i$$.

Question. Given $$n geq 2$$ and $$m geq 2$$, is it the case that for each such family of disjoint sets $$S_1, dots, S_l$$ with large enough $$l$$ and each almost transversal family $$(T_1, dots, T_l)$$ over these sets one can find a transversal $$T$$ which lies $$m$$-locally in $$(T_1, dots, T_l)$$?

Already the case of $$n = m = 2$$ would be of interest to me. In that case a transversal corresponds to a binary string of length $$l$$ and an almost tranversal family corresponds to an $$l$$-tuple of binary strings of length $$l-1$$. More suggestively, an almost tranversal family corresponds to an $$l$$-tuple of strings $$T_i$$ of length $$l$$ where all the symbols of $$T_i$$ except for the $$i$$-th symbol are 0 or 1, for example $$({*}1100, 0{*}110, 10{*}10, 110{*}1, 1010{*})$$. The transversal $$10100$$ then lies $$2$$-locally in this almost transversal family: whenever we pick any pair of positions in $$10100$$, there is an almost tranversal in our family which agrees with $$10100$$ on these two positions. For small values of $$l$$ one can certainly find almost transversal families which have no $$2$$-local transversal, but it is less than clear to me whether counter-examples of arbitrarily high length exist.

## co.combinatorics – Cardinality of a class of posets under certain restrictions

In causal set theory, the Benincasa-Dowker action for a poset $$P$$ is defined as:
$$begin{equation} frac{1}{hbar}mathcal{S}(P) = mu Big(n + sum_{j = 0}^{j_{max}} lambda_{j}N_{j}Big) end{equation}$$
where $$mu$$ and $$lambda_i$$ are some fixed parameters, $$n$$ is the set size, and $$N_j$$ is the number of pairs of elements $${x, y} subset P$$ such that
$$begin{equation} j = left| {z in P: x prec z prec y } right|. end{equation}$$
We write $$x prec z prec y$$ to denote that $$y$$ covers $$z$$, and $$z$$ covers $$x$$.

Question: Given the values of $$N_j$$ for $$j = 0, 1, 2, 3$$, what is the cardinality of the class $$mathcal{P}$$ of posets $$P$$ over which $$mathcal{S}(P)$$ is constant?

As we have worked out here, this problem is easy to tackle when we ignore $$N_1$$, $$N_2$$ and $$N_3$$. Bring $$N_1$$ into the picture and the combinatorics gets very difficult.

Perhaps a simpler case would be to look at only three-level posets, where we borrow the definition of a level from the 1975 work of Kleitman and Rothschild.

The level $$L_i$$ of an order $$P$$, with $$i = 1, 2, 3, ldots k$$, is
the set of minimal elements that remain after deleting all elements in
levels $$L_m$$, $$m < i$$. In particular, $$L_1$$ contains all the minimal
elements of $$P$$.

Are there any known results/techniques that could help with the kind of counting stated in the question above, in particular for three-level posets?

## co.combinatorics – An averaging game on finite multisets of integers

The following procedure is a variant of one suggested by
Patrek Ragnarsson (age 10). Let $$M$$ be a finite multiset of
integers. A move consists of choosing two elements
$$a,b$$ of $$M$$ of the same parity and replacing them with the
pair $$frac 12(a+b)$$, $$frac 12(a+b)$$. If we continue to
make moves whenever possible, the procedure must eventually
terminate since the sum of the squares of the elements will
decrease at each move. What is the least and the most number
of moves to termination, in particular, if $$M={1,2,dots, n}$$? If $$M={a_1,dots,a_n}$$, then an upper bound on on
the maximum number of moves is $$frac 12sum (a_i-k)^2$$,
where $$k$$ is the integer which minimizes this sum. (In fact,
$$k$$ is the nearest integer to $$frac 1n(a_1+cdots+a_n)$$.)

We can turn this procedure into a game by having Alice and
Bob move alternately, with Alice moving first. The last
player to move wins. (We could also consider the misère
version, where the last player to move loses.) Which
multisets are winning for Alice, especially
$$M={1,2,dots,n}$$? The game is impartial, so it has a
Sprague-Grundy number. However, it doesn’t seem to be useful
for analyzing the game since a position $$M$$ never breaks up
into a disjoint union (or sum) of smaller independent
positions. Nevertheless we can ask for the Sprague-Grundy
number of a position $$M$$.