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 27

Kunal Duttar (University of Warsaw)

A Near-Optimal Constructive Algorithm for the \ell_2 Steinitz Problem

A classical result of Steinitz from 1913, answering an earlier  question of Riemann and Lévy, states that for any norm ∥⋅∥ in \R^d and  any set of vectors $v_1, \cdots, v_n \in \R^d$ whose sum is zero, there  exists an ordering of the vectors such that every partial sum along this  order is bounded by O(d). Steinitz's bound is tight up to constants in general, but for the \ell_2  norm, it has been conjectured that the best bound is O(\sqrt{d}). Almost  a century later, a breakthrough work of Banaszczyk gave a bound of  O(\sqrt{d}+\sqrt{\log n}) for the \ell_2 Steinitz problem, matching the  conjecture under the mild assumption that d≥Ω(logn). Banaszczyk's result  is non-constructive, and the previous best algorithmic bound was  O(\sqrt{d\log n}), due to Bansal and Garg (STOC 2017). Beginning with a brief history of the problem alongwith very recent  AI-related developments, I shall describe an efficient algorithm that  matches the conjectured O(\sqrt{d}) bound for the \ell_2 Steinitz  problem under the slightly worse, yet still polylogarithmic, condition  of d≥Ω(\log^7 n). As in prior work, our result extends to the harder  problem of \ell_2 prefix discrepancy. We employ the framework of obtaining the desired ordering via a discrete  Brownian motion, guided by a semidefinite program (SDP). To obtain our  results, we use the new technique of ``Decoupling via Affine Spectral  Independence'', proposed by Bansal and Jiang (STOC 2026) to achieve  substantial progress on the Beck-Fiala and Komlós conjectures, together  with a ``Global Interval Tree'' data structure that simultaneously  controls the deviations for all prefixes.  

Joint work with Agastya Vibhuti Jha and Haotian Jiang, to appear in  SODA.

November 10

Tim Seynnaeve (IM PAN)

TBA

TBA

November 24

Bartosz Naskręcki (Adam Mickiewicz University)

TBA

TBA

December 8

Thibaut Lemoine (Université de Strasbourg)

TBA

TBA

Past Talks:

October 13

Arvind Ayyer (Indian Institute of Science)

How large is the character degree sum compared to the character table sum for a finite group?

In 1961, Solomon proved that the sum of all the entries in the character table of a finite group does not exceed the cardinality of the group. We state a different and incomparable property here -- this sum is at most twice the sum of degrees of the irreducible characters. Although this is not true in general, it seems to hold for ``most'' groups. We establish the validity of this property for symmetric, hyperoctahedral and demihyperoctahedral groups. Using these techniques, we are able to show that the asymptotics of the character table sums is the same as the number of involutions in these groups. We will also derive generating functions for the character tables sum for these groups as infinite products of continued fractions. Time permitting, we will explain the situation of generalized symmetric groups as well, where something interesting happens.  

This is joint work with D. Paul and H. K. Dey (Alg. Comb., to appear).

October 6

Chaithra Pilakkat (TU Munich)

Root Multiplicities of BKM Lie Superalgebras and Graph-Coloring Invariants

Infinite-dimensional Lie superalgebras, particularly Borcherds–Kac–Moody (BKM) superalgebras, play an important role in mathematical physics, number theory, and representation theory. In this talk, we study root multiplicities of BKM Lie superalgebras through their denominator identities and derive explicit combinatorial formulas in terms of graph invariants associated with marked (quasi)Dynkin diagrams. A central notion in our approach is that of marked multi-colorings and their associated polynomials, which generalize chromatic polynomials and provide an effective framework for computing root multiplicities.

As part of this study, we introduce partially commutative Lie superalgebras (PCLSAs) as a tool for analyzing certain roots of BKM Lie superalgebras. We present a direct combinatorial proof of their denominator identity using ideas from Viennot’s heap theory. We also characterize the roots of PCLSAs and establish connections between their universal enveloping algebras and right-angled Coxeter groups, leading to explicit formulas for the corresponding Hilbert series.

This talk is based on joint work with Deniz Kus and R. Venkatesh.