Here we discuss a problem of arranging k linear orders on n elements to maximize the number of sets that can be obtained as intersections of their initial intervals. We argue that this problem can shed light on a hard problem of characterizing formal contexts of bounded VC dimension, extremal with respect to the number of their objects and attributes. To tackle this problem we introduce limit objects, which capture their asymptotics, and propose, for all k, a tentative optimal solution. We prove that, under additional hypothesis of symmetry, it is indeed optimal for k = 3.
As it was shown by Alexandre Albano and the author [
i i=0
This bound itself can be traced back to a well-known lemma of Sauer and
Shelah [
Apart from FCA perspective, this problem can be formulated in purely lattice-theoretical terms by putting a doubly founded (or, less generally, a finite) lattice into correspondence with its standard context. With this identification, which we will use throughout the paper, objects and attributes become joinirreducible and meet-irreducible elements, and the VC-dimension of a lattice L is defined as the largest integer k for which a boolean lattice on k elements B(k) can be order-embedded into L, see [3, Lemma 1]. Lattices on n objects of VCdimension at most k with f (n, k) elements are called (n, k + 1)-extremal. We use k + 1 instead of k to emphasize that these lattices do not allow an embedding of B(k + 1), or, alternatively, do not shatter any (k + 1)-set.
A notable feature of (n, k +1)-extremal lattices is that they can be completely
characterized, in a feasible fashion, through the doubling construction [
An example of a more nuanced conjecture could be as follows: Conjecture 1 Maximal in size concept lattice of a formal context (G, M, I) of VC-dimension at most k, such that |G| + |M | = 2n, and such that k divides n, is the Cartesian product of k chains of length n/k − 1 each:
L = × C k n k where C(l) is an l-element chain. The size of L is (n/k)k.
At the moment, these problems seem too hard to approach. A first easy step could be to construct an (n, k + 1)-extremal lattice, which, at the same time, would minimize the number of attributes. Such lattices will be called (n, k + 1)doubly extremal. For k = 1 the construction is trivial, and further on we will show that for k = 2 doubly extremal lattice is exactly the interval lattice. For k ≥ 3, however, things start getting bleak. We thus resort to an even simpler problem, which will be the central object of this investigation, and, as we hope, can provide a key insight towards constructing doubly extremal lattices. We now state this problem formally, and postpone the discussion of how it is connected with doubly extremal lattices till Section 2.
Definition 1 (Configuration) For a fixed k, let a (discrete) k-configuration C = { i | i = 1, . . . , k} be a set of k linear orderings of n. We say that C generates a feasible set Y ⊆ n, if Y can be obtained as an intersection of initial intervals of ≤i, that is,
Y = k \ (xi]i i=1 for some xi ∈ n, where (v]i = {u ∈ n | u empty set is considered to be non-feasible.
i v}. As a matter of convenience, the Problem 2 (k-chains problem) Describe a k-configuration C that generates the maximal number of sets, and the number |C| of its feasible sets. In particular, what is the asymptotic behavior of |C| when n approaches infinity, that is, what is the value of the limit lim sup |Cn| = lim sup k! · |C| , n→∞ C k n→∞ C nk (1) and which families of configurations correspond to this limit.
As it turns out, as long as we are interested in asymptotics, it is natural to consider continuous objects called limit configurations, introduced in Section 3, which enable us to present configuration families with specific asymptotics as a single object.
Problem 2, however, is still too hard to solve in its full extent. In Section 4 we present a tentative optimal family of k-configurations and its continuous counterpart. This object satisfies several sufficient conditions for optimality, which, due to the lack of space, were not included in the paper. However, in Section 5 we prove that, under additional condition of symmetry, the configuration for k = 3 is indeed optimal. We also note that the general machinery of the proof holds for arbitrary k. The only part that is specific to k = 3 is purely combinatorial Lemma 6. This lemma can be formulated for arbitrary k, but we were unable to handle the general case. 2
The starting point for the estimation of the number of meet-irreducible elements (attributes) in extremal lattices is the following lemma.
Lemma 2 Any (n + k, k + 1)-extremal lattice L has at least k(n + 1) meetirreducible elements, arranged in k disjoint chains of length n + 1 each. Every such chain contains exactly one element of rank i, for i ∈ k − 1, . . . n + k − 1. Proof. We proved this lemma in another paper [5, Theorem 3]. The proof uses the technique of extremal decompositions, which was developed in that paper, and is rather involved, so we have no possibility to reproduce it here.
We call the chains of meet-irreducible elements from Lemma 2 the principal chains. Figure 1 gives an illustration of this construction. It is also trivial [5, Lemma 7] that, for k = 2, the interval lattices are (n, k + 1)-extremal with no other attributes than those, provided by Lemma 2. Thus: Corollary 3 The interval lattices are (n, 3)-doubly extremal.
For larger k, however, Lemma 2 does not describe all meet-irreducible
elements. The technique of extremal decompositions from [
d
Instead of looking for additional meet-irreducible elements, we can reverse the question and ask how the principal chains should be constructed in order to maximize the number of elements they generate, that is, of elements of the lattice that can be constructed from them by intersections. Answering this question may be quite helpful for the construction of doubly extremal lattices, because of the following plausible conjecture: Conjecture 2 In a doubly extremal lattice the principal chains are optimal in the sense of generating the (asymptotically) maximal possible number of elements.
Notice that every principal chain corresponds to a k-almost ordering of the set of its objects, where k-almost ordering of a set X is a partial order on X, in which all elements are comparable, except for k − 1 smallest elements, which are incomparable with each other. For the (4, 3)- and (4, 4)-extremal lattices from Figure 1, the corresponding orderings are a ≤ b ≤ c ≤ d and d ≤ c ≤ b ≤ a for the former, and b, c ≤ a ≤ d; b, d ≤ a ≤ c and c, d ≤ a ≤ b for the latter. There is a one-to-one correspondence between the elements of the principal chains and the initial intervals of these orderings.
Thus, in order to estimate the size of the fragment of an extremal lattice generated by the principal chains, we have to find a family of k almost orderings which is is optimal, in a sense that it generates the (asymptotically) maximal number of sets as intersections of its initial intervals. This, however, is literally Problem 2, but with almost orderings instead of orderings. But it is not a problem, as switching between almost orderings and orderings does not change the asymptotics as n growth to infinity.
Apart from this, it can be easily shown that for a fixed configuration, the
family of its feasible sets, together with the empty set, forms a convex geometry.
It is known, however, that the convex geometries can be considered a natural
generalization of the (n, k)-extremal lattices [
Let us take a k-configuration C. We say that an ordered k-tuple (m1, . . . , mk), mi ∈ n, is feasible and corresponds to X, if 1. X = Ti(mi]i is a nonempty (and thus feasible) set, 2. mi is maximal in X with respect to i, for all i = 1, . . . , k.
Notice that for every feasible set X and every ordering i there is always an element mi ∈ X, maximal with respect to i, the k-tuple of these elements is feasible, and it is a unique feasible tuple that corresponds to X. Thus, feasible sets and feasible tuples are in one-to-one correspondence. On the other hand, while we can associate with an arbitrary k-tuple a = (a1, . . . , am) a feasible (or empty) set A = Ti(ai]i, in general, a will not be feasible for A, even for nonempty A, as the following example shows: Example 1 Let k = 2 and n = 3, 1 1 2 1 3 and 1 2 3 2 2. Then for the configuration C = { 1, 2} there are four feasible sets: {1, 2, 3}, {1, 2}, {1, 3} and { }
1 ; and their feasible tuples are (3, 2), (2, 2), (3, 3) and (1, 1). The tuple (2, 3) is not feasible, because although it corresponds to the feasible set {1} = (2]1 ∩ (3]2, elements 2 and 3 do not lie in {1}, and thus can not be maximal in it with respect to any ordering.
By putting feasible sets and feasible tuples into correspondence, we conclude that there are at most kn feasible sets. But this estimate is way too crude, as the following statement holds: Statement 1 For a k-configuration C and a feasible tuple (m1, . . . , mk), such that all mi are different, a tuple (mσ(1), mσ(2), . . . , mσ(k)) is not feasible for any nontrivial permutation σ.
Proof. Let us take a nontrivial σ and fix j such that σ(j) 6= j. Then mσ(j) ≺j mj , and thus mj ∈/ Y = Tik=1(mσ(i)]i. But then mj cannot be in a feasible tuple, corresponding to Y , a contradiction.
Thus, there can be at most nk ≈ nk/k! feasible sets with distinct components, where a feasible set is a k-set in n, for which there is a corresponding feasible tuple. As for the tuples with repeating elements, their number will be asymptotically negligible comparing to nk, so we can disregard them. This clarification also explains the choice of the denominator in the limit in (1).
When analyzing a k-configuration, or rather a family of configurations Cn, parametrized with n, we will be interested in the volume vol of Cn: vol(Cn) = lim |Cn| = lim n→∞ nk n→∞ k! · |Cn| nk ≤ 1.
(2)
As long as we are concentrating on the asymptotics, it will be convenient
for us to define a notion of a limit object, which approximates the behavior of
the sequence of configurations as n goes to infinity. Good example of such limit
objects are graphons [
Our definition of a limit configuration exploits the fact that for a given
kconfiguration C, every element from the base set n naturally corresponds to a
tuple in nk, whose coordinates represent the relative position of the element
in corresponding chains. Further on, by measure on [
Definition 2 (Limit configuration) Limit k-configuration μ is a measure on
[
Usually we deal with a measure given in a form of a measurable weight
function w on a 1-dimensional manifold M ⊆ [
For a limit configuration μ, the axes, with their natural order, represent the chains; the measure μ represents relative positions of elements in the chains; and the restriction on projections reflects the fact that the elements are uniformly distributed along each chain.
A k-tuple (x1, . . . , xk), xi ∈ [
Z k
Y dμ(xi) = k! · μk(F ),
(x1,...,xk)∈F i=1
(3)
where μk is a measure on [
It is possible, and easy, to show that for every discrete configuration it is possible to construct a limit object, so that, for large n, their volumes would be arbitrary close. And, on the contrary, for every continuous configuration it is possible to construct a family of discrete configurations, which approximate it with respect to volume. The proofs are omitted due to space restrictions.
We conclude the section with a couple of examples of limit configurations. Example 2 (Discrete configuration) For a given k-configuration C on n, let us define a limit k-configuration μC in the following way. Let
P ⊆ [
× [ol(i)/n − 1/n, ol(i)/n], i∈n l=1,...,k where ol(i) is a position of i with respect to l in decreasing order, that is, if a l b l c, then ol(a) = 3, ol(b) = 2 and ol(c) = 1. We then take μC to be a measure, uniformly distributed over P , that is
μC (X) = |X ∩ P |/|P |. This construction gives a “continuous version” of the discrete configuration C, vol(C) ≤ vol(μC ), and for reasonable C, the difference between the volumes is small for large n.
Example 3 (Random configuration) Let us take a k-configuration C on n by choosing i to be a random ordering of n, taken independently for all i. It is easy to see that for a k-tuple (x1, . . . , xk) with distinct elements, the probability of being feasible is 1/kk (x1 is the smallest with respect to 1 with probability 1/k, etc.). Thus,
E vol(C) = k! kk .
A limit configuration, corresponding to this construction, is simply the Lebesgue measure μ(X) = |X|, and vol(μ) = E vol(C). 4
Author’s intuition prompts, and the rest of the paper will be devoted to substantiate this claim, that the following k-configuration can be asymptotically optimal for the k-chains problem, at least for k = 2 and 3: Definition 3 (Tentative optimal configuration) Let us fix k and n = k · m, and let us split n into k disjoint bunches of m elements each: a1, . . . am; b1, . . . bm; . . . ; z1, . . . , zm, where a, b, . . . , z is a symbolic representation of these k bunches. Then the asymptotically optimal k-configuration is Ok,n = { a, b , . . . , z}, where a = a1 ≥ · · · ≥ am ≥ bm ≥ · · · ≥ zm ≥ bm−1 ≥ · · · ≥ zm−1 ≥ b1 ≥ · · · ≥ z1;
z = z1 ≥ · · · ≥ zm ≥ am ≥ · · · ≥ ym ≥ am−1 ≥ · · · ≥ ym−1 ≥ a1 ≥ · · · ≥ y1. Figure 3 below illustrates this construction.
It can be the case that the tentative optimal construction can be optimized further, for example by swapping ai and bi in c. These modifications, however, are asymptotically negligible, and we thus refrain from trying them for the sake of simplicity. Note also, that for k = 2 orderings a and b will be inverse to each other, and it is easy to see that the corresponding lattice, as expected, will be the interval lattice on n elements, that is, (n, 3)-doubly extremal lattice. The corresponding limit configuration is defined as follows: Definition 4 (Optimal limit configuration) The limit configuration Ok,∞ = (M, w), which corresponds to the tentative optimal configuration family Ok,n, is defined as
M ⊆ [
[ [c, ei],
where c, ei ∈ [
Proposition 4 (Feasible sets of the optimal limit configuration.) A set {x1, . . . , xk} ⊆ Ok,∞ is feasible iff one of the following mutually exclusive conditions hold: 1. all {xi} lie on different line segments, xi ∈ [c, ei]. The corresponding feasible tuple is (x1, x2, . . . , xk); 2. or all {xi}, except for two of them, xp and xq, lie on different line segments: xi ∈ [c, ei], i 6= p, q. Elements xp and xq lie on one of the remaining segments [c, ep], and for xq it holds:
πq(xq) ≤ πq(xi), for all i = 1, . . . , k. The corresponding feasible tuple is (x1, x2, . . . , xk).
Figure 4 shows a feasible configuration corresponding to the second case of the above proposition. This, together with volume formula (3), enables us to easily calculate the volume of the optimal solution: Proposition 5 (Volume of the optimal limit configuration)
.
Z 1
0 kk·kk! =
For two and three chains we thus get: vol(O2,∞) = 1 and vol(O3,∞) = 23 . 5
An important feature which holds for Ok,∞, is that it is symmetric in the
following sense:
Definition 5 (Symmetry) We say that a limit k-configuration (or simply a
measure) μ is symmetric if μ (ρσ[X]) = μ(X), for every permutation σ on k
and every measurable X ⊆ [
In symmetric configurations all chains look alike, and it is reasonable to suppose that the optimal configuration would be symmetric. In this section we prove that, assuming symmetry, our tentative solution for k = 3 is the best possible. We start with the following simple combinatorial statement: Lemma 6 Let (A, B, C) be a subdivision of the set 9 into three nonintersecting subsets of size three each, and let a1, a2, a3; b1, b2, b3 and c1, c2 and c3 be enumerations of A, B and C correspondingly. We say that such triple of enumerations is feasible if a1 < b1, c1, b2 < a2, c2 and c3 < a1, b1. Then, for a fixed subdivision, the maximal number of feasible triples is 24.
Note. This lemma can be reformulated for larger, or even for arbitrary k, and an optimal upper bound can then be used for an upper bound for the symmetric case for arbitrary dimension. The solution strategy which we undertook there can not, however, be easily scaled, so finding such bound may prove problematic. Proof. In order to be able to compare subdivisions, let us introduce the following notations. For a subdivision S = (A, B, C), we denote the number of feasible triples of enumerations by n(S). For subdivisions S = (A, B, C) and S0 = (A0, B0, C0) we introduce the shift operation [S → S0], which translates the enumerations of S into the enumerations of S0, so that the relative order of elements inside every set remains the same. An example of the shift is given on Figure 5 below. Every shift is one-to-one and onto, and the inverse of [S → S0] is [S0 → S]. For a subdivision S0, we say that S is dominated by S0, denoted S S0, if for every feasible enumeration triple α of S, the triple [S →0 S]α is feasible for S0. Trivially, we might look for an optimal subdivision only among those, which are not dominated by any other.
Now, let us proceed with finding an optimal configuration, and note that the problem is symmetric, that is, for a feasible triple (a1, a2, a3; b1, b2, b3; c1, c2, c3) for the subdivision (A, B, C), the triple (b2, b1, b3; a2, a1, a3; c2, c1, c3) will be feasible for the subdivision (B, A, C), and so on. Here we changed the order of each enumeration in the same way as we changed the order of sets in the subdivision. Thus, without restricting generality, we can assume that the element 1 lies in A.
As 1 is the smallest element in 9, we can see that the only element from the enumeration that can be 1 is a1: if, to the contrary, we take, say, a2 = 1, then the constraint b2 < a2 will not hold. Now, we claim that an optimal position for A is {1, 8, 9}. Indeed, for a subdivision S = (A, B, C), let S0 = (A0, B0, C0) be the subdivision, obtained from S0 by shifting the second and the third elements of A to the right. It is easy to see that in this case the subdivision S0 dominates S, see Figure 5 for the illustration.
S S0
Now, in order for a subdivision to be optimal, we only need to optimally subdivide the set {2, . . . , 7} into B and C. As before, without losing generality, we may assume that the smallest element, that is 2, lies in B. Note that assigning b3 = 2 breaks the constraint c3 < b3, but it is, in principle, possible for a feasible enumeration to have b1 = 2 or b2 = 2, so we can not apply the same simple argument as we did for the optimal position of A.
However, there are not so many ways to make such subdivision: in fact, there are ten, so we may check them manually. In order to simplify it even further, we note that all subdivisions with 2, 3 ∈ B are dominated by B = {2, 3, 7} and C = {4, 5, 6}, and the subdivisions with 2 ∈ B and 6, 7 ∈ C are dominated by B = {3, 4, 5} and C = {2, 6, 7}. Other five we check manually, and obtain that there are several choices for an optimal subdivision S∗ = (B, C), with n(S∗) = 12. The situation is subsumed on Figure 6.
Now, an optimal subdivision for S = (A, B, C) is obtained by combining the optimal position of A with one of the optimal subdivisions for S∗ = (B, C). In this case, n(S) = 24, finishing the proof of the lemma. See Figure 7 for example.
For this part we introduce additional definitions for measures on [
C:
then its total size is 1. A measure μ is diagonal-free if μ (D) = 0, where D =
{x ∈ [
Proof. Let us fix such μ. The proof strategy is to show that for every feasible tuple on μ, only a specific fraction of tuples, obtained from it by permutations, may be feasible.
By (3), we evaluate the volume of μ as where FD = F \D3 is a diagonal-free version of F . Note, that the elements of FD can have coinciding coordinates. Indeed, due to exclusion of the diagonal, for an element (x, y, z) ∈ FD it holds that x1 6= x2 6= x3, but it may hold that, for example, x1 = y1. But finite size of μ and its continuousness on projections ensure that the volume of these points is 0. For example:
Z (x,xy1,z=)y∈1FD dμ(x)μ(y)μ(z) ≤ =
Z
Z
x∈[
Z
Now, if we apply permutations σx, σy and σz to the coordinates of x, y and z, we get
o(x, y, z) = (X, Y, Z), ex, ey, ez , o(σx(x), σy(y), σz(z)) = (X, Y, Z), σx(ex), σy(ey), σz(ez) .
So, 3! · 24
3!3 2 Z
.
where Fo is a set of feasible orderings of 9, n(X, Y, Z) is a number of feasible
enumerations for a subdivision (X, Y, Z), and [X, Y, Z] is a subset in [
Lemma 8 For a symmetric k-configuration μ there is a family {μa}a∈(1,∞) of
symmetric continuous on projections diagonal-free measures on [
Proof. Due to the lack of space, we prove this lemma only for k = 2. The similar, but more elaborated proof can be carried over for arbitrary k.
For a fixed α ∈ (1, ∞) we split [
LU = {(x, y) | x = αy, y > 0},
CU = {(x, y) | x < αy, y > 0},
We define the mapping ·∗ : (LL ∪ LU ∪ CL ∪ CU ) 7→ [
(αu, v), (u, v) ∈ LU ∪ CU .
Note that ·∗ is one-to-one on CL ∪ CU , and (LL ∪ LU )∗ = D. Now, we define μα
as
μα(X) = μ X ∩ (CL ∪ CU ) ∗ +
μ X ∩ LL ∗ +
μ X ∩ LU ∗,
for every measurable X ⊆ [
It is trivial to check that μα is symmetric, diagonal-free, continuous on projections and has total size 1. Notice also that μ(Y ) = μα([·∗]−1Y ), for every measurable Y . The only thing we need to check is that the volumes of μa converge towards vol(μ).
Z
(x,y)∈F\Z2 vol(μα) = 2
Z Z Z (x,y)∈F+ (x,y)∈F+ (x,y)∈(F\Z2)∗ |vol(μα) − vol(μ)| ≤ 2 where F ⊆ F + = [·∗]−1(F \Z2)∗. Then where Δ denotes the symmetric difference. We estimate two summands separately. If (x, y) ∈ (F \Z2)∗ΔF then something like x1 ≤ y1 ≤ αx1 holds (perhaps along different coordinate, perhaps with x and y swapped). Then Z (x,y)∈(F\Z2)∗ΔF dμ(x)μ(y) ≤ C ≤ C
Z x
Z y∈[x1,α+x1]
dμ(x)μ(y) {(x,y) | x1≤y1≤αx1}
! dμ(y) dμ(x) ≤ C [x1, α + x1] = Cα. for some constant C, which depends only on k. For the second estimate let us consider what it means for (x, y) to lie in F +\F . First of all, as ·∗ is one-to-one on CL∪CU , then either x or y (or both) lie in LL∪LU . Say, x ∈ LL, which means that x1 = αx2. Then (x, y) ∈/ F but (x0, y) ∈ F , where x0 = (x2, x1) = (x2, αx2). Yet again, something like x2 ≤ y2 ≤ αx2 holds (perhaps along different coordinate, perhaps with x and y swapped). After applying ·∗, to change from F +\F to (F +\F )∗, these restriction can only change by α. So, just like for the previous summand, we infer
Z (x,y)∈ F+\F ∗
dμ(x)μ(y) ≤ Dα2. for some constant D, which depends only on k. The combination of these two estimates finishes the proof.
Theorem 9 (Optimality under symmetry assumption) For a symmetric limit 3-configuration μ, it holds: vol(μ) ≤ 3!/33−1 = 2/3, that is, vol(μ) ≤ vol(O3,∞). Thus, the configuration O3,∞ is optimal symmetric 3-configuration. Proof. By Lemma 7, this bound holds for arbitrary symmetric continuous on projections diagonal-free measure η of total size 1, and by Lemma 8, every symmetric k-configuration μ can be approximated (in volume) by such measures with arbitrary precision.
The author is grateful to Alexandre Luiz Junqueira Hadura Albano for reading the initial draft and making a sanity check, and to anonymous reviewers, for their detailed remarks, which, hopefully, have made this paper more readable.