The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
1answer
177 views

Über theorem on unavoidable patterns?

Let $A$ be an alphabet of $k$ symbols, and $p$ a pattern. An example of a pattern is $p=XX$, where $X$ is any finite string of symbols from $A^+$. Avoiding $p$ is avoiding any subword repeated twice ...
0
votes
0answers
34 views

$B_k[1]$ sets with smallest possible $m = max B_k[1]$ for given $k$ and $n = |B_k[1]|$ elements

Sidon sets are sets $A \subset \mathbb{N}$ such that for all $a_j,b_j \in A$ holds $$a_1+a_2=b_1+b_2 \iff \{a_1,a_2\}=\{b_1,b_2\}$$ Thus if you know the sum of two elements, you know which elements ...
10
votes
1answer
643 views

Two to the power of a triangular number: bijections

The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds ...
3
votes
0answers
68 views

Counting perfect matchings with integrals

Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to ...
3
votes
0answers
99 views

Triangulations of special polyhedra

Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...
17
votes
5answers
537 views

Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...
4
votes
0answers
160 views

Littlewood-Richardson rule for Schubert polynomials

What is the current state of the problem of finding a combinatorial rule for multiplying two Schubert polynomials? Is the problem still open?
9
votes
1answer
249 views

Why are the power symmetric functions sums of hook Schur functions only?

One interesting fact in symmetric function theory is that the power symmetric function $p_n$ can be written as an alternating sum of hook Schur functions $s_{\lambda}$: $$ p_n = \sum_{k+\ell = n} ...
2
votes
0answers
75 views

Lagrangean equations for the generating function of quadrangulations

Let $M(z)$ be the generating function of edge-rooted connected quadrangulations, with $z$ marking the number of edges. I derived the following Lagrangean equations for $M(z)$: $$M(z) = ...
6
votes
0answers
300 views

On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be ...
2
votes
1answer
190 views

Question about a proof in Graham and Lehrer's “Cellular algebras”

I'm sorry if this question is too basic for MO. I'm reading a paper by Graham and Lehrer "Cellular algebras" and have trouble understanding one step in a proof of a crucial theorem. I suppose that the ...
1
vote
3answers
196 views

Constructions of $2-(v,3,3)$-designs

I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...
2
votes
0answers
55 views

Rank generating functions on a graded poset and a linear extension of it

Let $A$ be a possibly infinite ensemble and let $\leq$ be a partial order between elements of $A$. We denote $P_{\leq}=(A,\leq)$ the corresponding poset. Furthermore, we suppose that $P$ is graded, ...
11
votes
1answer
239 views

A Product Related to Unrestricted Partitions

Start with the product for unrestricted partitions: (1+x+x$^2$+...)(1+x$^2$+x$^4$+...)(1+x$^3$+x$^6$+...)... Now replace some of the plus signs with minus signs and expand the product into a ...
2
votes
2answers
237 views

Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...
3
votes
2answers
258 views

Sandpile group corresponding to Abelian group

How we can prove each finite Abelian group is the sandpile group for some graph ?
0
votes
1answer
268 views

Missing formula! [closed]

I am doing a project on group association schemes, in particular looking at the structure constant $$p_{KL}^M = \#\{(x, y, xy) : x \in K, y\in L, xy \in M\}$$ where $K, L$ and $M$ are conjugacy ...
13
votes
2answers
794 views

Has Reifegerste's Theorem on RSK and Knuth relations received a slick proof by now?

For the notations I am using, I refer to the Appendix at the end of this post. Here is what, for the sake of this post, I consider to be Reifegerste's theorem: Theorem 1. Let $n\in\mathbb N$ and ...
8
votes
3answers
459 views

Arithmetic product of symmetric functions: why is it integral?

For every commutative ring $A$, let $\mathbf{Symm}_A$ be the ring of symmetric functions over $A$. Let $\mathbf{Symm}$ without a subscript denote $\mathbf{Symm}_{\mathbb{Z}}$. We can define a ...
15
votes
1answer
519 views

