Combinatorial Theory

We build on recent work of Yeats, Courtiel, and others involving connected chord diagrams. We first derive from a Hopf-algebraic foundation a class of tree-like functional equations and prove that they are solved by weighted generating functions of two different subsets of weighted connected chord diagrams: arbitrary diagrams and diagrams forbidding so-called top cycle subdiagrams. These equations generalize the classic specification for increasing ordered trees and their solution uses a novel decomposition, simplifying and generalizing previous results. The resulting tree perspective on chord diagrams leads to new enumerative insights through the study of novel diagram classes. We present a recursive bijection between connected top-cycle-free diagrams with \(n\) chords and triangulations of a disk with \(n+1\) vertices, thereby counting the former. This connects to combinatorial maps, Catalan intervals, and uniquely sorted permutations, leading to new conjectured bijective relationships between diagram classes defined by forbidding graphical subdiagrams and imposing connectedness properties and a rich variety of other combinatorial objects. We conclude by exhibiting and studying a direct bijection between diagrams of size \(n\) with a single terminal chord and diagrams of size \(n-1\).Mathematics Subject Classifications: 05A05, 05A10, 05A15, 05A18, 05A19Keywords: Chord diagrams, perfect matchings, combinatorial classes, pattern avoidance, combinatorial maps, triangulations, Catalan posets, uniquely sorted permutations

Lukas Nabergall

The combinatorics of a tree-like functional equation for connected chord diagrams

连通弦图的树状函数方程的组合学

We extend the periodicity of birational rowmotion for rectangular posets to the case when the base field is replaced by a noncommutative ring (under appropriate conditions). This resolves a conjecture from 2014. The proof uses a novel approach and is fully self-contained. Consider labelings of a finite poset \(P\) by \(\left\vert P\right\vert + 2\) elements of a ring \(\mathbb{K}\): one label associated with each poset element and two constant labels for the added top and bottom elements in \(\widehat{P}\). Birational rowmotion is a partial map on such labelings. It was originally defined by Einstein and Propp for \(\mathbb{K}=\mathbb{R}\) as a lifting (via detropicalization) of piecewise-linear rowmotion, a map on the order polytope \(\mathcal{O}(P) := \{\text{order-preserving } f: P \to[0,1]\}\). The latter, in turn, extends the well-studied rowmotion map on the set of order ideals (or more properly, the set of order filters) of \(P\), which correspond to the vertices of \(\mathcal{O}(P)\). Dynamical properties of these combinatorial maps sometimes (but not always) extend to the birational level, while results proven at the birational level always imply their combinatorial counterparts. Allowing \(\mathbb{K}\) to be noncommutative, we generalize the birational level even further, and some properties are in fact lost at this step.In 2014, the authors gave the first proof of periodicity for birational rowmotion on rectangular posets (when \(P\) is a product of two chains) for \(\mathbb{K}\) a field, and conjectured that it survives (in an appropriately twisted form) in the noncommutative case. In this paper, we prove this noncommutative periodicity and a concomitant antipodal reciprocity formula. We end with some conjectures about periodicity for other posets, and the question of whether our results can be extended to (noncommutative) semirings.It has been observed by Glick and Grinberg that, in the commutative case, periodicity of birational rowmotion can be used to derive Zamolodchikov periodicity in the type \(AA\) case, and vice-versa. However, for noncommutative \(\mathbb{K}\), Zamolodchikov periodicity fails even in small examples (no matter what order the factors are multiplied), while noncommutative birational rowmotion continues to exhibit periodicity. Thus, our result can be viewed as a lateral generalization of Zamolodchikov periodicity to the noncommutative setting.Mathematics Subject Classifications: 06A07, 05E99Keywords: Rowmotion, posets, noncommutative rings, semirings, Zamolodchikov periodicity, root systems, promotion, trees, graded posets, Grassmannian, tropicalization

Darij Grinberg

Tom Roby

Birational rowmotion on a rectangle over a noncommutative ring

非交换环上矩形的双有理行运动

Erdős, Füredi, Rothschild and Sós initiated a study of classes of graphs that forbid every induced subgraph on a given number \(m\) of vertices and number \(f\) of edges. Extending their notation to \(r\)-graphs, we write \((n,e) \to_r (m,f)\) if every \(r\)-graph \(G\) on \(n\) vertices with \(e\) edges has an induced subgraph on \(m\) vertices and \(f\) edges. The forcing density of a pair \((m,f)\) is \[ \sigma_r(m,f) =\left. \limsup\limits_{n \to \infty} \frac{|\{e : (n,e) \to_r (m,f)\}|}{\binom{n}{r}} \right. .\] In the graph setting it is known that there are infinitely many pairs \((m, f)\) with positive forcing density. Weber asked if there is a pair of positive forcing density for \(r\geq 3\) apart from the trivial ones \((m, 0)\) and \((m, \binom{m}{r})\). Answering her question, we show that \((6,10)\) is such a pair for \(r=3\) and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting this conjecture.Mathematics Subject Classifications: 05C35, 05C65Keywords: Induced hypergraphs, forcing density

Maria Axenovich

József Balogh

Felix Christian Clemen

Lea Weber

Unavoidable order-size pairs in hypergraphs -- positive forcing density

超图中不可避免的阶数对——正强迫密度

We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among \(N\) uniformly random points on \([0,1]^2\) has size asymptotically \(2\sqrt{N}\). More generally, the order \(\Theta(\sqrt{N})\) still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of \(N\) greater than \(\sqrt{N}\), up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box.Mathematics Subject Classifications: 60C05, 05A05Keywords: Random permutations, longest increasing subsequences, permutons

Victor Dubach

Locally uniform random permutations with large increasing subsequences

局部一致随机排列及其长递增子序列

This article studies some new insertion algorithms that associate pairs of shifted tableaux to finite integer sequences in which certain terms may be primed. When primes are ignored in the input word these algorithms reduce to known correspondences, namely, a shifted form of Edelman-Greene insertion, Sagan-Worley insertion, and Haiman's shifted mixed insertion. These maps have the property that when the input word varies such that one output tableau is fixed, the other output tableau ranges over all (semi)standard tableaux of a given shape with no primed diagonal entries. Our algorithms have the same feature, but now with primes allowed on the main diagonal. One application of this is to give another Littlewood-Richardson rule for products of Schur \(Q\)-functions. It is hoped that there will exist set-valued generalizations of our bijections that can be used to understand products of \(K\)-theoretic Schur \(Q\)-functions.Mathematics Subject Classifications: 05A19, 05E05Keywords: Shifted tableaux, Edelman-Greene insertion, Sagan-Worley insertion, shifted mixed insertion, Schur \(Q\)-functions

涉及主题	discrete mathematicscombinatoricsmathematics
出版信息	出版商: eScholarship University of California，出版周期: ，期刊类型: journal，开源期刊: 是
基本数据	创刊年份: 2021，原创研究文献占比: ，自引率:， Gold OA占比:
平均审稿周期	60 weeks

Combinatorial Theory

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

The combinatorics of a tree-like functional equation for connected chord diagrams

Birational rowmotion on a rectangle over a noncommutative ring

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Locally uniform random permutations with large increasing subsequences

Shifted insertion algorithms for primed words

On the diameters of friends-and-strangers graphs

Promotion permutations for tableaux

Every group-embeddable monoid arises as the bimorphism monoid of some graph

Permutoric promotion: gliding globs, sliding stones, and colliding coins

The merging operation and \((d-i)\)-simplicial \(i\)-simple \(d\)-polytopes

ISSN	2766-1334
h-index	4