6. Combinatorics Questions
-
Equivariant Log-Concavity of Stirling Numbers of the First Kind
Problem 6.1.
[Shiyue Li] The sequence of Stirling numbers of the first kind count the number of permutations in $S_n$ decomposing into $k$ disjoint cycles. Precisely, $$ \begin{bmatrix}n \\ k \end{bmatrix} := \#\{\sigma \in S_n \mid \sigma \text{ has } k \text{ distinct cycles}\}.$$ We say a sequence $\{a_i\}$ of nonnegative numbers $a_i$ is log-concave if $$a_i^2 \geq a_{i-1}a_{i+1} \ \forall \ i.$$ The sequence $$\left\{\begin{bmatrix}n\\k\end{bmatrix}\right\}_{k = 0}^{k=n}$$ is known to be log-concave via an analytic proof of real-rootedness of the generating polynomial.
A graded $G$-representation $$ V^\bullet = \bigoplus_{i = 0} V_k$$ is said to be equivariantly log-concave if, for all $i$, there exists an injection $$\varphi: V_{i-1}\otimes V_{i+1} \hookrightarrow V_{i} \otimes V_i $$ such that $g\cdot \varphi(v) = \varphi(g \cdot v) \ \forall \ g \in G,\ \forall \ v \in V_{i-1}\otimes V_{i+1}$.
Question: Is there an equivariantly log-concave $S_n$-representation $V^\bullet = \oplus V_k$ such that $\text{dim}(V_k) = \begin{bmatrix}n\\k\end{bmatrix}$? -
Ehrhardt Volume of the Normal Complex
Problem 6.2.
[Anastasia Nathanson] Given a matroid $M$, one can associate to it a certain polytopal complex called the normal complex of $M$. One can ask whether the normal complex of $M$ admits an analogue of the Ehrhart polynomial, since the Ehrhart polynomial of a polytope will also calculate the polytope’s volume. Question: Can we produce an analogue of the Ehrhart polynomial for normal complexes, or more generally polytopal complexes, and use this to calculate some notion of Ehrhart volume for the normal complex? -
Sidorenko’s Conjecture
Problem 6.3.
[Nitya Mani] For any bipartite graph $H$ and for any graph $G = (V,E)$,
$$\#\{\text{labeled subgraphs in }G \text{ isomorphic to } H\} \ \geq n^{V(H)}p^{e(H)}$$ where $n^{V(H)}p^{e(H)}$ denotes the expected number of such labelled subgraphs for $G$ a random graph of the same density (i.e. same number of edges on a fixed number of vertices).
A more tractable question in the same vein,
Are there particular families of graphs $H$ that satisfy Sidorenko’s conjecture? Can we instead consider the distribution of subgraphs $H$ as they appear in a directed graph or a tournament (a directed complete graph)? -
Distribution of Intersection Numbers of Undirected Graphs
Problem 6.4.
[Alex Markham] Given an undirected graph $G$, a clique of $G$ is an induced subgraph of $G$ that is complete (that is, any two distinct vetices are adjacent). An edge clique cover is a set of cliques covering all vertices of $G$. The intersection number of a graph $G$ is the number of cliques in a minimum edge-clique cover. Question: What is the distribution of these intersection numbers? If one were to make a histogram of all undirected graphs on $n$ vertices, what is the distribution of these intersection numbers? -
Ehrhart Theory of Lattice Path and Panhandle Matroids
Problem 6.5.
[Andrés R. Vindas Meléndez] Given a panhandle matroid that can be realized as a lattice path matroid on a $n \times k$ grid, is it true that the coeffcients of the Ehrhart polynomial are bounded above by the coefficients of the uniform matroid $U_{n,k}$ and below by those of the minimal matroid? Moreover, are panhandle matroids Ehrhart-positive? -
Problem 6.6.
[Mont Cordero, Federico Ardila, Kris Shaw] What are combinatorially and geometrically interesting tropical varieties, in particular as they arise from root systems and/or matroids?
Cite this as: AimPL: Gems of combinatorics, available at http://aimpl.org/gemscombin.