An Upper Bound on the Sizes of Multiset-Union-Free Families

2014/12/29 by Ordentlich, Or, Shayevitz, Ofer
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1412.8415

Abstract

Let F₁ and F₂ be two families of subsets of an n-element set. We say that F₁ and F₂ are multiset-union-free if for any A,B∈ F₁ and C,D∈ F₂ the multisets A\uplus C and B\uplus D are different, unless both A = B and C= D. We derive a new upper bound on the maximal sizes of multiset-union-free pairs, improving a result of Urbanke and Li.

Related

• Maximum union-free subfamilies
• Union-Free Families of Subsets
• On the number of union-free families
• Partition-free families of sets
• Large B_d-free and union-free subfamilies