1 Introduction↩︎

1.1 Background↩︎

The motivation of this work comes from an unexpected interaction between several combinatorial structures arising in different areas of mathematics. In our previous work [1], we established a correspondence between MAT-labeled graphs, which originate in the theory of hyperplane arrangements, and locally regular vines, which appear in probability theory. In the present paper we show that this connection extends further and naturally relates to single-peaked domains in social choice theory.

The first main concept in this paper is the notion of MAT-labeled graphs.

The study of MAT-labelings originates from a question of Cuntz–Mücksch [3] concerning free hyperplane arrangements. A hyperplane arrangement is a finite collection of linear hyperplanes in a vector space. Such an arrangement is called free if its module of logarithmic derivations is free [4], [5]. Freeness has been a central topic in the theory of hyperplane arrangements for several decades, and a major direction in the area is to understand this algebraic property through combinatorial structures associated with the arrangement.

One important notion in this direction is MAT-freeness, introduced by Abe–Barakat–Cuntz–Hoge–Terao [6]. An arrangement is called MAT-free if its hyperplanes admit an MAT-partition, namely a partition satisfying certain combinatorial conditions. MAT-freeness implies freeness and played a crucial role in the proof of the Sommers–Tymoczko conjecture [7] on the freeness of ideal subarrangements of Weyl arrangements.

Intuitively, an MAT-partition organizes the hyperplanes into layers. On the other hand, the motivating examples coming from root systems also carry a natural partial order given by the root poset. This leads naturally to the question of whether MAT-partitions can be described through a suitable poset structure extending the classical root poset. Such a question was posed by Cuntz–Mücksch [3] and motivated our earlier work [1], where we answered this question for graphic arrangements.

Subarrangements of a type \(A\) Weyl arrangement are in one-to-one correspondence with graphic arrangements, and their MAT-partitions correspond precisely to MAT-labelings of the underlying graphs. It is well known that a graphic arrangement is free if and only if the underlying graph is chordal (e.g., [8]). Consequently, every graph admitting an MAT-labeling must be chordal. Moreover, it was shown in [2] that a graph admits an MAT-labeling if and only if it is strongly chordal. Thus, although MAT-freeness originated in the theory of hyperplane arrangements, MAT-labelings also arise naturally as a graph-theoretic property.

The second structure appearing in this story is that of regular vines.

The nested incidence relations among the vertices and edges of a regular vine naturally define a poset structure. This leads to an equivalent poset description of regular vines, which will be used throughout the paper.

In [1] we proved that the categories of MAT-labeled graphs and locally regular vines are equivalent. In particular, MAT-labeled complete graphs correspond exactly to regular vines. This result provides a positive answer to the question of Cuntz–Mücksch in the special case of graphic arrangements.

Regular vines were originally introduced in probability theory as models for describing dependence structures in multivariate distributions. They have since become an important tool in probability, uncertainty analysis, and related fields. For a comprehensive account of vine models and their applications, we refer the reader to [11].

A key observation behind the correspondence established in [1] was that the numbers of non-isomorphic MAT-labeled complete graphs with \(n\) vertices and of non-isomorphic regular vines on \(n\) elements coincide for \(n\le 8\). Such numerical coincidences frequently hint at deeper structural relationships, and in this case it ultimately led to the equivalence between the two objects.

In the present work, the same sequence also arises in the enumeration of non-isomorphic maximal Arrow’s single-peaked domains [12]. This suggests that these structures may admit a common combinatorial framework.

We now recall the notion of Arrow’s single-peaked domains. Let \(A\) be a finite set with \(n\) elements (the alternatives) and let \(\mathcal{L}(A)\) denote the set of linear orders (the preferences) on \(A\). For \(\mathcal{D} \subseteq \mathcal{L}(A)\) and \(T \subseteq A\), let \(\mathcal{D}_{T}\) denote the set of linear orders on \(T\) obtained by restricting the linear orders in \(\mathcal{D}\) to \(T\).

