Topics in combinatorics and combinatorial algorithms

In this dissertation we investigate three topics. The first is a structural parameter for partially ordered sets (posets). The parameter that we study is the interval number of a poset, denoted by i(P) for a poset P. The interval number is related to a well-studied poset parameter, partial order dimension. We derive an upper bound on the interval number of a poset in terms of its dimension. We determine the interval number exactly for several classes of posets, such as the Boolean algebras. The behavior of interval number under poset operations is studied and so are one-point removal theorems. Asymptotic bounds on the interval number of almost every poset are derived, as well as results concerning the computational complexity of this parameter.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Madej, Thomas

Contributors dc:contributor

• Liu, Jane W.S.

• Mathematics
• Computer Science

Statement dc:rights

• Copyright 1989 Madej, Thomas

Language dc:language

eng

Identifier

AAI9010947
(UMI)AAI9010947

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/20233