Combinatorics and Interactions

Combinatorics and Interactions is an initiative that aims to foster interactions between researchers from various areas of mathematics (and physics) by focusing on topics that connect algebraic and enumerative combinatorics with other fields, such as representation theory, probability, enumerative geometry, integrable systems, and more.

The talks take place on Tuesdays 2 pm at the Instytut Matematyczny PAN Kraków (ul. Św. Tomasza 30/7, III floor)

Organized by Maciej Dołęga (IM PAN Kraków), Divya Setia (IM PAN Kraków), and  Jacinta Torres (Jagiellonian University).

Upcoming Talks:

October 13

Arvind Ayyer (Indian Institute of Science)

TBA

TBA

October 6

Chaithra Pilakkat (TU Munich)

TBA

TBA

Past Talks:

June 16

Álvaro Gutiérrez (University of Bristol)

Plethystic lifts of 𝑞-binomial identities

Every combinatorial formula has its 𝑞-analogue, often involving 𝑞-binomials. But some 𝑞-analogues seem to open a new world of finer and richer combinatorics, whereas others obscure the beauty of the original formula. On the other hand, 𝑞-binomials are a tool to study an instance of the problem of plethysm, but which 𝑞-binomial identities reflect a deeper property of plethysms? We develop a framework to give a partial answer to this question.

Secretly, we will be presenting progress towards a categorification of quantum 𝖘𝖑₂ joint with Á. Martínez, M. Szwej, and M. Wildon.

June 2

Clément Legrand (Jagiellonian University)

Dirac's theorem and the switch geometry of perfect matchings

Dirac's theorem states that all n-vertex graphs with minimum degree n/2 contain a perfect matching. This is tight and graphs with minimum degree cn are more generally called c-Dirac graphs. In fact, a phase transition occurs at c=1/2: c-Dirac graphs with c ≥ 1/2 contain many perfect matchings, that are everywhere in G.

With Ross Kang, we give a new understanding of this phase transition by describing how the perfect matchings of a Dirac graph cluster. More precisely, we analyse the geometrical properties of the space of perfect matchings of G, endowed with the graph metric such that perfect matchings differing on at most k edges are at distance one. For any fixed k, we pinpoint sharp thresholds at which this space is shattered into exponentially many components, becomes connected, or becomes an expander. For k≥3, these thresholds concentrate around c=1/2. Finally, we also show that the threshold at which this space exhibits positive minimum degree is related to the notorious Caccetta-Häggkvist conjecture.

May 19

Jerzy Weyman (Jagiellonian University)

Categorification of Giambelli and Jacobi—Trudi formulas

In this talk I will discuss recent joint work with Steven Sam and Keller VandeBogert on Jacobi-Trudi and Giambelli formulas in the theory of symmetric functions. They express the Schur functions as determinants of matrices whose entries are elementary (resp. hook) symmetric functions.

For each of these formulas we will describe a categorification, i.e. a complex of Schur functors realizing the formula by taking its Euler characteristic. For Jacobi-Trudi formulas such constructions were given by Akin and Zelevinsky. Our construction is different. For Giambelli formulas this construction is new. Both our constructions come from sheafified versions of EFW complexes giving examples of pure resolutions in commutative algebra.

May 19

Zbiginiew Wojciechowski (TU Dresden)

Infinite sequences via Lie algebra actions for oligomorphic groups

Many integer sequences arise by counting G-orbits on the set of n-element subsets of a set X, for a group G acting on X. For finite X, Stanley proved that these finite sequences increase towards the middle using an action of the Lie algebra sl2. For infinite sets X, and hence infinite sequences, Cameron provided an argument for monotonicity. He first identifies orbits with a vector space basis of a certain commutative k-algebra H*, called the orbit algebra. He then considers the operator which forms the product with the constant 1-function on X, and proves its injectivity. In this paper, we generalize Stanley's approach to oligomorphic groups, and in particular extend Cameron's operator to a full sl2-action on H*. Most crucially, we define for every oligomorphic permutation group G the X-th tensor power of the standard representation of the general linear Lie algebra generalizing work of Entova-Aizenbud. This space carries natural commuting actions of G and gl_n, the latter depending on a Harman–Snowden measure on G. In the case d = 2, Cameron's result implies that H* decomposes into a direct sum of Verma modules, which provides a representation-theoretic explanation for monotonicity. A highlight of the talk is an sl2-representation whose weight space dimensions are given by the Fibonacci numbers.