Given a collection of voters, each with a preference on \(A\), the majority relation declares that \(x\) is socially preferred to \(y\) whenever a strict majority of voters rank \(x\) above \(y\). When the number of voters is odd, this relation is well defined but may fail to be transitive, a phenomenon known as the Condorcet paradox.

A domain \(\mathcal{D} \subseteq \mathcal{L}(A)\) is called a Condorcet domain if for every odd preference profile whose preferences lie in \(\mathcal{D}\), the induced majority relation is always a linear order, thereby avoiding the Condorcet paradox. In this case the majority rule always admits a Condorcet winner, an alternative that defeats every other alternative in pairwise majority comparisons.

Condorcet domains are classical objects in social choice theory, tracing back to the work of Borda and Condorcet in the late 18th century. Understanding their structure is a major problem in the theory and remains largely open. Among the known examples, ASPDs form one of the largest and most tractable families, and maximal ASPDs provide important extremal instances within this class.

Several combinatorial frameworks for maximal ASPDs have been proposed in the literature. For instance, Liversidge [15] described them using Hamiltonian directed paths, Karpov–Slinko [16] introduced the concatenation and shuffle construction, and Slinko [17] developed an approach based on generalized arrangements of pseudolines. Recently, Karpov [12] gave a characterization and enumeration of maximal ASPDs via binary matrices.

1.2 Main results↩︎

This paper uncovers a common structure underlying three combinatorial objects that arise in different areas: maximal ASPDs, MAT-labeled complete graphs, and regular vines. Despite their different definitions and origins in social choice theory, hyperplane arrangements, and probability theory, we show that these objects admit the same recursive description.

Our approach is to view each of these structures as a combinatorial species and to identify two fundamental operations, called splitting and merging, that govern their recursive construction. The splitting operation leads to a natural proximity condition, while merging gives rise to a corresponding mergeability condition (Definition 14). We prove that these two axioms uniquely determine the structure, yielding an axiomatic characterization that applies uniformly to all three families. This is the central result of the paper and is stated in Theorem 12.

The framework has two main advantages. First, it explains why these objects share similar structural and enumerative properties. Second, it provides a systematic viewpoint for relating and analyzing further examples arising in different areas. In particular, we will see in the applications that extremal lattices from formal concept analysis and extremal binary matrices from combinatorial matrix theory also fit naturally into this framework.

As a consequence of Theorem 12, isomorphisms between these structures can be constructed inductively from the splitting and merging operations. In Theorems 14 and 15 we give explicit constructions of these isomorphisms, relating maximal ASPDs to MAT-labeled complete graphs and to regular vines, respectively. These constructions make the correspondences transparent and allow structural properties to be translated between the different settings.

1.3 Applications↩︎

Our results lead to two main lines of applications.

The first concerns social choice theory. The axiomatic characterization of maximal ASPDs, together with the explicit correspondences with MAT-labeled complete graphs and regular vines, provides two concrete combinatorial models for maximal ASPDs—one graph-theoretic and one poset-theoretic. The representation via regular vines also yields an explicit formula for the number of non-isomorphic maximal ASPDs (Corollary 3).

The correspondence with regular vines further yields several applications in social choice theory, which are developed in Section 5. First, maximal Black’s single-peaked domains correspond precisely to D-vines. Second, the distribution of first-ranked alternatives in a maximal ASPD can be computed via maximal chains of the corresponding regular vine, leading to a rule analogous to Pascal’s triangle. Third, we obtain a characterization of the richness property in terms of the combinatorial structure of regular vines.

The second line of applications illustrates the broader scope of our axiomatic framework. Using a direct combinatorial proof (Theorem 22), we show that regular vines are equivalent to \((n,3)\)-extremal lattices arising in formal concept analysis, a field that studies data through object–attribute relationships. We further show (Proposition 24) that these extremal lattices are equivalent to extremal binary matrices with no triangles from combinatorial matrix theory. This equivalence recovers the characterization of maximal ASPDs via binary matrices recently obtained by Karpov [12]. Consequently, both the extremal lattices and the extremal binary matrices admit the same splitting-and-merging structure and therefore fit naturally into our framework.

