Wednesday, January 6, 2010

Теория частичных порядков 2

В статье [1] упоминается о том, что граф линейных расширений $G(P)$ не является инвариантом сравнимости, при этом дается ссылка на [2].

Удалось найти работу [3], в которой отыскивается число линейных расширений с минимильным числом скачков.

В работе [1] приводится интересная теорема о том, что диаметр $G(P)$ равен числу несравнимых пар в минимальном двухмерном расширении $P$.
  1. Felsner S. The Linear-Extension-Diameter of a Poset / S. Felsner, K. Reuter // SIAM Journal on Discrete Mathematics, 1999.
  2. K. Reuter Linear Extensions of a Poset as Abstract Convex Sets, Preprint, Universitaet Hamburg, 1996.
  3. H.C. Jung Counting jump optimal linear extensions of some posets // Recent progress in algebra, AMS, 1999.

No comments:

Post a Comment