May 5

Sam Mellick (Jagiellonian University)

The Ideal Poisson Voronoi tessellation

An exciting new stochastic geometric object has received attention recently. It is constructed in the following way: on an infinite graph, take a Bernoulli(p) random subset, and look at its Voronoi tessellation. Now consider the weak limit as p goes to zero. In favourable situations, there is a unique limiting tessellation. On the Euclidean lattice, the limit turns out to be trivial (one big cell). However, on d-regular trees, the limit is nontrivial and admits an explicit description.

April 28

Maciej Dołęga (IM PAN)

Gentle introduction to topological recursion

This talk, as the title suggests, is intended to be an introduction to a very powerful technique to compute various interesting invariants known as topological recursion. Topological recursion, introduced by Eynard and Orantin in 2007, is an algorithm that takes two meromorphic functions as input and, for each pair of nonnegative integers (g,n) (since we are going to count things, you can already start thinking that g is the genus of some interesting object and n is the number of special boundaries on this object), produces certain differential forms. For interesting choices of the initial meromorphic functions, these differential forms, when expanded in some basis, yield various geometric/combinatorial invariants, such as combinatorial maps, Hurwitz numbers, Gromov-Witten invariants, Weil-Petersson volumes of some moduli spaces, and many more! We will show many examples, explain the main philosophy behind this concept, do some computations, and discuss various interesting problems in this area.

April 14

Viola Conte (University of Padova)

Species with Potential from Orbifold Surfaces and Their Representations

Given a colored triangulation of a surface with marked and orbifold points, one can associate a weighted quiver with a modulating function, giving rise to a species with potential (SP). Flips of triangulations (combinatorial operations on arcs) correspond to SP-mutations, extending the notion of quiver mutation.

In this talk, I will introduce these constructions and present a representation-theoretic interpretation of SP-mutation. I will then describe a bijection between indecomposable representations and certain curves on surfaces.

This is joint ongoing work with Prof. Labardini Fragoso and forms part of my PhD research

March 31

Gaëtan Borot (Humboldt University)

Gaussian free field fluctuations in discrete Coulomb gases and random lozenge tilings

Random lozenge tiling models on a large class of surfaces can be mapped to an ensemble of N particles sitting on integers and strongly repelling each other. N is proportional to the size of the surface. In this ensemble one can derive as N -> infinity the law of large number and under suitable conditions, a central limit theorem for the macroscopic fluctuations of particles. The covariance can in fact be related to the Green function on the spectral curve of the model, which is constructed from the model in an algebraic way. This result can in turn be upgraded to prove Gaussian free field fluctuations on the whole liquid region of the surface (Kenyon-Okounkov conjecture).  The talk is based on joint work 2601.16377 with Vadim Gorin and Alice Guionnet.

March 17

Bárbara Muniz (Jagiellonian University)

The structure and geometry of the tableau algebra

We will study the variety associated to the tableau algebra. We classify its maximal ideals, describe the topology of its maximal spectrum and construct a toric embedding. This variety appears, via work of Gonciulea–Lakshmibai, as a toric degeneration of certain partial flag varieties. As an application, we enumerate the corresponding Plücker relations.

March 3

Sylwia Antoniuk (Adam Mickiewicz University)

On constructing small subgraphs in the budget-constrained random graph process

The random graph process on vertex set $[n]$ is a sequence of graphs $(G_0, G_1, \ldots, G_M)$, $M={n\choose 2}$, all on vertex set $[n]$, where $G_0$ is the empty graph and, for each $i\in[M]$, an edge $e_i$ is chosen uniformly at random from ${[n]\choose 2}\setminus E(G_{i-1})$ before setting $G_i := G_{i-1}\cup\{e_i\}$.

