Comments on the Golden Partition Conjecture

Authors

  • Marcin Piotr Peczarski Institute of Informatics University of Warsaw

DOI:

https://doi.org/10.11575/cdm.v12i1.62349

Keywords:

Poset, Linear extension, 1/3--2/3 Conjecture, Golden Partition Conjecture

Abstract

We generalize the result of Zaguia that 1/3--2/3 Conjecture is satisfied by every N-free finite poset which is not a chain: we show a wider class of posets which satisfy the Golden Partition Conjecture. We generalize the result of Pouzet that 1/3--2/3 Conjecture is satisfied by every finite poset with a non-trivial automorphism: we show that such posets satisfy the Golden Partition Conjecture.

References

G. Brightwell,

Balanced pairs in partial orders,

Discrete Math. 201 (1--3) (1999) 25--52.

B. Ganter, G. H\"afner, W. Poguntke,

On linear extensions of ordered sets with a symmetry,

Discrete Math. 63 (2--3) (1987) 153--156.

S.S. Kislitsyn,

Finite partially ordered sets and their associated sets of permutations,

Mat. Zametki 4 (5) (1968) 511--518.

N. Linial,

The information theoretic bound is good for merging,

SIAM J. Comput. 13 (4) (1984) 795--801.

M. Peczarski,

The gold partition conjecture,

Order 23 (1) (2006) 89--95.

I. Zaguia,

The 1/3--2/3 conjecture for N-free ordered sets,

Electr. J. Comb. 19 (2) (2012) P29.

Downloads

Published

2017-09-27

Issue

Section

Articles