- FindStat

edit this statistic or download as text // json

Identifier

St000849: Posets ⟶ ℤ

Values

([],2) => 1

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

([],3) => 3

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

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

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

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

([],4) => 6

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

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

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

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

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

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

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

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

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

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

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

([(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) => 2

([],5) => 10

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

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

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

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

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

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

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

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

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

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

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

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

([(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) => 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

([(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) => 2

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

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

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

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

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

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

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

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

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

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

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

([(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) => 4

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

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

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

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

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

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

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

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

([],6) => 15

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

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

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

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

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

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

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

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

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

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

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

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

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

([(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 number of 1/3-balanced pairs in a poset.
A pair of elements $x,y$ of a poset is $\alpha$-balanced if the proportion of linear extensions where $x$ comes before $y$ is between $\alpha$ and $1-\alpha$.
Kislitsyn [1] conjectured that every poset which is not a chain has a $1/3$-balanced pair. Brightwell, Felsner and Trotter [2] show that at least a $(1-\sqrt 5)/10$-balanced pair exists in posets which are not chains.
Olson and Sagan [3] show that posets corresponding to skew Ferrers diagrams have a $1/3$-balanced pair.

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, alpha=1/3):
    l_ext = P.linear_extensions().list()
    lower = len(l_ext)*alpha
    upper = len(l_ext)*(1-alpha)
    pairs = 0
    for x,y in Subsets(P,2):
        l = [ext for ext in l_ext
             if ext.index(x) < ext.index(y)]
        if lower <= len(l) <= upper:
            pairs += 1
    return pairs

Created

Jun 16, 2017 at 06:20 by Martin Rubey

Updated

Jul 17, 2017 at 07:30 by Martin Rubey