Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych
Wydział Matematyki i Nauk Informacyjnych, Politechnika Warszawska
Kalendarz Środy, 10:15-11:45
Pinezka Gmach MiNI PW, Sala 431, ul. Koszykowa 75, Warszawa
Komputer Seminaria odbywają się stacjonarnie z transmisją na platformie MS Teams.
Mail Jeśli chcesz dołączyć do spotkania, to napisz do sekretarza seminarium.

Najbliższy referat
06.05.2026 Jarosław Grytczuk PW
Fair division of a matroid
\(\quad\)Let E be a finite set and suppose that each element of E is assigned a value (a nonnegative real number). The value of a subset X of E is then the sum of the values of elements of X. Two sets have nearly equal values if they are indeed equal or the smaller one is not less than the value of the other set with some element deleted. A partition of E is nearly fair if all parts have nearly equal values. It is not hard to see that such partition of E into any given number of parts always exists. Now suppose that E is a ground set of a matroid M of arboricity k (the set E has a partition into k independent sets). It is conjectured that a nearly fair partition of E into k independent sets always exists. The conjecture has been confirmed for many classes of matroids, but in general is open even in the case of k = 2. Our main result shows that, assuming validity of the above conjecture, the epistemic version of a more general conjecture holds, where we are given k arbitrary valuations of the set E, with natural modification of nearly fairness of the partition of E into independent sets. Joint work with Marcin Anholcer, Maciej Bartkowiak, and Bartłomiej Bosek
Zespół prowadzący