Events

Abstract:Twin-width is a notion introduced in 2020 by Bonnet, Kim, Thomassé and Watrigant  which provides a unified perspective on a range of important graph classes, encompassing both sparse and dense classes. Many graph classes ranging from planar graphs, H-minor-free graphs to proper interval graphs and graphs of bounded cliquewidth have bounded twin-width. This new perspective also allows us to establish powerful properties such as tractability of First-Order model checking on many graph classes and (polynomial) χ-boundedness in a unified way. Twin-width is now considered an important part of the toolbox for structural graph theory, algorithms design, logic on finite graphs and data structure.

Title: Jeu de Taquin for Mixed Insertion and a Problem of Soojin Cho

Abstract: 

Serrano (2010) introduced the shifted plactic monoid, governing Haiman's (1989) mixed insertion algorithm, as a type B analogue of the classical plactic monoid that connects jeu de taquin of Young tableaux with the Robinson–Schensted–Knuth insertion algorithm. Serrano proposed a corresponding definition of skew shifted plactic Schur functions. Cho (2013) disproved Serrano's conjecture regarding this definition, by showing that the functions do not live in the desired ring and hence cannot provide an algebraic interpretation of tableau rectification or of the corresponding structure coefficients. Cho asked for a new definition with particular properties. We introduce such a definition and prove that it behaves as desired. We also introduce the first jeu de taquin theory that computes mixed insertion. This is joint work with Oliver Pechenik.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm in MC 5417.

Abstract:In 1943, Hadwiger conjectured that every k-chromatic graph has a K_k-minor. While the cases k = 5 and k = 6 have been shown to be equivalent to the Four Colour Theorem, respectively by Wagner, and in seminal work by Robertson, Seymour and Thomas, the cases k at least 7 remain open. We show that any 7-chromatic graph has as a minor the complete graph K_7 with two adjacent edges removed, by extending work of Kawarabayashi and Toft and by proving a new edge-extremal bound. This improves Jakobsen’s result with two arbitrary edges removed. Joint work with Sergey Norin.

Abstract: The order dimension of a partially ordered set (poset), which is often difficult to compute, is a measure of its complexity. Dilworth proved that the dimension of a distributive lattice is the width of its subposet on its join-irreducible elements. We generalize this result by showing that the dimension of a semidistributive extremal lattice is the chromatic number of the complement of its Galois graph (see Section 3.5 of arXiv:2511.18540). We apply this result to prove that the dimension of the lattice of torsion classes of a gentle tree with n vertices is equal to n. No advanced background is required to follow the talk.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm in MC 5417.

Abstract: A central goal of quantum information theory is to determine the capacities of a quantum channel for sending different sorts of information.  I’ll highlight the new and fundamentally quantum aspects that arise in quantum information theory compared to the classical theory. These include the central role of entanglement, nonadditivity, and synergies between resources. I will also discuss some challenging open questions that we will have to solve to push the theory forward. 
 

Abstract: In this talk, we present sequential contracts under matroid constraints. In the sequential setting, an agent can take actions one by one. After each action, the agent observes the stochastic value of the action and then decides which action to take next, if any. At the end, the agent decides what subset of taken actions to use for the principal's reward; and the principal receives the total value of this subset as a reward. Taking each action induces a certain cost for the agent. Thus, to motivate the agent to take actions the principal is expected to offer an appropriate contract. A contract describes the payment from the principal to the agent as a function of the principal's reward obtained through the agent's actions. In this work, we concentrate on studying linear contracts, i.e. the contracts where the principal transfers a fraction of their total reward to the agent. We assume that the total principal's reward is calculated based on a subset of actions that forms an independent set in a given matroid. We establish a relationship between the problem of finding an optimal linear contract (or computing the corresponding principal's utility) and the so called matroid (un)reliability problem. Generally, the above problems turn out to be equivalent subject to adding parallel copies of elements to the given matroid. (Joint work with Jacob Skitsko and Yun Xing)

Abstract: We use a new combinatorial construction and a sign-reversing involution to simplify an alternating sum that arises naturally in intersection theory on moduli spaces of curves. In particular, it is well known that a product of ψ classes on the moduli space M₀,ₙ-bar, the most commonly studied compactification of the moduli space M₀,ₙ of choices of n distinct marked points on ℙ¹, is equal to a multinomial coefficient and has many natural combinatorial interpretations.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm in MC 5417.