This collection contains supplementary material for the following paper:¶

[1] E. Iurlano and G. R. Raidl: SAT-Based Search for Minwise Independent Families. (submitted)¶

The source code of the project can be downloaded from here

The following are the certifying instances for [1, Propositions 11, 13]. Readers interested in inspecting these objects find below a standalone feasibility checker:

In [6]:
#d,n,k;|G|=60,6,6;6
θ = [[2, 4, 5, 3, 6, 1], [2, 5, 1, 4, 6, 3], [4, 6, 1, 3, 2, 5], [2, 6, 1, 5, 3, 4], [3, 2, 1, 4, 5, 6],
    [5, 4, 1, 2, 3, 6], [4, 3, 1, 5, 6, 2], [6, 5, 2, 3, 4, 1], [4, 3, 2, 5, 1, 6], [6, 3, 2, 1, 5, 4]] # |θ|=10
G = [[1, 2, 3, 4, 5, 6], [5, 4, 2, 3, 6, 1], [6, 3, 4, 2, 1, 5], [4, 5, 6, 1, 2, 3], [2, 1, 5, 6, 3, 4], [3, 6, 1, 5, 4, 2]] # |G|=6

#d,n,k;|G|=60,6,5;6
θ = [[4, 5, 6, 1, 2, 3], [3, 4, 5, 2, 6, 1], [1, 3, 6, 2, 5, 4], [1, 3, 6, 4, 2, 5], [2, 4, 6, 3, 1, 5],
    [1, 2, 6, 5, 4, 3], [2, 5, 3, 6, 1, 4], [3, 6, 4, 5, 1, 2], [2, 3, 1, 6, 4, 5], [2, 5, 3, 1, 6, 4]] # |θ|=10
G = [[1, 2, 3, 4, 5, 6], [5, 4, 2, 3, 6, 1], [6, 3, 4, 2, 1, 5], [4, 5, 6, 1, 2, 3], [2, 1, 5, 6, 3, 4], [3, 6, 1, 5, 4, 2]] # |G|=6

#d,n,k;|G|=60,5,5;60
θ = [[1, 4, 3, 2, 5]] # |θ|=1
G = [[1, 2, 3, 4, 5], [1, 4, 2, 3, 5], [1, 3, 4, 2, 5], [1, 4, 3, 5, 2], [1, 5, 4, 3, 2], [1, 3, 5, 4, 2],
    [1, 5, 3, 2, 4], [1, 2, 5, 3, 4], [1, 3, 2, 5, 4], [1, 5, 2, 4, 3], [1, 4, 5, 2, 3], [1, 2, 4, 5, 3],
    [2, 1, 5, 4, 3], [2, 4, 1, 5, 3], [2, 5, 4, 1, 3], [2, 4, 5, 3, 1], [2, 3, 4, 5, 1], [2, 5, 3, 4, 1],
    [2, 3, 5, 1, 4], [2, 1, 3, 5, 4], [2, 5, 1, 3, 4], [2, 3, 1, 4, 5], [2, 4, 3, 1, 5], [2, 1, 4, 3, 5],
    [4, 1, 2, 5, 3], [4, 5, 1, 2, 3], [4, 2, 5, 1, 3], [4, 5, 2, 3, 1], [4, 3, 5, 2, 1], [4, 2, 3, 5, 1],
    [4, 3, 2, 1, 5], [4, 1, 3, 2, 5], [4, 2, 1, 3, 5], [4, 3, 1, 5, 2], [4, 5, 3, 1, 2], [4, 1, 5, 3, 2],
    [5, 1, 4, 2, 3], [5, 2, 1, 4, 3], [5, 4, 2, 1, 3], [5, 2, 4, 3, 1], [5, 3, 2, 4, 1], [5, 4, 3, 2, 1],
    [5, 3, 4, 1, 2], [5, 1, 3, 4, 2], [5, 4, 1, 3, 2], [5, 3, 1, 2, 4], [5, 2, 3, 1, 4], [5, 1, 2, 3, 4],
    [3, 2, 4, 1, 5], [3, 1, 2, 4, 5], [3, 4, 1, 2, 5], [3, 1, 4, 5, 2], [3, 5, 1, 4, 2], [3, 4, 5, 1, 2],
    [3, 5, 4, 2, 1], [3, 2, 5, 4, 1], [3, 4, 2, 5, 1], [3, 5, 2, 1, 4], [3, 1, 5, 2, 4], [3, 2, 1, 5, 4]] # |G|=60