Conjectural identities for Young symmetrizers and Young-Jucys-Murphy elements

The following questions I have found in my own notes from about 3 years ago. Unfortunately, I lost much of the context; I believe I made these conjectures reading Okounkov-Vershik, arXiv:0503040v3, ...
0
votes
2answers
283 views

Morse matching with 0-cells and (n-1)-cells

Suppose one has a Morse matching (acyclic matching) of a poset $P$ of rank $n$ in which the only unmatched cells are 0-cells and $(n-1)$-cells, the same number $k$ of each one. If $P$ is connected ...
10
votes
1answer
243 views

Reference request: Grothendieck groups of Hecke algebras at root of unity and symmetric functions

Let $\zeta$ be an $\ell^{\text{th}}$ root of unity, and consider $H_n(\zeta)$, the (finite) Hecke algebra of type A. One can consider a dual pair of Hopf algebras arising from this data, denoted ...
8
votes
1answer
262 views

Plethysm of $\mathrm{QSym}$ into $\mathrm{QSym}$: can it be defined?

I will denote by $\Lambda$ the ring of symmetric functions, and by $\mathrm{QSym}$ the ring of quasisymmetric functions (both in infinitely many variables $x_1$, $x_2$, $x_3$, ..., both over $\mathbb ...
9
votes
2answers
267 views

How exactly does Schützenberger promotion relate to Striker-Williams promotion?

Schützenberger promotion, studied (for example) in Richard Stanley, Promotion and Evacuation, 2009, is a permutation of the set of all linear extensions of a finite poset. Since one can identify the ...
6
votes
2answers
583 views

What are the most important open problems in algebraic combinatorics? [closed]

I have seen the paper of Stanley http://math.mit.edu/~rstan/pubs/pubfiles/116.pdf but it is quite old and many of the problems are solved. I would like to know the two or three biggest open problems ...
3
votes
1answer
185 views

Semi-planar partition monoid/algebra

Here are some beginner questions on partition algebras... I am trying to understand the monoid called $P_k$ in Tom Halverson, Arun Ram, Partition Algebras. For the sake of simplicity, let $k$ be a ...
8
votes
3answers
569 views

bijection between number of partitions of 2n satisfying certain conditions with number of partitions of n

Suppose $\lambda = (\lambda_1,\lambda_2,.....,\lambda_k)$ is a partition of $2n$ where $n \in \mathbb N$ satisfying the following conditions: (1) $\lambda_{k} = 1$. (2) $\lambda_{i} - \lambda_{i+1} ...
2
votes
1answer
444 views

Combinatorial Inequality

Consider a set of $2^n-1$ non negative integers $S= ${$ a_{i,j}|1\le i\le n; 1\le j\le 2^{i-1} $} such that: \begin{align}{} 1.\ \ &a_{i,j}\le 2^{n+1-i} \\\\ 2.\ \ &a_{i,j}\le a_{i-1,j} \\\\ ...
1
vote
1answer
180 views

principal specialization of projective Schur functions

Is there a nice/known formula for the (some) principal specialization of a projective (P or Q) Schur polynomial? That is, I am talking about a projective analogue of Stanley's hook content formula ...
4
votes
1answer
173 views

Is the “renormalized third comultiplication” on $\mathbf{Symm}$ integral?

Background: For any commutative ring $R$, let $\mathbf{Symm}_R$ be the ring of symmetric functions in countably many variables $x_1$, $x_2$, $x_3$, ... over $R$. ("Symmetric functions" really means ...
2
votes
2answers
261 views

Alternating sum of binomial coefficients times logarithm

Trying to find a closed form expression for the following sum, or an asymptotic expression in terms of well known functions (like the Gamma function, for instance). Let $m,n$ be positive integers ...
10
votes
1answer
447 views

Analogues of the Knuth and Forgotten equivalences on permutations: have they been studied?

Consider a totally ordered alphabet $A$ of $n$ letters. Let $W$ be the set of all words over $A$ which have no two letters equal. Then, for example, we can define the Knuth equivalence on $W$ as the ...
20
votes
1answer
727 views

A strange sum over bipartite graphs

While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
2
votes
0answers
322 views

Software for Combinatorial Algebra sought

I am looking for software which helps me do straightforward tasks in combinatorial algebra. Let me give an example of what I mean by a straightforward task: I have two graded (generally ...
8
votes
2answers
597 views

Ubiquitous Zimin words

Let $w$ be a word in letters $x_1,...,x_n$. A value of $w$ is any word of the form $w(u_1,...,u_n)$ where $u_1,...,u_n$ are words. For example, $abaaba$ is a value of $x^2$. A word $u$ is called ...
8
votes
1answer
671 views

Connected graded involutive bialgebras (Hopf algebras) sought (for Dynkin idempotent checking)

Again, there is a general and a concrete question: Concrete question. Let $H$ be a connected graded bialgebra over a commutative ring $k$ with unity (where graded means $\mathbb N$-graded). Then, it ...
3
votes
6answers
247 views

Do stunted exponential series give projections of a cocommutative bialgebra on its coradical filtration?

Let $k$ be a field of characteristic $0$. Let $H$ be a cocommutative connected filtered bialgebra over $k$. ("Connected" means that the counit, restricted to the $0$-th part of the filtration, is an ...
2
votes
1answer
288 views

Rational Binomial Identity

Can anyone give a reference, a proof, or a reference that explains why Maple can evaluate this identity mathematically correctly: ...
6
votes
1answer
236 views

Simplices in convex polytopes

This question is a direct generalization of: Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices Given a convex ...
19
votes
2answers
2k views

Regular, Gorenstein and Cohen-Macaulay

All the statements below are considered over local rings, so by regular, I mean a regular local ring and so on; It is well-known that every regular ring is Gorenstein and every Gorenstein ring is ...
4
votes
1answer
279 views

Monotonicity of complete homogeneous symmetric polynomials

The complete homogeneous symmetric polynomials are defined as $$ h_k (x_1, \dots,x_n) = \sum_{1 \leq i_1 \leq i_2 \leq \cdots \leq i_k \leq n} x_{i_1} x_{i_2} \cdots x_{i_k}. $$ For example, $$ ...
5
votes
1answer
289 views

On MacMahon's conjecture and a Schur function identity

Recently I am reading Professor Bressoud's book "Proofs and confirmations"。And chapter 4 of his book is about using Schur functions to prove Macmahon's conjecture on symmetric plane partitions: ...
12
votes
1answer
1k views

Sublattices of Young's Lattice

Young's Lattice is the lattice of inclusions of Young tableaux, or integer partitions. In R. Stanley's Enumerative Combinatorics Vol. 1, Proposition 1.4.4., there is a generalization of integer ...
2
votes
1answer
207 views

Reference for: the Bruhat-minimal permutations not less than a fixed permutation pi?

Let $\pi\in S_n$. I recently needed to understand the permutations $\rho$ such that $\rho\not\leq\pi$ in Bruhat order. Since there are $O(n!)$ of those I really wanted a description of the $O(n^2)$ ...
6
votes
4answers
3k views

When is an algebra of commuting matrices (contained in one) generated by a single matrix?

Let C be an nxn matrix, then the polynomials in C (with appropriate coefficients) form an algebra of commuting matrices. I feel that I should know if the converse is true but I do not. So my first ...
4
votes
0answers
296 views

Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times ...
6
votes
2answers
668 views

What is the most general “two in one row for A & in one column for B” theorem?

Let $A$ and $B$ be two Young tableaux, i. e. Young diagrams filled with the numbers $1$, $2$, ..., $n$ for some $n$ (not necessarily the same $n$). (They need not be semistandard.) (a) (Etingof's ...