An upper bound on the sizes of multiset-union-free families

DOI10.1137/15M1021118zbMATH Open1336.05143arXiv1412.8415OpenAlexW2963365260MaRDI QIDQ2808160FDOQ2808160

Authors: Or Ordentlich, Ofer Shayevitz 

Publication date: 26 May 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $mathcal{F}_1$ and $mathcal{F}_2$ be two families of subsets of an $n$-element set. We say that $mathcal{F}_1$ and $mathcal{F}_2$ are multiset-union-free if for any $A,Binmathcal{F}_1$ and $C,Dinmathcal{F}_2$ the multisets $AuplusC$ and $BuplusD$ 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.

Full work available at URL: https://arxiv.org/abs/1412.8415

Recommendations

• New bounds for union-free families of sets
• Extremal families containing no two sets and their union
• Large \(B_d\)-free and union-free subfamilies
• Best possible bounds concerning the set-wise union of families
• Maximum union-free subfamilies

zbMATH Keywords

additive combinatoricsbinary adder channelzero error capacity

Mathematics Subject Classification ID

Information theory (general) (94A15) Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The probabilistic method
• The rate-distortion function for source coding with side information at the decoder
• On the density of sets of vectors
• The common information of two dependent random variables
• Source coding with side information and a converse for degraded broadcast channels
• A Coding Theorem for Multiple Access Channels With Correlated Sources
• Determination of two vectors from the sum
• Graph theoretic approaches to the code construction for the two-user multiple- access binary adder channel
• A New Bound for the Zero-Error Capacity Region of the Two-User Binary Adder Channel
• A family of good uniquely decodable code pairs for the two-access binary adder channel
• Bounds on the achievable rates of block coding for a memoryless multiple-access channel
• An upper bound for codes in a two-access binary erasure channel (Corresp.)
• Coding for a multiple-access channel
• Upper bound for uniquely decodable codes in a binary input N-user adder channel
• Construction of uniquely decodable codes for the two-user binary adder channel

Cited In (7)

• Size-maximal symmetric difference-free families of subsets of \([n]\)
• Multiply union families in \(\mathbb{N}^n\)
• Extremal Uniquely Resolvable Multisets
• Union distinct families of sets, with an application to cryptography.
• Large \(B_d\)-free and union-free subfamilies
• Small maximally disjoint union-free families
• A note on the size of \(\mathscr{N}\)-free families

This page was built for publication: An upper bound on the sizes of multiset-union-free families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808160)