Furthermore, a recursive formula for the number of non-isomorphic \((n,3)\)-extremal lattices is already known. Via the correspondence established here, this immediately yields a recursive formula for the number of non-isomorphic regular vines, MAT-labeled complete graphs, and maximal ASPDs (Corollary 6).

We summarize the relationships between the main structures and the resulting applications in Figure 4.

Acknowledgements. The authors thank A. V. Karpov for informing us, after the first draft of this paper appeared, of his work [12] on the characterization of maximal ASPDs via extremal binary matrices with no triangles. This led us to observe the equivalence between \((n,3)\)-extremal lattices and extremal binary matrices with no triangles established in Proposition 24. S. Tsujie was supported by JSPS KAKENHI Grant Numbers JP23H00081 and JP26K16955.

2 Preliminaries↩︎

2.1 MAT-labeled graphs↩︎

In this subsection, we recall several basic properties of MAT-labeled graphs that will be used later. All graphs in this paper are finite, undirected, and simple. Let \(G=(A,E)\) be a graph and let \(\lambda \colon E \longrightarrow \mathbb{Z}_{>0}\) be an edge-labeling. For simplicity of notation, we write \[\lambda(a,b)\mathrel{\vcenter{:}}=\lambda(\{a,b\})\] for the label of an edge \(\{a,b\}\in E\).

Let \(K_A\) denote the complete graph on vertex set \(A\). In this paper, we will be particularly interested in MAT-labeled complete graphs. We recall two structural properties that will play a central role in our framework.

2.2 Regular vines↩︎

We recall several structural properties of regular vines established in [1].

The following are two structural properties of regular vines closely paralleling the splitting and merging properties of MAT-labeled complete graphs.

When we consider merging regular vines, the following observation will be useful.

Now we define two important families of regular vines.

D-vines and C-vines can be regarded as the extreme cases of regular vines.

D-vines can also be characterized by the existence of certain maximal chains.

2.3 Maximal Arrow’s single-peaked domains↩︎

We begin this section by recalling the definitions of Condorcet and single-peaked domains together with some of their basic properties. Our presentation is slightly different from, but equivalent to, the one given in the introduction (see, e.g., [20]).

Let \(A\) be a finite set of \(n\) elements, called alternatives (or candidates), and let \(\mathcal{L}(A)\) denote the set of all bijections from \([n] \mathrel{\vcenter{:}}= \{1, \dots, n\}\) onto \(A\). Each \(\omega \in \mathcal{L}(A)\) naturally induces a linear order \(>_{\omega}\) on \(A\), defined by \[\omega(1) >_{\omega} \omega(2) >_{\omega} \cdots >_{\omega} \omega(n).\] An element of \(\mathcal{L}(A)\) is called a preference. We will write a preference \(\omega \in \mathcal{L}(A)\) by juxtaposition \[\omega = \omega(1)\omega(2)\cdots\omega(n).\] In particular, \(\omega(1)\) and \(\omega(n)\) represent the first-ranked and last-ranked alternatives, respectively.

A subset \(\mathcal{D} \subseteq \mathcal{L}(A)\) is called a domain of preferences.

Characterizing Condorcet domains is a challenging problem and remains open in general. Several important subclasses of Condorcet domains are known.

An ASPD is sometimes referred to as a locally BSPD. An alternative is called a bottom alternative of a domain if it is ranked last in at least one preference in the domain. The following proposition gives a convenient characterization of ASPDs.

It is easy to see that every subset of an ASPD (resp.  BSPD, Condorcet domain) is also an ASPD (resp.  BSPD, Condorcet domain). Thus it is natural to ask when such domains are maximal. From a voting-theoretic perspective, larger domains allow voters greater freedom in expressing their preferences.

