The Worst Balanced Partially Ordered Sets—Ladders with Broken Rungs

ABSTRACT

We present results of a computer search for partially ordered sets (posets) with fairly small value of the balance constant. The motivation behind this work was to search for a poset with the balance constant less than 1/3. Such a poset would be a counterexample to the 1/3–2/3 Conjecture and its generalization, which is the Golden Partition Conjecture. A counterexample is not found, but obtained results led us to define a new class of posets, which we call ladders with broken rungs. This class contains the worst known balanced posets. Finally, based on the found examples, we conjecture that the worst balanced n-element poset (except n = 5, 7, 8), being not a linear sum, is a ladder with broken rungs, and that there exists a constant β ≈ 0.348843, such that there is no poset with a value of the balance constant greater than 1/3 and less than β.

KEYWORDS:

• Poset
• linear extension
• balance constant
• 1/3–2/3 Conjecture
• Golden Partition Conjecture

2010 AMS Subject Classification:

• 06A11