Welcome to Combinatorics and Optimization

Title: Minimum spectral radius in a given class of graphs

Abstract: :  In 1986, Brualdi and Solheid posed the question of determining the maximum and minimum spectral radius of a graph within a given class of simple graphs. Since then, this problem has been extensively studied for various graph classes. In this talk, I will discuss two such classes: simple connected graphs with a given order and size, and simple connected graphs with a given order and dissociation number. This presentation is based on joint works with Sebastian Cioaba, Dheer Noal Desai, and Celso Marques.  

Title: A constant factor approximation for Nash social welfare with subadditive valuations, Part II

Abstract::Social welfare refers to a class of optimization problems where the goal is to allocate subsets of resources $\mathcal{I}$ among agents $\mathcal{A}$ (or people) such that maximizes the overall "happiness" of society in a fair and efficient manner. More specifically, each agent $i \in \mathcal{I}$ has an intrinsic \emph{valuation} function $v_i: 2^{\mathcal{I}}\rightarrow \mathbb{R}$, which is a monotone function with $v_i(\emptyset)=0$, and $v_i$ quantifies the intrinsic value for subsets of items $S\subseteq \mathcal{I}$.

Variations of allocation with different valuation and objective functions has been studied in different areas of computer science, economies, and game theory. In this talk we focus on the Nash social welfare welfare (NSW) problem; given an allocation $\mathcal{S}= (S_i)_{i\in \mathcal{A}}$ the goal is to maximize the geometric mean of agents valuations.

Unfortunately, Nash social welfare problem is NP-hard already in the case of two agents with identical additive valuations, and it is NP-hard to approximate within a factor better than 0.936 for additive valuations and $(1-\frac{1}{e})$ for submodular valuation. 

Moreover, the current best approximation factors of $\simeq 0.992$ for additive valuations and $(\frac{1}{4}-\epsilon)$ for submodular valuations were found by Barman et al (2018) and Garg et al. (2023), respectively.

In this talk, we present a sketch of the algorithm in recent work by Dobzinski et al., which proves the first constant-factor approximation algorithm (with a fairly large constant $\sim \frac{1}{375,000}$) for NSW problem with subadditive valuations accessible via demand queries.

Title: The pathwidth theorem for induced subgraphs

Abstract: We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. If time permits , we will also try to discuss the proof of the first result mentioned above.

Based on joint work with Maria Chudnovsky and Sophie Spirkl.