Maximal BSPDs can be characterized as follows.

None

The following lemma shows that maximal ASPDs admit a recursive structure.

We now establish another important structural property of maximal ASPDs.

3 Axiomatic framework from splitting and merging of species↩︎

We briefly recall the notion of a combinatorial species; see [24] for background. A (combinatorial) species is a functor from the category of finite sets and bijections to itself. More precisely, a species \(\mathsf{F}\) assigns to each finite set \(A\) (the set of labels) a finite set \(\mathsf{F}[A]\) (the \(\mathsf{F}\)-structures on \(A\)), and to each bijection \(h\colon A\longrightarrow B\) a transport map (relabeling) \[\mathsf{F}[h]\colon \mathsf{F}[A]\longrightarrow\mathsf{F}[B].\] These maps satisfy the functoriality conditions \[\mathsf{F}[\mathrm{id}_A]=\mathrm{id}_{\mathsf{F}[A]}, \qquad \mathsf{F}[g\circ h]=\mathsf{F}[g]\circ\mathsf{F}[h]\] for all bijections \(h \colon A\longrightarrow B\) and \(g\colon B\longrightarrow C\).

A natural transformation \(\eta \colon \mathsf{F}\longrightarrow\mathsf{G}\) between species consists of component maps \(\eta_A\colon \mathsf{F}[A]\longrightarrow\mathsf{G}[A]\) for all finite sets \(A\) satisfying the naturality condition. That is, for every bijection \(h\colon A\longrightarrow B\) the diagram \[\begin{tikzcd} \mathsf{F}[A] \ar[r,"{\mathsf{F}[h]}"] \ar[d,"\eta_A"'] & \mathsf{F}[B] \ar[d,"\eta_B"]\\ \mathsf{G}[A] \ar[r,"{\mathsf{G}[h]}"] & \mathsf{G}[B] \end{tikzcd}\] commutes. A natural transformation whose components are bijections is called a natural isomorphism.

As we saw in Section 2, MAT-labeled complete graphs, regular vines, and maximal ASPDs admit similar splitting and merging structures. In this section, we formulate these operations axiomatically in the language of combinatorial species. We first fix some notation that will be used throughout this section. Let \(A\) be a finite set. If \(a_1,a_2 \in A\) are distinct elements, define \[A_i \mathrel{\vcenter{:}}= A\setminus\{a_i\} \quad (i=1,2), \qquad A' \mathrel{\vcenter{:}}= A\setminus\{a_1,a_2\}.\]

We now introduce two properties of the species \(\mathop{\mathrm{\mathsf{Sp}}}^{\mathsf{F}}\), which will play a central role in our constructions.

The following theorem, which is the main result of this paper, provides an axiomatic characterization of species whose splittings satisfy the proximity and mergeability properties.

We conclude this section with two important corollaries of Theorem 12. Since the species of MAT-labeled complete graphs \(\mathop{\mathrm{\mathscr{G}}}\) (Example 9), regular vines \(\mathop{\mathrm{\mathscr{V}}}\) (Example 10), and maximal ASPDs \(\mathop{\mathrm{\mathscr{D}}}\) (Example 11) admit splittings satisfying the proximity and mergeability properties, we obtain the following.

In [25] and [26], explicit formulas are given for the numbers of regular vines and their isomorphism classes. Hence, we obtain the following.

We note that related enumeration formulas for maximal ASPDs were also obtained independently by Karpov [12] using a different approach based on binary matrices. The values of \(\tilde{f}_n\) for \(1 \le n \le 12\) are listed below: \[\begin{align} 1,1,1, 2, 6, 40, 560, 17024, 1066496, 135307264, 34496249856, 17626824704000. \end{align}\] A recursive formula for \(\tilde{f}_n\) will be given in Corollary 6.

4 Explicit constructions of the correspondences↩︎

By Theorem 12, we can construct, in an inductive manner, isomorphisms between any two of the species \(\mathop{\mathrm{\mathscr{G}}}, \mathop{\mathrm{\mathscr{V}}}, \mathop{\mathrm{\mathscr{D}}}\). The strength of the theorem lies in the fact that these natural isomorphisms always exist and are unique. In this section, we provide explicit descriptions of these isomorphisms. These constructions make the correspondences more transparent and allow one to translate structural properties between the different settings.

It is worth noting that the structures \(\mathop{\mathrm{\mathscr{G}}}, \mathop{\mathrm{\mathscr{V}}}, \mathop{\mathrm{\mathscr{D}}}\) arise from distinct areas and are defined in quite different ways. Thus, constructing correspondences between them directly would be nontrivial. However, as will be seen in the proofs of Theorems 13, 14 and 15, the recursive structure provided by splitting and merging, together with Theorem 12, reduces the problem to verifying that the maps are well defined and that the relevant diagrams commute.

We continue to use the notation introduced in the previous section. Let \(\sigma^{\mathsf{F}}\colon \mathsf{F}\longrightarrow\mathop{\mathrm{\mathsf{Sp}}}^{\mathsf{F}}\) be a splitting and let \(A\) be a finite set. If \[\sigma^{\mathsf{F}}_{A}(\ell) = \{\ell_{1}, \ell_{2}\},\] denote by \(A_{i} = A\setminus\{a_{i}\}\) the subset of \(A\) such that \(\ell_{i} \in \mathsf{F}[A_{i}]\) for \(i \in \{1,2\}\), and let \(A^{\prime}= A\setminus\{a_{1},a_{2}\}.\)

4.1 MAT-labelings and regular vines↩︎

It was proved in [1] that the categories of MAT-labeled graphs and locally regular vines are equivalent. Consequently, the species \(\mathop{\mathrm{\mathscr{G}}}\) and \(\mathop{\mathrm{\mathscr{V}}}\) are isomorphic. We recall below an explicit isomorphism between these species.

Let \(\lambda \in \mathop{\mathrm{\mathscr{G}}}[A]\) and let \(e = \{a,b\} \in \pi_{k}\). By Condition 1([definition32MAT-labeling32triangle]), the edge \(e\) forms exactly \(k-1\) triangles with vertices \(c_{1}, \dots, c_{k-1}\) whose labels are less than \(k\). The set \[C_{e} \mathrel{\vcenter{:}}= \{a,b,c_{1}, \dots, c_{k-1}\}\] is called the principal clique generated by \(e\). Define \(\xi \colon \mathop{\mathrm{\mathscr{G}}}\longrightarrow \mathop{\mathrm{\mathscr{V}}}\) by \[\begin{align} \xi_{A}(\lambda) \mathrel{\vcenter{:}}= \Set{\{a\} \mid a \in A} \cup \Set{C_{e} \mid e \in E_{K_{A}}} \subseteq 2^{A}. \end{align}\] See [1] for a proof that \(\xi_{A}(\lambda)\) is a regular vine.

Define \(\eta \colon \mathop{\mathrm{\mathscr{V}}}\longrightarrow \mathop{\mathrm{\mathscr{G}}}\) by \[\begin{align} \eta_{A}(\mathcal{V})(a,b) \mathrel{\vcenter{:}}= \mathop{\mathrm{rank}}(\{a\}\vee \{b\}) -1. \end{align}\] See [1] for a proof that \(\eta_{A}(\mathcal{V})\) is an MAT-labeling of \(K_{A}\).

It was shown in [1] by a direct proof that \(\xi\) and \(\eta\) are natural isomorphisms and inverses of each other. Here, we give an alternative proof using Theorem 12.

4.2 Maximal ASPDs and MAT-labelings↩︎

Let \(\mathcal{D}\) be a domain of preferences on a finite set \(A\). Two distinct elements \(a,b \in A\) are called contiguous in \(\mathcal{D}\) if there exists \(\omega \in \mathcal{D}\) such that \(\{a,b\} = \{\omega(i), \omega(i+1)\}\) for some \(1 \le i \le n-1\).

Recall the notion of an MAT-perfect elimination ordering (MAT-PEO) of an MAT-labeled graph from Definition 6.

4.3 Maximal ASPDs and regular vines↩︎

The following is an immediate consequence of Theorem 15.

5 Applications to social choice theory↩︎

Theorem 12 characterizes maximal ASPDs through two structural axioms. Combined with the correspondences established in Theorems 14 and 15, this characterization yields concrete combinatorial representations of maximal ASPDs via MAT-labeled complete graphs and regular vines. In particular, the representation by regular vines naturally leads to an explicit formula for the number of non-isomorphic maximal ASPDs (Corollary 3).

These results provide our main applications to social choice. In this section we present three further consequences obtained from the correspondence with regular vines in Theorem 15.

Throughout this section, let \(\mathcal{D}\) be a maximal ASPD on a finite set \(A\), and let \(\mathcal{V}\) denote the regular vine corresponding to \(\mathcal{D}\) under the isomorphism \(\eta\) in Theorem 15.

5.1 Maximal BSPDs and D-vines↩︎

We show that maximal BSPDs correspond to D-vines under the isomorphism in Theorem 15, thereby giving a poset characterization of these domains. This correspondence further illustrates the close alignment between the theory of single-peaked domains and that of regular vines.

5.2 First-rank distribution↩︎

It was shown in [22] that any maximal ASPD is minimally rich, meaning that every alternative appears as the first-ranked alternative in at least one preference in the domain. We refine this result by giving a formula for the number of times each alternative is first-ranked.

For a domain \(\mathcal{D}\) on a set \(A\), define the first-rank distribution \(\operatorname{first}(\mathcal{D})\) to be the multiset \[\operatorname{first}(\mathcal{D}) = \Set{t_a | a \in A}, \quad \text{where } t_a \mathrel{\vcenter{:}}= \lvert\Set{\omega \in \mathcal{D} | \omega(1) = a }\rvert.\] As a consequence of Corollary 4, we obtain the following.

The number of maximal chains in a regular vine can be computed via a rule analogous to Pascal’s triangle. In particular, the first-rank distributions corresponding to D-vines and C-vines are given by binomial coefficients and powers of \(2\), respectively, which can be verified by induction on the number of alternatives.

5.3 Richness↩︎

In this subsection, we discuss another application of Theorem 15, concerning a generalization of minimal richness.

A domain \(\mathcal{D}\) on a set \(A\) is \(k\)-rich if for every \(j \le k\) and \(a \in A\), there exists \(\omega \in \mathcal{D}\) such that \(\omega(j) = a\). We say that \(\mathcal{D}\) has richness \(k\) if it is \(k\)-rich but not \((k+1)\)-rich, and denote the richness by \(\operatorname{rich}({\mathcal{D}})\).

The notion of richness has several interpretations in social choice theory; see [28] for details. Maximal ASPDs with minimal richness were classified in [28]. It was posed in [28] to find a structural characterization of maximal richness. We provide such a characterization for all possible richness values in Theorem 19, thereby resolving the problem for maximal richness.

The following is an immediate consequence of Theorems 18 and 19.

By definition, all associated trees of a C-vine are star graphs; hence C-vines have minimal richness \(2\). On the other hand, by the description of D-vines in Remark 4, one verifies that the Condition  5(2) holds, so D-vines attain the maximal richness \(\lfloor n/2 \rfloor + 1\). This further illustrates the strong correspondence between vine structures and single-peaked domains, with C-vines and D-vines representing the two extreme cases.

6 Extremal lattices↩︎

6.1 Extremal lattices and regular vines↩︎

In this subsection, we discuss a class of lattices arising in formal concept analysis (FCA). We prove directly that these lattices are essentially the same as regular vines.

A lattice is a poset in which every pair of elements has a join and a meet. An element in a poset is called join-irreducible if \(a = b \vee c\) implies \(a=b\) or \(a=c\) for any non-minimal element \(a\). An atom in a lattice is an element that covers the minimal element. Every atom is join-irreducible. Let \(B(k)=(2^{[k]}, \subseteq)\) denote the Boolean lattice on \([k]=\{1,\ldots,k\}\). We say that a lattice \(\mathcal{P}\) is \(B(k)\)-free if it does not contain an induced subposet isomorphic to \(B(k)\).

By [29], any lattice satisfying conditions (1) and (2) has at most \(\sum_{i=0}^{k-1} \binom{n}{i}\) elements. Thus, condition (3) means that \(\mathcal{P}\) attains the maximum possible size under these constraints, which justifies the term extremal.

Extremal lattices arise naturally in FCA, which studies the structure of data through object–attribute relationships. We briefly recall the necessary definitions.

A formal context is a triple \(\mathfrak{C} = (G, M, I)\) consisting of a set of objects \(G\), a set of attributes \(M\), and an incidence relation \(I \subseteq G \times M\), where \((g,m) \in I\) indicates that the object \(g\) has the attribute \(m\). For a subset \(A \subseteq G\), define \[A^I \mathrel{\vcenter{:}}= \Set{ m \in M | (g,m) \in I \text{ for all } g \in A },\] and for \(B \subseteq M\), define \[B^I \mathrel{\vcenter{:}}= \Set{ g \in G | (g,m) \in I \text{ for all } m \in B }.\]

A pair \((A,B)\) is called a formal concept if \(A^I = B\) and \(B^I = A\). Here, \(A\) and \(B\) are called the extent and intent of the concept, respectively. The set of all formal concepts is partially ordered by \[(A_1,B_1) \le (A_2,B_2) \iff A_1 \subseteq A_2 \quad (\text{equivalently, } B_1 \supseteq B_2),\] and this poset forms a lattice \(\mathcal{P}(\mathfrak{C})\), called the concept lattice.

An implication is an expression \(X \Rightarrow Y\) for \(X,Y \subseteq M\), which is said to hold if \(X^I \subseteq Y^I\), that is, every object having all attributes in \(X\) also has all attributes in \(Y\). It is trivial if \(Y \subseteq X\), and nontrivial otherwise.

An important example is the contranominal scale. For \(k \in \mathbb{Z}_{>0}\), define \[\mathfrak{C}_k = ([k], [k], \neq),\] where \((i,j) \in I\) if and only if \(i \ne j\). Thus each object has all attributes except one.

The concept lattice \(\mathcal{P}(\mathfrak{C}_k)\) is isomorphic to the Boolean lattice \(B(k)\). Equivalently, the context admits no nontrivial implications. Intuitively, the attributes are maximally independent: no attribute can be inferred from any combination of others.

This example is maximal in the sense that all subsets of \(M\) occur as intents. Any modification yields dependencies. For instance, adding \((3,c)\) yields the nontrivial implication \(\{a\} \Rightarrow \{c\}\), which collapses part of the Boolean structure and reduces the number of concepts.

Thus, forbidding large Boolean sublattices can be viewed as restricting the independence of attributes. Extremal lattices correspond to contexts whose concept lattices are as large as possible under such constraints.

For \(k=1\) and \(k=2\), the structure is simple: every \((n,1)\)-extremal lattice is a singleton, and every \((n,2)\)-extremal lattice is a chain of length \(n\). The first nontrivial case is therefore \(k=3\), which we now study. From the general theory developed in [29], we extract several results that will be used in this paper.

Let \(\mathcal{P}\) be an \((n,3)\)-extremal lattice and let \(\mathcal{C}\) be a maximal chain of \(\mathcal{P}\). Let \(\dot{\mathcal{C}} \mathrel{\vcenter{:}}= \Set{\dot{x} \mid x \in \mathcal{C}}\) be a disjoint copy of \(\mathcal{C}\). The doubling \(\mathcal{P}[\mathcal{C}]\) of \(\mathcal{C}\) in \(\mathcal{P}\) is the poset on \[\mathcal{P} \sqcup \dot{\mathcal{C}}\] whose order relation is defined by \[\begin{align} x \le y &\text{ whenever } x \le y \text{ in } \mathcal{P} \quad (x,y \in \mathcal{P}),\\ x \le \dot{y} &\text{ whenever } x \le y \text{ in } \mathcal{P} \quad(x \in \mathcal{P},\, y \in \mathcal{C}),\\ \dot{x} \le \dot{y} &\text{ whenever } x \le y \text{ in } \mathcal{P} \quad (x,y \in \mathcal{C}). \end{align}\]

We will show that \((n,3)\)-extremal lattices and regular vines are essentially equivalent notions. In this context, the realization of a regular vine as an induced subposet of a Boolean lattice is inessential; only its poset structure matters. Therefore, throughout this section, a regular vine will mean a poset satisfying the conditions in Definition 3.

Chornomaz [30] showed that the automorphism group of an \((n,3)\)-extremal lattice is a subgroup of the symmetric group \(S_{2}\) of degree \(2\). Moreover, Chornomaz obtained recurrence relations for the numbers \(p_{n}\) and \(q_{n}\) of isomorphism classes of \((n,3)\)-extremal lattices whose automorphism groups are \(S_{2}\) and \(\{\mathrm{id}\}\), respectively. In fact, the observation that the numbers of isomorphism classes of \((n,3)\)-extremal lattices and regular vines coincide for the first several values played an important role in discovering the equivalence between these two objects established in Theorem 22. We therefore obtain the following.

Similar recursive formulas for maximal ASPDs also appear in [12].

6.2 Extremal binary matrices without triangles↩︎

In this subsection, we discuss extremal binary matrices with no triangles arising in combinatorial matrix theory. We show directly that these matrices are equivalent to \((n,3)\)-extremal lattices and therefore also fit naturally into the splitting-and-merging framework.

There is a natural correspondence between \(2^{[n]}\) and the set of binary column vectors \(\{0,1\}^{n}\). Thus, every non-empty subset of \(2^{[n]}\) can be represented as a binary matrix. A triangle is the binary matrix \[\begin{align} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}. \end{align}\] A binary matrix \(M\) is said to have no triangles if no row and column permutation of \(M\) contains a triangle as a submatrix.

Anstee [31] showed that a binary matrix with \(n\) rows, distinct columns, and no triangles has at most \(1+n+\binom{n}{2}\) columns. A binary matrix achieving this upper bound is called an extremal binary matrix with no triangles.

Let \(\mathcal{D} \subseteq \mathcal{L}([n])\) be a maximal ASPD and define \[\begin{align} \mathcal{P} \mathrel{\vcenter{:}}= \Set{\{\omega(1), \dots, \omega(k)\} \mid \omega \in \mathcal{D},\;k \in [n]} \cup \{\varnothing\} \subseteq 2^{[n]}. \end{align}\] Let \(M\) be the binary matrix corresponding to \(\mathcal{P}\).

Note that \(\mathcal{P}\) is an \((n,3)\)-extremal lattice by Theorems 15 and 22. We now give a direct proof that \((n,3)\)-extremal lattices are equivalent to extremal binary matrices with no triangles.

In particular, combining Proposition 24 with the equivalences between maximal ASPDs, regular vines, and \((n,3)\)-extremal lattices established in Theorems 15 and 22, we recover the characterization of maximal ASPDs via extremal binary matrices with no triangles obtained by Karpov in Theorem 23.

Appendix: Catalog↩︎

We give here a catalog of MAT-labeled complete graphs, regular vines, and maximal ASPDs of order \(3\le n\le 6\) under the correspondences in Theorems 13, 14, and 15.

References↩︎