We study the budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli, where each time an edge is offered through the random graph process, we must irrevocably decide whether to ``purchase'' this edge or not, with our goal being to construct a graph which satisfies some property within a given time $t$ and while purchasing at most $b$ edges. We consider the problem of constructing graphs containing certain fixed small subgraphs.

We provide an optimal strategy for building a graph which contains a copy of $K_4$. This resolves a problem raised by I{\v{l}}kovi{\v{c}}, Le\'{o}n and Shu.More generally, we obtain analogously tight results for containing a wheel of any fixed size, or a graph consisting of a tree plus one additional universal vertex.We also tackle the problem of constructing graphs containing a copy of~$K_5$, obtaining both lower and upper bounds on the optimal budget, though a gap remains in this case.

February 17

Ugo Giocanti (Jagiellonian University)

Structure of highly symmetric graphs : planarity, minor exclusion and more

A graph is quasi-transitive if the action of its automorphism group on its vertex set has finitely many orbits. Quasi-transitive graphs generalize in particular Cayley graphs and vertex/edge-transitive graphs. In this presentation, I will give an overview of different recent structural results on quasi-transitive graphs. In the case of planar quasi-transitive graphs, I will present a generalization of a theorem of Droms (2006) allowing to decompose such a graph into simpler pieces. I will also present a structure theorem for quasi-transitive graphs which more generally exclude a finite or infinite graph as a minor, which can be seen as a symmetric-friendly version of Robertson Seymour’s structure theorem, and present some of its applications. If the time permits, I will also mention a number of recent related questions and results on more general classes of quasi-transitive graphs that recently attired a lot of attention inCoarse graph theory.

Some of the works this talk is based on are joint with Louis Esperet and Clément Legrand-Duchesne.

February 3

Jacinta Torres (Jagiellonian University)

The branching models of Kwon and Sundaram via flagged hives

We prove a bijection between the branching models of Kwon and Sundaram, conjectured previously by Lenart-Lecouvey. To do so, we use a symmetry of Littlewood-Richardson coefficients in terms of the hive model. Along the way, we obtain a new branching model in terms of flagged hives.

December 23

Jakub Kozik (Jagiellonian University)

Alon-Tarsi index of regular graphs

The problem of list edge coloring of regular graphs provides a rare opportunity to compare two powerful approaches—probabilistic and algebraic—within the context of a major open question in graph theory. The central List Edge Coloring Conjecture, which states that the chromatic index of a graph equals its list chromatic index, remains unresolved. However, two important asymptotic results have been obtained using methods from these distinct fields. The better-known result, first proved by Kahn (1996) and later refined by Molloy and Reed (2000), uses the semi-random method. The less familiar approach, due to Häggkvist and Janssen (1997), relies on the Combinatorial Nullstellensatz and the Alon–Tarsi method. In this talk, we revisit the second technique, explore how it can be adapted to colorings along natural decompositions of a graph into bipartite subgraphs, and examine its connection to the Alon–Tarsi Conjecture.

December 16

Piotr Pokora (University of the National Education Commission)

Interactions between algebra and combinatorics: variations on Terao's freeness conjecture

The main aim of my talk is to discuss the combinatorial aspects of Terao's freeness conjecture, which predicts that the homological properties of the module of syzygies associated with hyperplane arrangements are governed by strong combinatorics, i.e. intersection posets. I will also discuss recent developments in Ziegler pairs that could be crucial in disproving the conjecture.

November 25

Michał Szwej (University of Bristol)

Characteristic-free lifts of q-binomial identities

The q-binomial coefficients refine the usual binomial coefficients and admit many combinatorial interpretations: for example, \binom{n+k}{k}_q is the generating function for the weights of k-subsets, the generating function for partitions fitting inside an n x k rectangle, and the number of k-dimensional subspaces of F_q^{n+k}. They also play a central role in the representation theory of SL_2(C): the character theory immediately gives a lift the q-binomial identities to isomorphisms of SL_2(C)-representations. For instance, the symmetry \binom{n+k}{k}_q = \binom{n+k}{n}_q lifts to Hermite reciprocity Sym^n(Sym^k C^2) \cong Sym^k(Sym^n C^2). 

