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

DOI10.1137/15M1021118MaRDI QIDQ2808160zbMATH OpenOpenAlexFDO

Authors Or Ordentlich, Ofer Shayevitz

Publication date 26 May 2016

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• A Coding Theorem for Multiple Access Channels With Correlated Sources
• 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
• An upper bound for codes in a two-access binary erasure channel (Corresp.)
• Bounds on the achievable rates of block coding for a memoryless multiple-access channel
• Coding for a multiple-access channel
• Construction of uniquely decodable codes for the two-user binary adder channel
• Determination of two vectors from the sum
• Graph theoretic approaches to the code construction for the two-user multiple- access binary adder channel
• On the density of sets of vectors
• Source coding with side information and a converse for degraded broadcast channels
• The common information of two dependent random variables
• The probabilistic method
• The rate-distortion function for source coding with side information at the decoder
• Upper bound for uniquely decodable codes in a binary input N-user 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)