Events

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. 

Title: Entropy and the growth rate of universal covering trees

Abstract:This work studies the relation between two graph parameters, rho and Lambda. For an undirected graph G,  rho(G) is the growth rate of its universal covering tree, while Lambda(G) is a weighted geometric average of the vertex degree minus one, corresponding to the rate of entropy growth for the non-backtracking random walk (NBRW). It is well known that rho >= Lambda for all graphs, and that graphs with rho = Lambda exhibit some special properties. In this work we derive an easy to check, necessary and sufficient condition for the equality to hold. Furthermore, we show that the variance of the number of random bits used by a length l NBRW is O(1) if rho = Lambda and Omega(l) if rho > Lambda. As a consequence we exhibit infinitely many non-trivial examples of graphs with rho = Lambda.

Joint work with Idan Eisner, Tel-Hai College, Israel.

Title: New perspectives on quasisymmetry via divided differences, flag varieties, etc.

 Abstract: In this talk we will introduce a new combinatorial approach to understanding quasisymmetric polynomials via a quasisymmetric analogue of "divided differences". The resulting combinatorial theory is paired with a geometric theory that closely follows the classical development of Schubert calculus and Schubert varieties. Next week Nantel Bergeron will continue with the torus-equivariant story.

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

Title: A New Complexity Analysis of Primal-Dual Interior-Point Methods with Applications to Hyperbolic Cone Programming

Abstract: Primal-dual interior-point methods stand at the forefront of convex optimization, distinguished by their theoretical efficiency and practical robustness. After presenting the fundamental 
structure of these algorithms, I will introduce a complexity measure for a large family of primal-dual algorithms. A consequence of the new analyses of this complexity measure is a substantial improvement of the iteration 
complexity bounds for these primal-dual algorithms on hyperbolic cone programming problems.

This talk is based on joint work with Joachim Dahl and Lieven Vandenberghe.