Dtjytyk

Let $X$ be a finite poset.

If
$$X = X_1 cup X_2$$
where $X_1$ and $X_2$ are strict upper sets, then a lot of properties of $X$ can be inferred from the smaller posets $X_1, X_2$ and $X_1cap X_2$ (see background below). We can now subdivide these 3 posets in the same way. If we keep subdividing these posets, then we will eventually end up with "trivial" posets, which for my purposes is when it only has 1 minimal element.

My question is: If we keep subdividing $X$ into 2 strict upper sets and their intersection, until we reach "trivial" posets, how many
distinct (as sets) posets will we have encountered?

I'm interested in how this value grows as a function of the number of points of $X$, with the best choice of subdivision on the worst poset $X$. Is it polynomial? Can you give an example where it is exponential?

As you can see, in the background below, I make a very specific choice of subdivision. An answer to the question for only this subdivision scheme is also very helpful.

Thanks for your help!

Some Background:

I will write $X_{text{min}}$ for the set of minimal elements of $X$. I will also write $uparrow Y$ for the upper set of $Y subseteq X$.

The Euler characteristic of $X$ is the alternating sum
$$chi(X) = sum_{n=0}^infty (-1)^n #C_n$$
where $#C_n$ is the number of chains of length $n$ in $X$.

Alternatively, it is the Euler characteristic of $X$ seen as a topological space. (ignore this if unfamiliar).

I want to compute the Euler characteristic (and many similar concepts) of a poset using the following 3 properties:

1. 
   $chi(A cup B) = chi(A) + chi(B) - chi(A cap B) $ if $A$ and $B$ are upper sets.


2. If $X_{text{min}}$ has only 1 element, then $chi(X) = 1$
   


3. 
   $chi(emptyset) = 0$

Propertiy 1 can be seen as a recursion, while property 2 and 3 can serve as a base case for this recursion. This leads to the following algorithm (pseudocode):

def euler_characteristic(X):



    if len(X_min) == 1:

        return 1

    elif len(X_min) == 0:

        return 0

    else:



        # subdivide X_min into 2 roughly equal disjoint parts:

        middle = len(X_min)//2

        I = X_min[0:middle]

        J = X_min[middle:end]



        return   euler_characteristic(↑I)

               + euler_characteristic(↑J)

               - euler_characteristic(↑I ∩ ↑J)

Actual working sage code can be found and ran here.

One could ask, how many times does this code call the function euler_characteristic as a function of $n$ asymptotically in the worst case. Then the answer is $Theta(3^n)$ as this example shows.

However, in that example, the function often gets called with the same input. We could just store inputs and outputs that we already calculated and first do a look up there. Then the above example is no longer exponential.

Alternative formulation of the question: How many times does the function get called on distinct inputs?

Some more background:
The above discussion with the Euler characteristic is just one (simple) example of where this technique could be used. In algebraic topology, there are more invariants of finite topological spaces which satisfy similar properties that could lead to a similar algorithm. For example, for the homology groups and Betti numbers we have the Mayer-Vietoris sequence, while for the fundamental group(oid) we have the Seifert–van Kampen theorem.

In this pre-print article, the idea is introduced for Betti numbers. Watch out, it contains mistakes (for example, it claims the amount of calls is polynomial in general, which it isn't as my example shows) and is incomplete. It is useful tough, to get a good idea of what my question is about.