Events

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,

Title: Well-quasi-ordering and connectivity

Abstract: Connectivity systems provide an abstract framework for studying various connectivity notions on graphs, matroids, and other combinatorial structures. In joint work with Rutger Campbell, we prove a novel well-quasi-ordering result on certain connectivity systems which gives new excluded minor results in matroid theory and gives new proofs for several results in graph theory.

Title: Equivariant quasisymmetry

 Abstract: We introduce equivariant quasisymmetry, a version of quasisymmetry for polynomials in two sets of variables. Using this definition we define double fundamental polynomials and double forest polynomials, a quasisymmetric generalizations of the theory of double Schur and double Schubert polynomials, where the subset of noncrossing permutations play the role of $S_n$.This combinatorics is governed by the quasisymmetric flag variety, a new geometric construction which plays the role for equivariant quasisymmetry what the usual flag variety plays in the classical story.

In this talk, I will focus on the combinatorial aspect first, and with the remaining time discuss the geometrical implications.

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

Title:Evolution of random graph orders and their dimensions

Abstract: A poset is a set X equipped with a partial order. In this talk I will briefly review the literature of different models on random orders. Then we discuss a particular model called the random graph order. The random graph order is classical model to generate a random causal set, which was introduced in physics to model and analyse the space-time universe. 

We will focus on an open problem proposed by Erdos, Kierstad and Trotter on the evolution of the dimensions of random graph orders. This problem has been studied by Albert and Frieze, and by Erdos, Kierstad and Trotter around 1990. Better bounds on the dimensions were obtained by Bollobas and Brightwell in 1997, for “non-sparse” random graph orders. We study the last piece of the puzzle, in the bipartite case, by investigating “a transition phase” that was predicted to occur in the sparse regime by Bollobas and Brightwel, and we prove a negative result to their prediction. We expect that a similar phenomenon would occur in the nonbipartite case.

This talk is based on a collaborated work with Arnav Kumar.