#d,n,k;|G|=36,8,4;2
G = [[1, 2, 3, 4, 5, 6, 7, 8], [8, 7, 6, 5, 4, 3, 2, 1]] # |G|=2, exceptionally here considered as right-coset
θ = [[1, 2, 3, 4, 5, 6, 7, 8], [8, 5, 6, 7, 2, 3, 4, 1], [1, 6, 7, 3, 2, 4, 8, 5],
    [5, 2, 4, 8, 6, 7, 3, 1], [1, 4, 6, 5, 8, 3, 2, 7], [7, 8, 3, 2, 4, 6, 5, 1],
    [5, 1, 8, 7, 3, 4, 2, 6], [6, 3, 4, 2, 1, 8, 7, 5], [5, 1, 8, 3, 6, 4, 7, 2],
    [2, 6, 4, 7, 1, 8, 3, 5], [2, 6, 1, 5, 8, 4, 7, 3], [3, 8, 4, 7, 6, 1, 5, 2],
    [6, 2, 1, 5, 4, 3, 8, 7], [7, 4, 3, 8, 2, 1, 5, 6], [5, 7, 1, 3, 6, 4, 2, 8],
    [8, 6, 4, 2, 7, 1, 3, 5], [4, 3, 8, 1, 7, 6, 2, 5], [5, 7, 6, 2, 3, 8, 1, 4]] # |θ|=18, inferred from Na et al. 2023, Proposition 4.6(iii)

#d,n,k;|G|=48,8,4;24
θ = [[5, 8, 7, 2, 3, 6, 1, 4], [6, 5, 1, 4, 2, 3, 8, 7]] # |θ|=2
G = [[1, 2, 3, 4, 5, 6, 7, 8], [1, 5, 7, 2, 4, 3, 6, 8], [1, 4, 6, 5, 2, 7, 3, 8], [8, 7, 4, 3, 6, 5, 2, 1],
    [8, 6, 2, 7, 3, 4, 5, 1], [8, 3, 5, 6, 7, 2, 4, 1], [3, 6, 8, 1, 2, 7, 5, 4], [3, 2, 5, 6, 1, 8, 7, 4],
    [3, 1, 7, 2, 6, 5, 8, 4], [4, 5, 1, 8, 7, 2, 6, 3], [4, 7, 6, 5, 8, 1, 2, 3], [4, 8, 2, 7, 5, 6, 1, 3],
    [6, 4, 2, 7, 1, 8, 3, 5], [6, 1, 3, 4, 7, 2, 8, 5], [6, 7, 8, 1, 4, 3, 2, 5], [5, 3, 7, 2, 8, 1, 4, 6],
    [5, 8, 4, 3, 2, 7, 1, 6], [5, 2, 1, 8, 3, 4, 7, 6], [2, 8, 5, 6, 4, 3, 1, 7], [2, 4, 1, 8, 6, 5, 3, 7],
    [2, 6, 3, 4, 8, 1, 5, 7], [7, 1, 6, 5, 3, 4, 8, 2], [7, 3, 8, 1, 5, 6, 4, 2], [7, 5, 4, 3, 1, 8, 6, 2]] # |G|=24

#d,n,k;|G|=24,7,4;12
θ = [[7, 2, 5, 6, 3, 4, 1], [7, 6, 4, 3, 1, 5, 2]] # |θ|=2
G = [[1, 2, 3, 4, 5, 6, 7], [1, 2, 3, 5, 4, 7, 6], [3, 2, 1, 5, 4, 6, 7], [3, 2, 1, 4, 5, 7, 6],
    [6, 2, 7, 3, 1, 5, 4], [6, 2, 7, 1, 3, 4, 5], [7, 2, 6, 1, 3, 5, 4], [7, 2, 6, 3, 1, 4, 5],
    [5, 2, 4, 7, 6, 1, 3], [5, 2, 4, 6, 7, 3, 1], [4, 2, 5, 6, 7, 1, 3], [4, 2, 5, 7, 6, 3, 1]] # |G|=12

