An upper bound on the sizes of multiset-union-free families. (English) Zbl 1336.05143
Summary: 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,B\in \mathcal{F}_1\) and \(C,D\in \mathcal{F}_2\) 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 R. Urbanke and Q. Li [“The zero-error capacity region of the 2-user synchronous BAC is strictly smaller than its Shannon capacity region”, in: Information Theory Workshop, 22–26 June 1998, Killarney, Ireland. Piscataway, NJ: IEEE. 61 (1998; doi:10.1109/ITW.1998.706434)].
MSC:
| 05D05 | Extremal set theory |
| 05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |
| 94A15 | Information theory (general) |
References:
| [1] | B. Lindström, {\it Determination of two vectors from the sum}, J. Combin. Theory, 6 (1969), pp. 402-407. · Zbl 0169.32001 |
| [2] | H. van Tilborg, {\it An upper bound for codes in a two-access binary erasure channel (Corresp.)}, IEEE Trans. Inform. Theory, 24 (1978), pp. 112-116. · Zbl 0371.94036 |
| [3] | T. Kasami and S. Lin, {\it Bounds on the achievable rates of block coding for a memoryless multiple-access channel}, IEEE Trans. Inform. Theory, 24 (1978), pp. 187-197. · Zbl 0369.94013 |
| [4] | E. J. Weldon, {\it Coding for a multiple-access channel}, Inform. Control, 36 (1978), pp. 256-274. · Zbl 0387.94008 |
| [5] | T. Kasami, S. Lin, V. K. Wei, and S. Yamamura, {\it Graph theoretic approaches to the code construction for the two-user multiple-access binary adder channel}, IEEE Trans. Inform. Theory, 29 (1983), pp. 114-130. · Zbl 0519.94003 |
| [6] | P. C. van den Braak and H. van Tilborg, {\it A family of good uniquely decodable code pairs for the two-access binary adder channel}, IEEE Trans. Inform. Theory, 31 (1985), pp. 3-9. · Zbl 0575.94010 |
| [7] | S. I. Bross and I. F. Blake, {\it Upper bound for uniquely decodable codes in a binary input N-user adder channel}, IEEE Trans. Inform. Theory, 44, (1998), pp. 334-340. · Zbl 0906.94012 |
| [8] | R. Urbanke and Q. Li, {\it The zero-error capacity region of the 2-user synchronous BAC is strictly smaller than its Shannon capacity region}, in proceedings of the Information Theory Workshop, 1998. |
| [9] | R. Ahlswede and V. B. Balakirsky, {\it Construction of uniquely decodable codes for the two-user binary adder channel}, IEEE Trans. Inform. Theory, 45 (1999), pp. 326-330. · Zbl 0947.94009 |
| [10] | M. Mattas and P. R. J. Österg\aard, {\it A new bound for the zero-error capacity region of the two-user binary adder channel}, IEEE Trans. Inform. Theory, 51 (2005), pp. 3289-3291. · Zbl 1310.94072 |
| [11] | T. M. Cover and J. A. Thomas, {\it Elements of Information Theory}, Wiley, NewYork, 1991. · Zbl 0762.94001 |
| [12] | N. Alon and J. H. Spencer, {\it The Probabilistic Method}, Wiley, 2004. · Zbl 1333.05001 |
| [13] | F. MacWilliams and N. Sloane, {\it The Theory of Error Correcting Codes}, Elsevier, NewYork, 1977. · Zbl 0369.94008 |
| [14] | N. Alon, {\it On the density of sets of vectors}, Discrete Math. 46 (1983), pp. 199-202. · Zbl 0514.05003 |
| [15] | D. Slepian, and J. K. Wolf, {\it A coding theorem for multiple access channels with correlated sources}, Bell Systems Technical J., 52 (1973), pp. 1037-1076. · Zbl 0273.94010 |
| [16] | R. Ahlswede, and J. Korner, {\it Source coding with side information and a converse for degraded broadcast channels}, IEEE Trans. Inform. Theory, 21 (1975), pp. 629-637. · Zbl 0315.94016 |
| [17] | A. D. Wyner and J. Ziv, {\it The rate-distortion function for source coding with side information at the decoder}, IEEE Trans. on Inform. Theory, 22 (1976), pp. 1-10. · Zbl 0324.94010 |
| [18] | F. M. J. Willems, {\it Information Theoretical Results for the Discrete Memoryless Multiple Access Channel}, PhD dissertation, Katholieke Universiteit Leuven, Belgium, 1982. |
| [19] | A. D. Wyner, {\it The common information of two dependent random variables}, IEEE Trans. Inform. Theory, 21 (1975), pp. 163-179. · Zbl 0299.94014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
