CanaDAM 2021
En ligne, 25 - 28 mai 2021

Posets and lattices

ANDREW BEVERIDGE, Macalester College
de Finetti Lattices and Magog Triangles  [PDF]

The order ideal $B_{n,2}$ of the Boolean lattice $B_n$ consists of all subsets of size at most $2$. Let $F_{n,2}$ denote the poset refinement of $B_{n,2}$ induced by the rules: $i < j$ implies $\{i \} \prec \{ j \}$ and $\{i,k \} \prec \{j,k\}$. These rules are a special case of de Finetti's axiom from probability. We give a bijection from a family of poset refinements of $F_{n,2}$ to magog triangles. We then adopt our proof techniques to show that row reversal of an alternating sign matrix corresponds to a natural involution on gog triangles.

JOHN MACHACEK, Hampden-Sydney College
Lattice walks ending on a coordinate hyperplane using $\pm 1$ steps  [PDF]

We work with lattice walks in $\mathbb{Z}^{r+1}$ using step set $\{\pm 1\}^{r+1}$ that finish with $x_{r+1} = 0$. We further impose conditions of avoiding backtracking (i.e. $[v,-v]$) and avoiding consecutive steps (i.e. $[v,v]$) each possibly combined with restricting to the half space $x_{r+1} \geq 0$. We find in all cases the generating functions for such walks are algebraic and give polynomial recurrences for their coefficients. The enumeration in special cases includes central binomial coefficients and Catalan numbers as well as relations to enumeration of other families of walks previously studied.

GAYEE PARK, University of Massachusettes Amherst
Naruse hook formula for linear extensions of mobile posets  [PDF]

Linear extensions of posets are important objects in enumerative and algebraic combinatorics that are difficult to count in general. Families of posets like straight shapes and $d$-complete posets have hook-length product formulas to count linear extensions, whereas families like skew shapes have determinant or positive sum formulas like the Naruse hook length formula from 2014. In 2020, Garver et. al. gave determinant formulas to count linear extensions of a family of posets called mobile posets that refine d-complete posets and border strip skew shapes. We give a Naruse type hook length formula to count linear extensions of such posets as well q-analogues of our formula in both major and inversion index.

GARA PRUESSE, Vancouver Island University
Plain Greed suffices to 2-approximate Jump Number for Interval Posets  [PDF]

The jump number problem is NP-complete for interval posets; the jump number is realized by a linear extension of the poset with the fewest consecutive pairs of incomparable elements. We show that shelling the poset while locally avoiding jumps always yields a linear extension with no more than twice the optimal number of jumps. This answers a question posed in 1985 by Faigle and Schrader. The jump number of interval posets has been the subject of recent research interest, and approximation ratios as low as 16/11 have been achieved by polynomial time algorithms. The advantage of greed is the extreme simplicity of implementation, as well as the linear time complexity of the algorithm.

LLUÍS VENA, Universitat Politècnica de Catalunya
Characterization of extremal families for the shadow minimization problem in the Boolean lattice  [PDF]

Kruskal-Katona's theorem states that the initial segments in the colex order minimize the size of the shadow $\Delta(\cdot)$ among families $S\subset \binom{[n]}{k}$ with the same cardinality. F\"uredi and Griggs asked for their characterization after showing that that these initial segments are the unique minimizing families for some cardinalities. We answer this question by a new approach which provides structural properties of the extremal families. We show that $\Delta^{\log(n)}(S)$ of an extremal family $S$ is always the initial segment in the colex order (as when the $\Delta^{s}(S)$ is not the initial colex segment, then the coefficients of the $k$-binomial decomposition of $|S|$ decrease as fast as the hypotenusal numbers (OEIS: A001660)). We can also determine in time $O(n\: \text{poly}(k)) $ whether there exists an extremal family $S\subset\binom{[n]}{k}$ with $|S|$ elements and $s$ the smallest integer with $\Delta^{s}(S)$ not being the initial colex segment. Joint work with Oriol Serra.