Abstract: We will discuss the following natural-looking problem whose variants come up often in real life. The governing body of a university consists of one professor from each department. Some of the faculty members don't get along well and should not be selected together to this important committee. Assuming that each faculty member has at most $d$ other professor whom they cannot stand, how large should the departments be, so we can surely assemble an appropriate committee where all members get along with each other?
We formulate this problem in the language of graph theory and indicate three proofs for its solution: one combinatorial, one probabilistic, and one topological.

Tee / Kaffee / Gebäck
ab 16:45 Uhr
Arnimallee 3, Raum 006

-------------------------------

Koordinatorin: PD Dr. Barbara Baumeister

-------------------------------