Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-09T17:50:22.204Z Has data issue: false hasContentIssue false

The Minimum Independence Number of a Hasse Diagram

Published online by Cambridge University Press:  07 April 2006

JIŘÍ MATOUšEK
Affiliation:
Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republicmatousek@kam.mff.cuni.cz, privetivy@kam.mff.cuni.cz
ALEš PŘÍVĚTIVÝ
Affiliation:
Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republicmatousek@kam.mff.cuni.cz, privetivy@kam.mff.cuni.cz
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let $P=(X,\le)$ be a finite partially ordered set. That is, $X$ is a finite ground set and $\le$ is a partial ordering on $X$ (a reflexive, transitive, and weakly antisymmetric relation). An $x\in X$ is an immediate predecessor of a $y\in X$ if $x<y$ and there is no $z\in X$ with $x<z<y$ (where $x<y$ means that $x\le y$ and $x\ne y$). The Hasse diagram$H(P)$ is the undirected graph with vertex set $X$ and with $\{x,y\}$ forming an edge if $x$ is an immediate predecessor of $y$ or if $y$ is an immediate predecessor of $x$. We denote bya $\alpha(H(P))$ the independence number of the Hasse diagram, that is, the maximum possible size of a subset $I\subseteq X$ such that no element of $I$ is an immediate predecessor (in $P$) of another element of $I$. This quantity should not be confused with the maximum size of an antichain in $P$, which is sometimes denoted by $\alpha(P)$.

Information

Type
PROBLEM SECTION
Copyright
2006 Cambridge University Press