0
$\begingroup$

Let $(E, \preceq)$ be a finite distributive lattice, $H_E$ be the Hasse diagram of $E$ and $d$ be the distance on $E \times E$ defined as the length of the shortest path in $H_E$ between any pair of points from $E$. An interval is a subset from $E$ of the form $[inf(e_1, e_2), sup(e_1, e_2)]$ for some $e_1, e_2 \in E$. The set $\mathcal{I}_E$ denotes the set of all intervals from $E$. A profile $P$ is a non-empty finite multiset of intervals. The set $\mathcal{P}_E$ denotes the set of all profiles. The distance $d$ is extended to the mapping $E \times \mathcal{I}_E \mapsto \mathbb{N}$ defined $\forall e \in E$, $\forall I \in \mathcal{I}_E$ as $d(e, I) = \min\{d(e, e') \mid e' \in I\}$. Then, $d$ is extended to the mapping $E \times \mathcal{P}_E \mapsto \mathbb{N}$ defined $\forall e \in E$, $\forall P \in \mathcal{P}_E$ as $d(e, P) = \sum\{d(e, I) \mid I \in P\}$. Lastly, for any profile $P \in \mathcal{P}_E$ let us denote $Merge(P)$ the set $argmin\{d(e, P) \mid e \in E\}$ (i.e., $Merge(P) = \{e \in E \mid \forall e' \in E, d(e, P) \leq d(e', P)\}$).

I would like to show that for any profile $P \in \mathcal{P}_E$, we have that $(Merge(P), \preceq)$ is an interval from $\mathcal{I}_E$ (or to find a counter-example, that I failed to do so far).

$\endgroup$
2
  • $\begingroup$ What does merge(P) look like when P is the set of intervals (x,1) in the boolean lattice where x ranges over all elements of distance 2 from 0, the least element of the lattice. My guess is the result is an antichain, or a semilattice, and not a lattice. $\endgroup$ May 26, 2014 at 18:34
  • $\begingroup$ erratum: I actually want to prove that $Merge(P)$ is always an interval from $\mathcal{I}_E$. I am not sure whether it is an equivalent proposition, otherwise sorry for the confusion, I am editing the request. Said that, if I get your example, then $merge(P) = \{1\}$, i.e., the intersection of all intervals from $P$ (which is always an interval in the specific case where the intersection of all intervals from $P$ is a non-empty set). $\endgroup$
    – user109711
    May 26, 2014 at 18:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.