Future students

Title: Complexity in linear multilevel programming

Abstract:Bilevel linear programming (BLP) is a generalization of linear programming (LP) in which a subset of the variables is constrained to be optimal for a second LP, called the lower-level problem. Multilevel linear programming (MLP) extends this further by replacing the lower-level LP with a BLP or even another MLP, up to some finite number of levels. MLP can be seen as a game-theoretic extension of LP where multiple decision makers with competing interests each have control over some subset of the variables in the problem. We discuss the computational complexity of solving MLP problems, including some recent results on the complexity of determining whether MLPs are unbounded (Rodrigues, Carvalho, and Anjos 2024). We will end with an interesting open problem about the complexity of determining unboundedness for a
special case of BLP.

Title:A mystery group action and the mystery statistic

Abstract: In 2010, B. Rhoades proved that promotion on rectangular standard Young tableaux together with the associated fake-degree polynomial shifted by an appropriate power, provides an instance of the cyclic sieving phenomenon. 

Motivated in part by this result, we show that we can expect a cyclic sieving phenomenon for m-tuples of standard Young tableaux of the same shape and the m-th power of the associated fake-degree polynomial, for fixed m, under mild and easily checked conditions. However, we are unable to exhibit an appropriate group action explicitly.
Put differently, we determine in which cases the mth tensor power of a character of the symmetric group carries a permutation representation of the cyclic group. 
To do so, we use a method proposed by N. Amini and P. Alexandersson, which amounts to establishing a bound on the number of border-strip tableaux. 

Finally, we apply our results to the invariant theory of tensor powers of the adjoint representation of the general linear group. In particular, we prove the existence of a statistic on permutations, which is equidistributed with the RSK-shape and invariant under rotation.

This is based on joint work with Per Alexandersson, Martin Rubey and Joakim Uhlin.

Title:The squish map and the SL_2 double dimer model

 Abstract: A plane partition, whose 3D Young diagram is made of unit cubes, can be approximated by a "coarser” plane partition, made of cubes of side length 2. Two such approximations can be obtained by "rounding up” or "rounding down” to the nearest cube. We relate this coarsening (or downsampling) operation to Young's squish map, introduced in earlier work. We exhibit a related measure-preserving map between the 2-periodic single dimer model on the honeycomb graph, and a particular instance of Kenyon's SL_2 double dimer model on a coarser honeycomb graph. This allows us to apply existing computations from the 2-periodic single dimer partition function to a portion of the parameter space of the the harder double dimer model. We also specialize our map and exhibit new criterion for the signed-tilability of a closed region on the honeycomb graph.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title: Towards generalized spectral determinacy of random graphs

Abstract: Wang and Xu (2006, 2017) discovered sufficient conditions for a graph to be uniquely characterized by the spectra of its adjacency matrix and of its complement graph. They conjectured that these conditions are satisfied with nonvanishing frequency, but this remains open and it was not clear what proof techniques could be used. I will present a new line of attack which approaches the problem as a question about random groups. This allows making connections to proof techniques from combinatorial random matrix theory. The results which I will present are in a toy case, but it is expected that the employed perspective will generalize.  

This talk is based on my paper “Cokernel statistics for walk matrices of directed and weighted random graphs” [Combinatorics, Probability and Computing (2025)]

Title:Odd-Ramsey numbers of complete bipartite graphs

Abstract: In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs ℋ, defined as the minimum number of colours needed to colour the edges of the complete graph so that every copy of a graph H in ℋ intersects some colour class by an odd number of edges. In recent joint work with Simona Boyadzhiyska, Shagnik Das, and Kaline Petrova, we focus on the odd-Ramsey numbers of complete bipartite graphs. First, using polynomial methods, we completely resolve the problem when ℋ is the family of all spanning complete bipartite graphs on n vertices. We then focus on its subfamilies. In this case, we establish an equivalence between the odd-Ramsey problem and a well-known problem from coding theory, asking for the maximum dimension of a linear binary code avoiding codewords of given weights. We then use known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs. 

Title: Quotient graphs and stochastic matrices

Abstract: Whenever graphs admit equitable partitions, their quotient graphs highlight the structure evidenced by the partition. It is therefore very natural to ask what can be said about two graphs that have the same quotient according to certain equitable partitions. This question has been connected to the theory of fractional isomorphisms and covers of graphs in well-known results that we briefly presents in these slides. We then depart to develop theory of what happens when the two graphs have the same symmetrized quotient, proving a structural result connecting this with the existence of certain doubly stochastic matrices. We apply this theorem to derive a new characterization of when two graphs have the same combinatorial quotient, and we also study graphs with weighted vertices and the related concept of pseudo-equitable partitions. Our results connect to known old and recent results, and are naturally applicable to study quantum walks.

Title: A Constant Factor Prophet Inequality for Subadditive Combinatorial Auctions

Abstract: In this talk, I will go through the paper of Correa and Cristi that appeared in STOC 2023. The paper proves a O(1) prophet inequality for online combinatorial auctions with subadditive buyers.

Their techniques involve the use of what they call a Random Score Generator (RSG for short), which is a distribution over prices of the items. Each buyer 'plays' an RSG. The algorithm samples a vector of prices of the items from this RSG for each buyer as they arrive, and assigns to them the set of items for which the sampled prices are larger than prices from another independent sample from the RSGs of all the buyers. A mirroring argument is used to bound the value of the allocation computed by their algorithm, and a novel fixed point argument is used to show the existence of RSGs that guarantee a good approximation.

In contrast to the O(log log m) prophet inequality covered previously in the CO reading group, the algorithm in this paper does not run in polynomial time, and does not involve posted prices. 

Title: Multiplicities of Eigenvalues in Symmetric Graph Matrices with Zero Entries for Non-Edges

Abstract: This talk will focus on the multiplicities of eigenvalues in symmetric matrices associated with simple graphs, where nonzero entries correspond to edges, and zero entries represent non-edges in the off-diagonal positions. We will discuss how the structural properties of graphs, particularly those of trees, impact their spectral characteristics, with a special emphasis on eigenvalue multiplicities. 

Title:Valuable partial orders

 Abstract: In the pre-seminar we will review Birkhoff's structure theory for finite distributive lattices and its consequences for the geometry of some algebraic varieties associated with lattices by Hibi. In the seminar itself we will look more closely at the geometry of these varieties, motivating the definition of an interesting class of partial orders and raising several open problems.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

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.