edit this statistic or download as text // json
Identifier
Values
=>
Cc0029;cc-rep
([],1)=>1 ([(0,1)],2)=>2 ([(0,2),(2,1)],3)=>5 ([(0,1),(0,2),(1,3),(2,3)],4)=>4 ([(0,3),(2,1),(3,2)],4)=>14 ([(0,1),(0,2),(0,3),(1,4),(2,4),(3,4)],5)=>2 ([(0,2),(0,3),(1,4),(2,4),(3,1)],5)=>5 ([(0,3),(1,4),(2,4),(3,1),(3,2)],5)=>13 ([(0,4),(2,3),(3,1),(4,2)],5)=>42 ([(0,2),(0,3),(2,4),(3,4),(4,1)],5)=>13 ([(0,1),(0,2),(0,3),(0,4),(1,5),(2,5),(3,5),(4,5)],6)=>2 ([(0,2),(0,3),(0,4),(1,5),(2,5),(3,5),(4,1)],6)=>3 ([(0,3),(0,4),(1,5),(2,5),(3,5),(4,1),(4,2)],6)=>3 ([(0,4),(1,5),(2,5),(3,5),(4,1),(4,2),(4,3)],6)=>8 ([(0,4),(1,5),(2,5),(3,2),(4,1),(4,3)],6)=>17 ([(0,4),(1,5),(2,5),(4,1),(4,2),(5,3)],6)=>48 ([(0,2),(0,4),(1,5),(2,5),(3,1),(4,3)],6)=>8 ([(0,3),(1,5),(2,5),(3,4),(4,1),(4,2)],6)=>42 ([(0,1),(0,2),(0,3),(1,5),(2,4),(3,4),(4,5)],6)=>3 ([(0,2),(0,3),(2,5),(3,5),(4,1),(5,4)],6)=>42 ([(0,2),(0,3),(0,4),(2,5),(3,5),(4,5),(5,1)],6)=>8 ([(0,3),(0,4),(1,5),(2,5),(3,2),(4,1)],6)=>7 ([(0,2),(0,3),(1,5),(2,4),(3,1),(3,4),(4,5)],6)=>10 ([(0,5),(2,4),(3,2),(4,1),(5,3)],6)=>132 ([(0,3),(0,4),(1,5),(3,5),(4,1),(5,2)],6)=>17 ([],0)=>1
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 tolerances of a finite lattice.
Let $L$ be a lattice. A tolerance $\tau$ is a reflexive and symmetric relation on $L$ which is compatible with meet and join. Equivalently, a tolerance of $L$ is the image of a congruence by a surjective lattice homomorphism onto $L$.
The number of tolerances of a chain of $n$ elements is the Catalan number $\frac{1}{n+1}\binom{2n}{n}$, see [2].
References
[1] Chajda, I., Zelinka, B. Tolerance relation on lattices MathSciNet:0360380
[2] Bandelt, H.-J. Tolerante Catalanzahlen MathSciNet:0725192
Code
def is_tolerance(t, L):
    # reflexive:
    if not all((e, e) in t for e in L):
        return False
    # symmetric:
    if not all((f, e) in t for e, f in t):
        return False
    # compatible:
    for (x, y), (z, u) in Subsets(t, 2):
        # join:
        if not (L.join(x, z), L.join(y, u)) in t:
            return False
        if not (L.meet(x, z), L.meet(y, u)) in t:
            return False
    return True

# extremely stupid code
def all_tolerances_iter(L):
    n = Subsets(Subsets(L, 2)).cardinality()
    if n > 2^15:
        raise ValueError("%s too large (%s)" % (L, n))
    for t0 in Subsets(Subsets(L, 2)):
        t = [tuple(x) for x in t0]
        t.extend((e, e) for e in L)
        t.extend((f, e) for e, f in t0)
        assert len(set(t)) == len(t)
        if is_tolerance(t, L):
            yield t

def all_tolerances(L):
    """
    sage: from sage.databases.findstat import _finite_lattices
    sage: [len(all_tolerances(L)) for L in _finite_lattices(6)]
    [2, 5, 13, 42, 13]
    """
    return list(all_tolerances_iter(L))

@cached_function
def statistic(L):
    return len(all_tolerances(L))

Created
Dec 13, 2021 at 11:51 by Martin Rubey
Updated
Dec 13, 2021 at 11:51 by Martin Rubey