The basic problem of causal discovery is concerned with estimating a directed acyclic graph (DAG)representing the dependence relations in multivariate data. Several successful causal discoveryalgorithms have optimization-based aspects, which operate via a set of rules for searching thespace of DAGs. Recent results have revealed that the edge graph of the so-called characteristicimset polytope, CIM𝑝, can provide a diverse set of such rules. Characterizing the edge graph ofCIM𝑝 is a generally challenging problem. However, many algorithms first estimate the adjacen-cies in the causal DAG, in the form of an undirected graph 𝐺, prior to orienting the edges. In thisregime, knowledge of the subpolytope CIM𝐺 defined for DAGs with adjacencies specified by 𝐺 isvaluable. In this paper, we characterize the edge graph of CIM𝐺 when 𝐺 is an undirected tree,providing the first family of characteristic imset polytopes for which the edge graph is completelyunderstood. These results are applied to give a new causal discovery algorithm that estimates apolytree representing the dependencies in the given multivariate data. Our algorithm is shownto out-perform comparable methods on both real and synthetic data. Our results also reveal con-nections between characteristic imset polytopes and the well-studied stable set polytopes fromcombinatorial optimization.

We enumerate the numbers avkn(1324) of 1324-avoiding n-permutations with exactly k inversions for all k and n≥(k+7)/2. The result depends on a structural characterization of such permutations in terms of a new notion of almost-decomposability. In particular, our enumeration verifies half of a conjecture of Claesson, Jelínek and Steingrímsson, according to which avkn(1324)≤avkn+1(1324) for all n and k. Proving also the other half would improve the best known upper bound for the exponential growth rate of the number of 1324-avoiders from 13.5 to approximately 13.002.

Set-valued standard Young tableaux (Young tableaux in which the cells are filled with nonempty sets of positive integers) are a generalization of standard Young tableaux due to Buch (2002) with applications in algebraic geometry. The enumeration of set-valued SYT is significantly more complicated than in the ordinary case, although product formulas are known in certain special cases. In this work, we study the case of two-rowed set-valued SYT with a fixed number of entries. These tableaux are a new combinatorial model for the Catalan, Narayana, and Kreweras numbers and can be shown to be in correspondence with both 321-avoiding permutations and a certain class of bicolored Motzkin paths. We also introduce a generalization of the set-valued comajor index studied by Hopkins, Lazar, and Linusson (2023) and use this statistic to find seemingly new q-analogs of the Catalan and Narayana numbers.

Set-valued standard Young tableaux are a generalization of standard Young tableaux due to Buch (2002) with applications in algebraic geometry. The enumeration of set-valued SYT is significantly more complicated than in the ordinary case, although product formulas are known in certain special cases. In this work we study the case of two-rowed set-valued SYT with a fixed number of entries. These tableaux are a new combinatorial model for the Catalan, Narayana, and Kreweras numbers, and can be shown to be in correspondence with both 321-avoiding permutations and a certain class of bicolored Motzkin paths. We also introduce a generalization of the set-valued comajor index studied by Hopkins, Lazar, and Linusson (2023), and use this statistic to find seemingly new q-analogs of the Catalan and Narayana numbers.

Finding a directed acyclic graph (DAG) that best encodes the conditional inde-pendence statements observable from data is a central question within causality. Algorithms that greedily transform one candidate DAG into another given a fixed set of moves have been particularly successful, for example, the greedy equivalence search, greedy interventional equivalence search, and max-min hill climbing algorithms. In 2010, Studenty, Hemmecke, and Lindner introduced the char-acteristic imset (CIM) polytope, CIMp, whose vertices correspond to Markov equivalence classes, as a way of transforming causal discovery into a linear optimization problem. We show that the moves of the aforementioned algorithms are included within classes of edges of CIMp and that restrictions placed on the skeleton of the candidate DAGs correspond to faces of CIMp. Thus, we observe that greedy equivalence search, greedy interventional equivalence search, and max-min hill climbing all have geometric realizations as greedy edge-walks along CIMp. Furthermore, the identified edges of CIMp strictly generalize the moves of these algorithms. Exploiting this generalization, we introduce a greedy simplex-type algorithm called greedy CIM, and a hybrid variant, skeletal greedy CIM, that outperforms current competitors among hybrid and constraint-based algorithms.

Barely set-valued tableaux are a variant of Young tableaux in which one box contains two numbers as its entry. It has recently been discovered that there are product formulas enumerating certain classes of barely set-valued tableaux. We give some q-analogs of these product formulas by introducing a version of major index for these tableaux. We also give product formulas and q-analogs for barely set-valued plane partitions. Many of the results are stated in the generality of P-partitions that then specialize to particularly nice formulas for rectangles and minuscule posets. The proofs use several probability distributions on the set of order ideals of a poset, depending on the real parameter q>0, which we think could be of independent interest.

We study a generalisation of Simpson reversal (also known as Simpson’s paradox or the Yule–Simpson effect) to 2×2×2 contingency tables and characterise the cases for which it can and cannot occur with two combinatorial-geometric lemmas. We also present a conjecture based on some computational experiments on the expected likelihood of such events. 

Let W be a finite Weyl group and (W) over tilde the corresponding affine Weyl group. A random element of (W) over tilde can be obtained as a reduced random walk on the alcoves of (W) over tilde. By a theorem of Lam (Ann. Prob. 2015), such a walk almost surely approaches one of vertical bar W vertical bar many directions. We compute these directions when W is B-n, C-n, and D-n, and the random walk is weighted by Kac and dual Kac labels. This settles Lam's questions for types B and C in the affirmative and for type D in the negative. The main tool is a combinatorial two row model for a totally asymmetric simple exclusion process (TASEP) called the D*-TASEP, with four parameters. By specializing the parameters in different ways, we obtain TASEPs for each of the Weyl groups mentioned above. Computing certain correlations in these TASEPs gives the desired limiting directions.

We examine a few families of semistandard Young tableaux, for which we observe the cyclic sieving phenomenon under promotion. The first family we consider consists of stretched hook shapes, where we use the cocharge generating polynomial as CSP-polynomial. The second family contains skew shapes, consisting of disjoint rectangles. Again, the charge generating polynomial together with promotion exhibits the cyclic sieving phenomenon. This generalizes earlier results by B. Rhoades and later B. Fontaine and J. Kamnitzer. Finally, we consider certain skew ribbons, where promotion behaves in a predictable manner. This result is stated in the form of a bicyclic sieving phenomenon. One of the tools we use is a novel method for computing charge of skew semistandard tableaux, in the case when every number in the tableau occurs with the same frequency.

We prove several new instances of the cyclic sieving phenomenon (CSP) on Catalan objects of type A and type B . Moreover, we refine many of the known instances of the CSP on Catalan objects. For example, we consider triangulations refined by the number of "ears", non-crossing matchings with a fixed number of short edges, and non-crossing configurations with a fixed number of loops and edges.