Combinatorics and Discrete Probability Seminar
Abhishek Dhawan
UIUC
Balanced independent sets and colorings
Abstract: An independent set in a bipartite graph G = (X, Y, E) is balanced if it contains an equal number of vertices from each partition. A balanced coloring of G is a proper coloring of G such that each color class forms a balanced independent set. In this talk, we will discuss the recent extension of these definitions to multipartite hypergraphs. We establish bounds on the balanced independence number and balanced chromatic number of multipartite hypergraphs that are near-optimal as exhibited by the behavior of these parameters on random instances. This talk is partially based on joint work with Yuzhou Wang.
Monday March 31, 2025 at 3:00 PM in 1227 SEO