- FindStat

edit this statistic or download as text // json

Identifier

St000848: Posets ⟶ ℤ

Values

([],2) => 1

([(0,1)],2) => 0

([],3) => 3

([(1,2)],3) => 1

([(0,1),(0,2)],3) => 1

([(0,2),(2,1)],3) => 0

([(0,2),(1,2)],3) => 1

([],4) => 12

([(2,3)],4) => 6

([(1,2),(1,3)],4) => 4

([(0,1),(0,2),(0,3)],4) => 3

([(0,2),(0,3),(3,1)],4) => 1

([(0,1),(0,2),(1,3),(2,3)],4) => 1

([(1,2),(2,3)],4) => 2

([(0,3),(3,1),(3,2)],4) => 1

([(1,3),(2,3)],4) => 4

([(0,3),(1,3),(3,2)],4) => 1

([(0,3),(1,3),(2,3)],4) => 3

([(0,3),(1,2)],4) => 3

([(0,3),(1,2),(1,3)],4) => 2

([(0,2),(0,3),(1,2),(1,3)],4) => 2

([(0,3),(2,1),(3,2)],4) => 0

([(0,3),(1,2),(2,3)],4) => 1

([],5) => 60

([(3,4)],5) => 30

([(2,3),(2,4)],5) => 20

([(1,2),(1,3),(1,4)],5) => 15

([(0,1),(0,2),(0,3),(0,4)],5) => 12

([(0,2),(0,3),(0,4),(4,1)],5) => 6

([(0,1),(0,2),(0,3),(2,4),(3,4)],5) => 4

([(0,1),(0,2),(0,3),(1,4),(2,4),(3,4)],5) => 3

([(1,3),(1,4),(4,2)],5) => 7

([(0,3),(0,4),(4,1),(4,2)],5) => 4

([(1,2),(1,3),(2,4),(3,4)],5) => 5

([(0,2),(0,3),(2,4),(3,4),(4,1)],5) => 1

([(0,3),(0,4),(3,2),(4,1)],5) => 3

([(0,2),(0,3),(2,4),(3,1),(3,4)],5) => 2

([(0,1),(0,2),(1,3),(1,4),(2,3),(2,4)],5) => 2

([(2,3),(3,4)],5) => 10

([(1,4),(4,2),(4,3)],5) => 5

([(0,4),(4,1),(4,2),(4,3)],5) => 3

([(2,4),(3,4)],5) => 20

([(1,4),(2,4),(4,3)],5) => 5

([(0,4),(1,4),(4,2),(4,3)],5) => 2

([(1,4),(2,4),(3,4)],5) => 15

([(0,4),(1,4),(2,4),(4,3)],5) => 3

([(0,4),(1,4),(2,4),(3,4)],5) => 12

([(0,4),(1,4),(2,3)],5) => 10

([(0,4),(1,3),(2,3),(2,4)],5) => 8