Over a field of arbitrary characteristic, however, character theory no longer determines whether such algebraic lifts exist. In this talk I will describe new characteristic-free lifts of several q-binomial identities and explain why symmetric polynomials continue to play a central — though now subtler — role. I will conclude with a collection of conjectures and open problems arising from this characteristic-free perspective.

Joint work with Álvaro Gutiérrez, Álvaro L. Martínez, and Mark Wildon

November 18

Mikołaj Frączyk (Jagiellonian University)

Groups and sparse factors of iid

Certain problems in measured group theory and quantitative topology lead us to consider sparse factor of iid subsets of graphs. 

A factor of iid subset of a graph is any subset that can be selected by a local algorithm. Local algorithms are the mathematical models of distributed computing. At each vertex of the graph we run an independent instance of a probabilistic algorithm and any two instances are only allowed communication along the vertices of the graph. Simplest examples of such a set is a Bernoulli random subsets where each point is selected independently with probability p>0. In my talk I will explain some unexpectedly strong constraints on the geometry of sparse subsets which can be distinguished by such an algorithm.

November 4

Piotr Śniady (IM PAN Toruń)

From visualization to computation: Representation theory in random RSK

The Robinson-Schensted-Knuth (RSK) correspondence on random inputs exhibits beautiful asymptotic phenomena, most famously the Vershik-Kerov-Logan-Shepp limiting shape theorem and its connections to random matrix theory. Motivated by new visualization techniques, we explore how representation-theoretic tools can produce explicit formulas for probabilistically natural quantities beyond the limiting shape. This talk illustrates how algebraic structure enables concrete probabilistic computations in random tableaux theory.

October 28

Kamil Szpojankowski (Warsaw University of Technology)

Free Askey--Wilson functionals and geometric last passage percolation

I will introduce free Askey--Wilson functionals and show how they provide a new description of the stationary measure of geometric last passage percolation. This perspective makes it possible to derive explicit generating functions and to analyze their asymptotics. As a result, we obtain the full phase diagram in the large-scale limit. I will also explain how this approach leads to a Poisson limit theorem. 

Based on joint work with Włodzimierz Bryc (University of Cincinnati) and Jacek Wesołowski (Warsaw University of Technology).

October 21

Yuze Luan (IM PAN Warsaw)

Hilbert scheme of points on a fat and nodal curve, and the colored knot homology

Using valuation theory, we construct a stratification of the punctual Hilbert scheme of points on a non-reduced and nodal singular curve, x^ay^b=0. Each stratum is isomorphic to a punctured affine plane to some power times an affine space, (C*)^m \times C^k. We consequently compute the Hilbert zeta function. As an application, we prove a variation of the colored Oblomkov-Rasmussen-Shende conjecture for the Hopf link, showing that the virtual Poincare polynomial is the row-colored link homology up to some change of variables. 

October 7

Divya Setia (IM PAN Kraków)

Graded representations of current Lie superalgebra sl(1|2)[t]

Lie superalgebras are generalizations of the Lie algebras introduced by Kac. Let g denote the Lie superalgebra and the current Lie superalgebra associated to g is denoted by g[t] := g ⊗ C[t], a class of infinite-dimensional Lie superalgebras, which carry a Z_{+}-grading induced by the grading of the polynomial algebra C[t]. Several mathematicians have attempted to derive results for graded representations of current Lie superalgebras analogous to the ones established for current Lie algebras.

In this talk, we will focus on the current Lie superalgebra sl(1|2)[t] and introduce the notion of local Weyl modules for sl(1|2)[t]. We have given a new combinatorial parametrization of the basis of the local Weyl module for sl(1|2)[t] by defining super POP’s. This helps us to derive the graded character formula of the local Weyl module for sl(1|2)[t]. The talk will conclude with a discussion of several open problems and possible directions for future research.