Research Technology Master Calendar

View Full Calendar

Graph Theory and Combinatorics Seminar

Event Type
Seminar/Symposium
Sponsor
Department of Mathematics
Location
Altgeld Hall 147
Date
Sep 30, 2025   1:00 - 2:00 pm  
Speaker
Annie Zeng
Contact
Abhishek Dhawan
E-Mail
adhawan2@illinois.edu
Views
13
Originating Calendar
Combinatorics Research Area Calendar

Speaker: Annie Zeng (UIUC)

Title: On the Structure of EFX Orientations on Graphs

Abstract: Fair division is the problem of allocating a set of items among agents in a fair manner. One of the most sought-after fairness notions is envy-freeness (EF), requiring that no agent envies another's allocation. In discrete settings, it may cease to exist, and envy-freeness up to any good (EFX) emerged as one of its strongest relaxations. The existence of EFX allocations is arguably the biggest open question within fair division. Christodoulou et al (2023) showed that EFX allocations always exist over a graph, where the vertices are the agents, the edges are the items, and each vertex only values incident edges. 

On the other hand, they showed NP-hardness for checking the existence of EFX orientations and asked for a characterization of graphs that exhibit EFX orientation regardless of the assigned valuations. We introduce the notion of strongly EFX orientable graphs -- graphs that have EFX orientations regardless of how much agents value the edges. We show a surprising connection between this property and the chromatic number $\chi(G)$ of the graph. In particular, we show that bipartite graphs are strongly EFX orientable, and those with $\chi(G) > 3$ are not strongly EFX orientable. We provide examples of strongly EFX orientable and non-strongly EFX orientable graphs of chromatic number 3 to prove tightness. Finally, we give a complete characterization of strong EFX orientability when restricted to binary valuations.

This talk is based on joint work with Ruta Mehta.

link for robots only