Unsourced multi-access protocols ensure that multiple users can transmit on the same physical resources without pre-allocation of resources to the different users. To avoid information loss caused by collision of messages transmitted simultaneously, we investigate how to use (adaptive) coding schemes that allow the concurrent transmission of coded messages stemming from different users with lossless reconstruction of the payloads.

The student should be proficient in communications engineering and coding theory, i.e., the following prerequisites (or similar) are minimal requirements:

• Channel Coding
• Nachrichtentechnik

Information theory and combinatorics are deeply intertwined. Beyond the use of combinatorics in coding theory and compression, there are many -sometimes surprising- connections.
One such connection is the use of graph entropy in combinatorial existence proofs.

This seminar topic is about explaining the proof technique introduced in [1] and [2] and applied in [3]. The goal is a tutorial-style paper with the focus on clear exposition through well chosen worked examples and visualizations.

[1] M. Fredman, and J. Komlós, On the Size of Separating Systems and Perfect Hash Functions, SIAM J. Alg. Disc. Meth., 5 (1984), pp. 61-68.

[2] J. Körner, Fredman-Komlós bounds and information theory, SIAM J. on Algebraic and Discrete Meth., 4(7), (1986), pp. 560–570.

[3] N. Alon, E. Fachini, and J. Körner, Locally Thin Set Families, Combinatorics, Probability and Computing, vol. 9 (Nov. 2000), pp. 481–488.