1
$\begingroup$

Consider a poset $P = (V,A)$. We may define a path structuring of $P$ as a chain $\Sigma$ of the form $X_0 \subset X_1 \subset \ldots \subset X_n$ where :

(i) for every $x \in V$, the set $\{ i \in [n] : x \in V_i \}$ is an interval,

(ii) for every $i$ we have $X_{i+1}$ of the form $X_i + \{x\}$ or $X_i - \{x\}$,

(iii) for every $i < j$, $P$ contains no backward arcs joining $X_j - X_i$ to $X_i - X_j$.

The width of $\Sigma$ is defined as $w(\Sigma) = \max_i |X_i|$, and the path-width of $P$ is defined as the minimum width of a path structuring of $P$. In particular, the path-width is always smaller than the width (defined as the size of a largest antichain).

The following questions seem natural in this respect:

  1. is it possible to define a corresponding notion of tree-width that is well-behaved? E.g. we would expect forest posets to have tw at most 1, and series-parallel posets to have tw at most 2.

  2. is it possible to get a width measure that is algorithmically useful? A possible application would be the counting of linear extensions: it is feasible in $n^{O(w)}$ for a poset of width $w$, but the extension to path-width / tree-width seems unlikely at this point.

$\endgroup$
  • $\begingroup$ Judging from your definitions, you probably want $V_j := \bigcup_{k \leqslant j} X_k$ and $V_j \subset V_{j+1}$. Anyway: every poset describes a directed acyclic simple graph (omitting the self-loops). If the graph is finite, it also has a transitive reduction. Your path structuring is then effectively the path decomposition which is standard in graph theory, and one may consider tree decompositions instead if one wishes. $\endgroup$ – Niel de Beaudrap Apr 25 '14 at 7:01
  • 2
    $\begingroup$ The purpose of this site is, essentially, for us to help each other with research. The Help Center says, "You should only post questions you're actually seriously thinking about." If you had seriously thought about these questions before posting them, you would know whether or not they were natural, rather than just saying that they "seem natural". It seems to me that you are just posting questions here because you want to give people questions to answer, not because you actually want the answers. Please stop doing this. $\endgroup$ – David Richerby Apr 25 '14 at 8:07
  • $\begingroup$ I admit that you're right, however I'm not the only one to do this, e.g. there are several questions related to separation of complexity classes which I doubt the author is serious about. As I said earlier I was just trying to suggest some directions for research that (i) I consider fruitful but (ii) I don't have time to investigate currently. I'm not aware of any other place that would better suit this purpose. $\endgroup$ – NisaiVloot Apr 25 '14 at 8:31
  • 1
    $\begingroup$ The open problems section of your next paper? $\endgroup$ – Tyson Williams Apr 25 '14 at 10:55
  • $\begingroup$ I canot tell if this is ironic, but given the delays due to reviews & revisions I'd rather post here first where I have the possibility of getting a larger audience & targeting different topics. I will consider your suggestion in due course though.. $\endgroup$ – NisaiVloot Apr 25 '14 at 11:10

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.