Abstract. 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 [Formula: see text]-analogs of the Catalan and Narayana numbers.

Abstract. Finding a directed acyclic graph (DAG) that best encodes the conditional independence 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, Studený, Hemmecke, and Lindner introduced the characteristic imset (CIM) polytope, [Formula: see text], 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 [Formula: see text] and that restrictions placed on the skeleton of the candidate DAGs correspond to faces of [Formula: see text]. 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 [Formula: see text]. Furthermore, the identified edges of [Formula: see text] 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.

Thomassen (J. Combin. Theory Ser. B, 62 (1994), pp. 180–181) proved that every planar graph is 5-choosable. This result was generalized by Škrekovski (Discrete Math., 190 (1998), pp. 223–226) and He, Miao, and Shen (Discrete Math., 308 (2008), pp. 4024–4026), who proved that every $K_5$-minor-free graph is 5-choosable. Both proofs rely on the characterization of $K_5$-minor-free graphs due to Wagner (Math. Ann., 114 (1937), pp. 570–590). This paper proves the same result without using Wagner's structure theorem or even planar embeddings. Given that there is no structure theorem for graphs with no $K_6$-minor, we argue that this proof suggests a possible approach for attacking the Hadwiger Conjecture.

We study the simplicial complex of t-colorable graphs on n vertices. We prove this complex is homotopy equivalent to a wedge of spheres all of dimension $n(t-1)-\binom{t}{2}-1$ when t=2 and when $t\ge n-3$. We show that such a homotopy equivalence does not hold for general t and n.

Given a list of n real numbers, one wants to decide whether every number in the list occurs at least k times. It will be shown that $\Omega(n\log n)$ is a sharp lower bound for the depth of an algebraic decision or computation tree solving this problem for a fixed k. For linear decision trees, the coefficient can be taken to be arbitrarily close to 1 (using the ternary logarithm). This is done by using the Björner--Lovász--Yao method, which turns the problem into one of estimating the Möbius function for a certain partition lattice. The method will work also for the more general T-multiplicity problem when T is additive and cofinite. A formula for the exponential generating function for the Möbius function of a partition poset with restricted block sizes in general will also be given.