Maximum Intersecting Families of Submultisets: A Complete Solution over All Ranks and Exact Results at Fixed Rank
Abstract
Let M = {n 1 /x 1 , . . . , n k /x k } be a multiset with arbitrary (non-uniform) multiplicities. We determine the largest pairwise-intersecting family of submultisets in two settings. Over all ranks, the maximum is the sum of max w(S), w(S c ) over complementary pairs of supports, where w(S) = i∈S n i ; it is attained by a "weighted majority" family, and the natural family of all submultisets containing the most frequent element is optimal if and only if
At fixed rank j, the maximum is max F S∈F c j (S) over the maximal intersecting families F of subsets of {1, . . . , k}, where c j (S) counts rank-j submultisets with support exactly S; a dominance argument reduces the 2, 4, 12, 81 families for k = 2, . . . , 5 to 1, 2, 3, 7 undominated ones, giving exact formulas for k ≤ 5. We then study the set F (M ) of ranks at which the star (all submultisets containing the most frequent element) is not optimal. With R
R, and that R -1 ∈ F (M ) whenever n 3 ≥ 2; for k = 3, 4 we determine F (M ) completely (it is an interval). Computer evidence for k = 5, 6 supports the conjecture that F (M ) is always an interval. A final section gives an explicit symmetric chain decomposition of the poset of submultisets.
Related
BibTeX
@misc{k2026maximum,
title = {{Maximum Intersecting Families of Submultisets: A Complete Solution over All Ranks and Exact Results at Fixed Rank}},
author = {Sunitha K G and Girish K P},
howpublished = {HAL},
year = {2026},
month = nov,
url = {https://hal.science/hal-05846994v1},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Maximum Intersecting Families of Submultisets: A Complete Solution over All Ranks and Exact Results at Fixed Rank
AU - Sunitha K G
AU - Girish K P
PY - 2026
DA - 2026/11/01
PB - HAL
UR - https://hal.science/hal-05846994v1
AB - Let M = {n 1 /x 1 , . . . , n k /x k } be a multiset with arbitrary (non-uniform) multiplicities. We determine the largest pairwise-intersecting family of submultisets in two settings. Over all ranks, the maximum is the sum of max w(S), w(S c ) over complementary pairs of supports, where w(S) = i∈S n i ; it is attained by a "weighted majority" family, and the natural family of all submultisets containing the most frequent element is optimal if and only if At fixed rank j, the maximum is max F S∈F c j (S) over the maximal intersecting families F of subsets of {1, . . . , k}, where c j (S) counts rank-j submultisets with support exactly S; a dominance argument reduces the 2, 4, 12, 81 families for k = 2, . . . , 5 to 1, 2, 3, 7 undominated ones, giving exact formulas for k ≤ 5. We then study the set F (M ) of ranks at which the star (all submultisets containing the most frequent element) is not optimal. With R R, and that R -1 ∈ F (M ) whenever n 3 ≥ 2; for k = 3, 4 we determine F (M ) completely (it is an interval). Computer evidence for k = 5, 6 supports the conjecture that F (M ) is always an interval. A final section gives an explicit symmetric chain decomposition of the poset of submultisets.
ER -