#d,n,k;|G|=24,6,4;24
θ = [[2, 3, 5, 1, 6, 4]] # |θ|=1
G = [[1, 2, 3, 4, 5, 6], [2, 1, 3, 4, 6, 5], [5, 6, 3, 4, 1, 2], [6, 5, 3, 4, 2, 1], [1, 2, 4, 3, 6, 5], [2, 1, 4, 3, 5, 6],
    [6, 5, 4, 3, 1, 2], [5, 6, 4, 3, 2, 1], [3, 4, 5, 6, 1, 2], [4, 3, 5, 6, 2, 1], [1, 2, 5, 6, 3, 4], [2, 1, 5, 6, 4, 3],
    [3, 4, 6, 5, 2, 1], [4, 3, 6, 5, 1, 2], [2, 1, 6, 5, 3, 4], [1, 2, 6, 5, 4, 3], [5, 6, 1, 2, 3, 4], [6, 5, 1, 2, 4, 3],
    [3, 4, 1, 2, 5, 6], [4, 3, 1, 2, 6, 5], [5, 6, 2, 1, 4, 3], [6, 5, 2, 1, 3, 4], [4, 3, 2, 1, 5, 6], [3, 4, 2, 1, 6, 5]] # |G|=24

#d,n,k;|G|=12,5,4;6 # Figure 2, right
θ = [[1, 4, 2, 3, 5], [5, 2, 4, 3, 1]] # |θ|=2
G = [[1, 2, 3, 4, 5], [1, 3, 2, 5, 4], [2, 3, 1, 4, 5], [2, 1, 3, 5, 4], [3, 1, 2, 4, 5], [3, 2, 1, 5, 4]] # |G|=6

#d,n,k;|G|=12,4,4;12 # Figure 2, left
θ = [[1, 3, 4, 2]] # |θ|=1
G = [[1, 2, 3, 4], [1, 3, 4, 2], [1, 4, 2, 3], [4, 3, 2, 1], [4, 2, 1, 3], [4, 1, 3, 2],
    [3, 4, 1, 2], [3, 1, 2, 4], [3, 2, 4, 1], [2, 1, 4, 3], [2, 4, 3, 1], [2, 3, 1, 4]] # |G|=1
Out[6]:
12-element Vector{Vector{Int64}}:
 [1, 2, 3, 4]
 [1, 3, 4, 2]
 [1, 4, 2, 3]
 [4, 3, 2, 1]
 [4, 2, 1, 3]
 [4, 1, 3, 2]
 [3, 4, 1, 2]
 [3, 1, 2, 4]
 [3, 2, 4, 1]
 [2, 1, 4, 3]
 [2, 4, 3, 1]
 [2, 3, 1, 4]
In [2]:
using Combinatorics

"""
Returns the composition of two permutations ‘outer‘ and ‘inner‘ which both are passed as lists.
"""
function apply_perm(outer, inner)
    return [outer[inner[j]] for j in 1:length(inner)]
end

"""
Returns the union over all k in ‘k_range‘ of all sets of semiordered patterns SOP(n,k).
"""
function gen_SOP_n_k_range(k_range, n)
    SOP = []
    for j in k_range
        tmp_cll = []
        for cmb_j in combinations(1:n, j)
            for idx in 1:length(cmb_j)
                copy_cmb_j = copy(cmb_j)
                el = cmb_j[idx]
                deleteat!(copy_cmb_j, idx)
                push!(tmp_cll, tuple([el; sort(copy_cmb_j)]...))
            end
        end
        sort!(tmp_cll)
        append!(SOP, tmp_cll)
    end
    return SOP
end

"""
Checks if the family ‘F‘ is ‘k‘-restricted minwise independent.
"""
function is_mw_indep(F, k)
    SOP = gen_SOP_n_k_range(2:k, length(F[1]))
    unmet = []
    is_valid = true
    for sop in SOP
        counter = 0
        for l in 1:length(F)
            if all([F[l][sop[1]] < F[l][sop[j]] for j in 2:length(sop)])
                counter += 1
            end
        end
        if counter != div(length(F), length(sop))
            push!(unmet, (sop, counter))
            is_valid = false
        end
    end
    is_valid == false && println("unmet multiplicity: ", unmet)
    return is_valid
end
Out[2]:
is_mw_indep
In [4]:
F = [apply_perm(offset,g) for offset in θ for g in G]
k=4; is_mw_indep(F, k)
Out[4]:
true
In [ ]:
In [ ]: