2
$\begingroup$

I was wondering if anything is known about this problem. Fix $0\leq m\leq k$. We are given a graded poset and we fix an element $x$ of rank $k$. Is it possible to estimate the number of elements $y$ of rank $k$ such that $x\wedge y$ has rank $m$? (I suppose the poset must be a meet-semilattice for this to be well-defined.)

I have kept the formulation general, but I'd be happy to hear any results with extra hypotheses on the poset. In fact, my use case is a lattice of certain subsets of a finite ground set. I think another formulation would be in terms of shadows in a set system. Is there a bound on the cardinality of the $(k-m)$th upper shadow of the $(k-m)$th lower shadow of a singleton in $X^{(k)}$? I apologise in advance if this question turns out to be trivial.

Edit. Based on the answer below, it seems there isn't something one can really say in general, so I'll just post my motivating example. Consider the poset of all subsets of $\{1,2,\ldots,n\}$ that are a (nonempty) arithmetic progression and fix a progression $P$ of length $k$. How many progressions of length $k$ have $m$ elements in common with $P$, for $0\leq m\leq k$?

I'd also be interested in any references that deal with any interesting properties of this poset. For example, the size of this poset seems to be $$1+n+\sum_{m=1}^{n-1}\sum_{k=1}^{n-1} \bigg\lfloor{m\over k}\bigg\rfloor,$$ according to the OEIS.

Improve this question
$\endgroup$
6
  • $\begingroup$ Interesting idea to consider the set of arithmetic progressions as a poset (haven't seen that before). Note that in general this poset is not even graded, starting from $n=4$ because (1,4), of length 2, is covered by (1,2,3,4), of length 4, and not by either of the length-3 progressions (1,2,3) and (2,3,4). $\endgroup$
    – Jukka Kohonen
    Commented May 24, 2021 at 15:15
  • $\begingroup$ Oops, that's embarrassing. I guess that sort of makes the question senseless $\endgroup$
    – Marcel K. Goh
    Commented May 24, 2021 at 20:48
  • $\begingroup$ No, I think the new question (about arithmetic progressions) is quite sensible. But I have no idea whether viewing it as a (non-graded) poset structure is helpful. It might be easier to attack it directly by number-theoretic means. Might be useful to post it as a separate question. $\endgroup$
    – Jukka Kohonen
    Commented May 25, 2021 at 0:16
  • $\begingroup$ Also, the more general question (properties of this poset) is certainly interesting. I haven't seen this as a poset before, but that's just me. $\endgroup$
    – Jukka Kohonen
    Commented May 25, 2021 at 0:26
  • $\begingroup$ @JukkaKohonen I will post the arithmetic progressions question separately! Indeed, even though the poset is not graded there are still lots of questions to ask about it, and I'm not sure if anything interesting will pop up, but I will continue looking into it for sure! $\endgroup$
    – Marcel K. Goh
    Commented May 25, 2021 at 0:52

1 Answer 1

Reset to default
2
$\begingroup$

If you only know that your poset is graded, I don't see any easy bounds, unless you have some auxiliary information. In general, the $y$'s could be all elements of rank $k$ (except $x$ itself), for example if your poset looks like this, and you fix $m=1$, $k=3$, $x=11$. Every distinct pair of elements at rank $k=3$ meet at rank $m=1$, namely, at the element "1".

Example graded poset

At the other extreme, if you know your poset is the Boolean lattice on a ground set of $n$ elements, the answer is simple. Seeing that $x$ and $y$ are sets of $k$ elements, their meet has rank $m$ iff $|x \cap y|=m$. Given $x$, the number of such $y$'s is $$ \binom{k}{m} \binom{n-k}{k-m} $$ because they are exactly those $k$-element sets that have $m$ elements from $x$, and $k-m$ elements from outside $x$.

However, it sounds like you have some case in between. It may be easier to answer if you can specify your case in more detail.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for this answer! I realise now that the problem was too broad and have edited my original post to include my motivating example. $\endgroup$
    – Marcel K. Goh
    Commented May 24, 2021 at 12:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .