Events

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: 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: 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: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: 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: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: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: Cayley incidence graphs

Abstract: Evra, Feigon, Maurischat, and Parzanchevksi defined Cayley incidence graphs (which they refer to as Cayley bigraphs), a class of biregular graphs used to construct bipartite expander graphs. These graphs are defined using a group G and a set of cells satisfying certain properties. Alternatively, they can be described as the incidence graphs of uniform and regular linear hypergraphs with a group G acting regularly on the vertices. In this talk, I will explore some basic properties of Cayley incidence graphs, as well as their connections to other combinatorial objects such as designs, coset geometries, and difference sets.

This talk is based on joint work with Arnbjörg Soffía Árnadóttir, Alexey Gordeev, Sabrina Lato, and Tovohery Randrianarisoa.

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: Combinatorial interpretation of the coefficients of the causal set theory d'Alembertian

 Abstract: Causal set theory is an approach to quantum gravity where the  underlying spacetime is a locally finite poset.  This opens up many interesting combinatorial questions on posets that are either useful to the physics or that are asked by the physics but wouldn't necessarily be asked from a purer perspective.  This talk is about one of the latter questions. Glaser gave a formula for the causal set theory analogue of the d'Alembertian in general dimension (growing out of previous work of Sorkin, Benincasa and Dowker, and Dowker and Glaser).  The formula

contains integer coefficients.  Who can resist trying to find something that they count -- not me! -- so I will tell you about such a something.

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