Set-defined graph classes: χ-boundedness meets tropical algebra

Prelegent(ci)

Tomáš Hons

Afiliacja

Charles University

Język referatu

angielski

Termin

15 października 2026 12:40

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

We study set-defined graph classes: hereditary classes whose vertices are assigned fixed-length numerical tuples, with adjacency determined solely by equality patterns among coordinates. These classes arise in structural graph theory, communication complexity, logic, and adjacency labeling schemes. We ask when they are χ-bounded. We prove a decomposition theorem which allows us to prove that all set-defined classes are fractionally χ-bounded. For classes consisting of all graphs realizable by a fixed Boolean rule on equality patterns, we prove a strong dichotomy: every such class is either polynomially χ-bounded or contains the class of D-dimensional shift graphs for some D. We provide an algorithm that, given a Boolean-function description of a full set-defined class, decides χ-boundedness of the class by reducing the problem to feasibility of tropical linear programs, and its correctness follows from a duality with winning strategies in mean-payoff games. Interestingly, this connection between χ-boundedness and tropical algebra also works in the other direction.

This is a joint work with Sarosh Adenwalla, Samuel Braunfeld, John Sylvester, and Viktor Zamaraev.