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.

-

-