KoKoKo – Koralm Kombinatorik Kolloquium

A partition of an integer $n$ is a finite sequence of positive integers $p_1 \geq p_2 \geq \cdots \geq p_k$ such that $n = p_1 + p_2 + \cdots + p_k$. We let $p(n)$ denote the number of partitions of $n$. For example, $p(4) = 5$ because there are five partitions of the integer $n = 4$:

In 1919, just one year before his death, Ramanujan discovered and proved some unexpected, and truly amazing, divisibility properties for the function $p(n)$. Since then, several mathematicians have studied $p(n)$ from different perspectives, trying to better understand these divisibility properties, especially from a combinatorial perspective. In the process, numerous "statistics" have been defined on partitions, including the rank and crank of a partition. In this talk, I will discuss this history in more detail, and then I will transition to some relatively new partition statistics, including the missing excludant (or mex) of a partition. I will discuss unexpected connections between this mex statistic and the crank, and then we will transition to some very recent work of Blecher and Knopfmacher on partition fixed points which, unbeknownst to them, is very closely connected to the crank and mex statistics. We will close by generalizing this concept of partition fixed points and show how this new family of functions naturally connects with generalized versions of the aforemen- tioned partition statistics. This is joint work with Brian Hopkins (St. Peter’s University), Dennis Stanton (University of Minnesota), and Ae Ja Yee (Penn State University).

We continue the enumeration of plane lattice walks with small steps avoiding the negative quadrant, initiated by Bousquet-Mélou in 2016. We solve in detail a new case, namely the king model where all eight nearest neighbour steps are allowed. The associated generating function satisfies an algebraicity pheonomeon: it is the sum of a simple, explicit $D$-finite series (related to the number of walks confined to the first quadrant), and an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou, 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of degree up to 216. This is joint work with Mireille Bousquet-Mélou.

We investigate rectangulations that avoid $\top$-like patterns -- the pattern ⊤ and its rotations. For every combination of such patterns, we enumerate the respective aviodance class. In particular, we show that $\top$-avoiding generic rectangulations are in bijection with several classes of inversion sequences, among them $I(010, 110, 120, 210)$ and $I(011, 201)$: this provides a proof for the conjecture (Yan and Lin, 2019) that these classes are enumerated by the same sequence. Joint work with Michaela Polley.

Banderier and Flajolet did a thorough study of the enumeration of four types of directed lattice paths (walks, bridges, meanders, and excursions), where they derived generating functions for each type of path using the kernel method. In recent years, a further family of lattice paths has started to be considered by lattice path combinatorialists: paths which start and end on the $x$-axis, are allowed within some region below the $x$-axis but need to stay above a negative level $t$ for a given $t\in\mathbb{N}$. The $k_t$-Dyck paths with negative boundary have been the subject of a number of studies, Motzkin paths with negative boundary, apart from special cases, have not yet been studied. This talk will explore, how one can derive the enumerative generating function for generalized Motzkin paths with negative boundary by using the kernel method.

Sidorenko’s conjecture can be formulated as "Let $H$ be a bipartite graph, and $\rho \in [0, 1]$. Of all the graphs with edge density $\rho$, the graph(-limit) obtained by picking edges uniformly at random minimizes the homomorphism density of $H$." This conjecture, first formulated in 1991 by Sidorenko, has received considerable attention over the last decades, and yet remains open in the general case. It was shown recently [Blekherman, Raymond, Singh, Thomas, 2020] that sums-of-squares in Razborov’s flag algebra are not strong enough to prove even small, known cases of the conjecture. To circumvent this, we introduce a novel kind of (Lie-)derivation of flags. Due to their combinatoric nature, we can use them to systematically gain knowledge on global minimizers of problems in extremal graph theory. We combine them with the flag algebra method to find new proofs for various cases of Sidorenko’s conjecture.

The distance-2 graph of a graph has edges between vertices that have distance 2 in the original graph. In this talk we ask: What are the graphs whose distance-2 graphs are 2-regular? We provide a complete and explicit characterization, rounding off with a few other results and a discussion of the corresponding counting sequences.

For a positive integer $n$, an $n$-Nakayama algebra $A$ is a finite-dimensional algebra over some field $\mathbb{F}$ that can be constructed as a quotient algebra $A = \mathbb{F}Q / I$, where $Q$ is a linear or cyclic quiver on $n$ vertices (i.e., $0 \to 1 \to \cdots \to n-1$ or $0 \to 1 \to \cdots \to n-1 \to 0$), $\mathbb{F}Q$ is the corresponding path algebra, and $I$ is a suitable two-sided ideal. A quantity that is particularly interesting for algebraists is the global dimension of $A$, which is defined as the maximal projective dimension of a simple module of $A$.

There is a well-known bijection that maps a "linear" $n$-Nakayama algebra to a Dyck path. Under this correspondence, the simple modules relevant for determining the global dimension of $A$ are mapped to even-parity integer points on and under the Dyck path. From this representation, their dimensions can be determined following a simple recursive scheme. Intriguingly, experiments suggest that the global dimension follows the same distribution as the height of Dyck paths -- for which we do not yet have a proper explanation.

In this talk we consider the global dimension from a purely combinatorial point of view. After walking through known results, we discuss the evidence for our conjecture linking path height and global dimension. In particular, we present a hand full of strategies that have not (yet) led to a successful proof.

Sums of powers of cotangents of the form

have been studied in various contexts in the mathematical literature, like number theory and topology. We give an explicit elementary evaluation of these sums in terms of certain integer valued polynomials with positive coefficients, whose combinatorial interpretation remains an open question.