([(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 7

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 6

([(0,4),(1,4),(2,3),(4,2)],5) => 1

([(0,4),(1,3),(2,3),(3,4)],5) => 4

([(0,4),(1,4),(2,3),(2,4)],5) => 9

([(0,4),(1,4),(2,3),(3,4)],5) => 6

([(1,4),(2,3)],5) => 15

([(1,4),(2,3),(2,4)],5) => 10

([(0,4),(1,2),(1,4),(2,3)],5) => 4

([(0,3),(1,2),(1,3),(2,4),(3,4)],5) => 2

([(1,3),(1,4),(2,3),(2,4)],5) => 10

([(0,3),(0,4),(1,3),(1,4),(4,2)],5) => 3

([(0,3),(0,4),(1,3),(1,4),(3,2),(4,2)],5) => 2

([(0,4),(1,2),(1,4),(4,3)],5) => 3

([(0,4),(1,2),(1,3)],5) => 10

([(0,4),(1,2),(1,3),(1,4)],5) => 9

([(0,2),(0,4),(3,1),(4,3)],5) => 2

([(0,4),(1,2),(1,3),(3,4)],5) => 4

([(0,2),(0,3),(1,4),(2,4),(3,1)],5) => 1

([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 4

([(0,3),(0,4),(1,2),(1,4)],5) => 8

([(0,3),(0,4),(1,2),(1,3),(1,4)],5) => 7

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4)],5) => 6

([(0,3),(0,4),(1,2),(1,3),(2,4)],5) => 3

([(0,3),(1,2),(1,4),(3,4)],5) => 4

([(0,3),(0,4),(1,2),(2,3),(2,4)],5) => 3

([(1,4),(3,2),(4,3)],5) => 2

([(0,3),(3,4),(4,1),(4,2)],5) => 1

([(1,4),(2,3),(3,4)],5) => 7

([(0,4),(1,2),(2,4),(4,3)],5) => 1

([(0,3),(1,4),(4,2)],5) => 4

([(0,4),(3,2),(4,1),(4,3)],5) => 1

([(0,4),(1,2),(2,3),(2,4)],5) => 3

([(0,4),(2,3),(3,1),(4,2)],5) => 0

([(0,3),(1,2),(2,4),(3,4)],5) => 3

([(0,4),(1,2),(2,3),(3,4)],5) => 2

([(0,3),(1,4),(2,4),(3,1),(3,2)],5) => 1

([],6) => 360

([(4,5)],6) => 180

([(3,4),(3,5)],6) => 120

([(2,3),(2,4),(2,5)],6) => 90

([(1,2),(1,3),(1,4),(1,5)],6) => 72

([(0,1),(0,2),(0,3),(0,4),(0,5)],6) => 60

([(0,2),(0,3),(0,4),(0,5),(5,1)],6) => 30

([(0,1),(0,2),(0,3),(0,4),(3,5),(4,5)],6) => 20

([(0,1),(0,2),(0,3),(0,4),(2,5),(3,5),(4,5)],6) => 15

([(0,1),(0,2),(0,3),(0,4),(1,5),(2,5),(3,5),(4,5)],6) => 12

([(1,3),(1,4),(1,5),(5,2)],6) => 36

([(0,3),(0,4),(0,5),(5,1),(5,2)],6) => 20

([(1,2),(1,3),(1,4),(3,5),(4,5)],6) => 24

([(1,2),(1,3),(1,4),(2,5),(3,5),(4,5)],6) => 18

([(0,2),(0,3),(0,4),(2,5),(3,5),(4,5),(5,1)],6) => 3

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The balance constant multiplied with the number of linear extensions of a poset.
A pair of elements $x,y$ of a poset is $\alpha$-balanced if the proportion $P(x,y)$ of linear extensions where $x$ comes before $y$ is between $\alpha$ and $1-\alpha$. The balance constant of a poset is $\max\min(P(x,y), P(y,x)).$
Kislitsyn [1] conjectured that every poset which is not a chain is $1/3$-balanced. Brightwell, Felsner and Trotter [2] show that it is at least $(1-\sqrt 5)/10$-balanced.
Olson and Sagan [3] exhibit various posets that are $1/2$-balanced.

References

[1] Kislicyn, S. S. Finite partially ordered sets and their corresponding permutation sets MathSciNet:0244113
[2] Brightwell, G. R., Felsner, S., Trotter, W. T. Balancing pairs and the cross product conjecture MathSciNet:1368815
[3] Olson, E. J., Sagan, B. E. On the $1/3-2/3$ Conjecture arXiv:1706.04985

Code

def statistic(P):
    l_ext = P.linear_extensions().list()
    max_balance = 0
    for x,y in Subsets(P,2):
        l = [ext for ext in l_ext
             if ext.index(x) < ext.index(y)]
        new_balance = min(len(l), len(l_ext)-len(l))
        max_balance = max(new_balance, max_balance)
    return max_balance

Created

Jun 16, 2017 at 06:35 by Martin Rubey

Updated

Jul 17, 2017 at 07:29 by Martin Rubey