# Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

1,579 questions

**8**

votes

**0**answers

175 views

### Does anyone know of this manifestation of the Littlewood-Richardson coefficients for the complete flag variety?

This is the culmination of about 11 years of research but after I discovered it I found a proof that was extremely trivial, so I'm wondering if it's already known.
Let $(a,b)$ with $a < b$ ...

**8**

votes

**0**answers

146 views

### Infinite series identities in search of a proof

This comes in relation to the Fishburn numbers.
I stumbled on the following relation for which I ask a proof if true.
Let $Q_i(z):=1-(1-t)^{i-1}(1-zt)$. Then
$$\sum_{n=0}^{\infty}\frac{(n+1)zt}{...

**8**

votes

**0**answers

86 views

### Counting symmetric convex bodies with no nonzero lattice point in the interior

In order to estimate the size of the torsion in the algebraic $K$-groups of $\mathbb Q$ one needs to understand the homology of $\mathrm{GL}_n(\mathbb Z)$, or alternatively, the homology of the space ...

**8**

votes

**0**answers

148 views

### For $q$-analogues of a known curious identity

In 2002 I published the folllowing curious combinatorial identity:
$$(x+m+1)\sum_{i=0}^m(-1)^i\binom{x+y+i}{m-i}\binom{y+2i}i-\sum_{i=0}^m\binom{x+i}{m-i}(-4)^i=(x-m)\binom xm.$$
My original proof is ...

**8**

votes

**0**answers

182 views

### Proof of Dixon's identity only using Chu-Vandermonde

For any integers $a,b,c\ge 0$,
one has the well known identity or "Dixon's Theorem":
$$
\sum_{k\in\mathbb{Z}} (-1)^k
\left(\begin{array}{c}a+b\\a+k\end{array}\right)
\left(\begin{array}{c}b+c\\b+k\end{...

**8**

votes

**0**answers

157 views

### Counting symmetric subgroups of symmetric groups

This question is related to, but much more specific than, this one.
For $k \leq n$, let $a(k,n)$ denote the number of conjugacy classes of subgroups of the symmetric group $S_n$ which are isomorphic ...

**8**

votes

**0**answers

143 views

### Nonzero subdeterminants conjecture: has anybody seen this anywhere?

I already posted this question on Mathematics StackExchange. A user there suggested that I rather post it on mathoverflow, since it is a research question. So here it is.
Let $m\geq2$, $n\geq1$ be ...

**8**

votes

**0**answers

164 views

### (First) Bianchi Identities

I'm looking at a paper of J. A. Thorpe ("Some Remarks on the Gauss-Bonnet Integral"). In the paper he defines "higher-order" notions of curvature. One thinks of the usual curvature tensor as $R\in \...

**8**

votes

**0**answers

188 views

### Asymptotic distribution of $\lambda_1$ under the $z$-measure for partitions

The following question about $z$-measures on Young diagrams came up in some ongoing work with Ofir Gorodetsky. I recall the background and then state our question below in the box.
For parameters $z$ ...

**8**

votes

**0**answers

148 views

### Stratification of space of labelled circles in the plane

Consider the space of $n$ round circles in the plane to be the open subset of $\mathbb R^{3n}$:
$$C_n = \{ (v_1, v_2, \cdots, v_n, r_1, r_2, \cdots, r_n ) : v_i \in \mathbb R^2, r_i \in (0, \infty) \ ...

**8**

votes

**0**answers

379 views

### Evaluating $\sum_{k=1}^{\infty} \binom{2z}{z-kn}$

Can we turn this sum into a simpler form ?
$$\sum_{k=1}^{\infty} \binom{2z}{z-kn}=\Gamma(2z+1)\sum_{k=1}^{\infty} \frac{1}{\Gamma(z-kn+1)\Gamma(z+kn+1)} \qquad;\qquad (z;n)\in \mathbb C \times \mathbb ...

**8**

votes

**0**answers

183 views

### Almost blocking sets in $\mathbb F_q^2$

$\newcommand{\F}{{\mathbb F}}$
Let $q$ be an odd prime power. A blocking set in the affine plane $\F_q^2$ is a set blocking (meeting) every line.
A union of two non-parallel lines is a blocking set ...

**8**

votes

**0**answers

143 views

### How many components are there in the space of “generic” planar N-gons? (Mnev's revenge)

Call an ordered $N$-tuple of points in the Euclidean plane ${\mathbb R} ^2$ "in general position" if no three points of the points in the set are collinear. As a function of $N$ how many components ...

**8**

votes

**0**answers

95 views

### Stable Acute Triangles in a Grid

The following combinatorial question came up while trying to prove a lemma for my research. Let $[N]$ denote the $N\times N$ grid inside the integer lattice $\mathbb{Z}\times\mathbb{Z}.$ The square ...

**8**

votes

**0**answers

183 views

### Stepanov phase transition in random graph

Consider the classical random graph model G(n,p), with p=c/n, as proposed by Erd\"os and R\'enyi.
At this scaling, the most prominent feature is arguably the abrupt change of the topology that the ...

**8**

votes

**0**answers

144 views

### Littlewood-Richardson sequences and Littlewood-Richardson coefficients

I'm looking for a proof or a reference for the following statement, I give the definitions below:
There exists a Littlewood-Richardson sequence of type $(\alpha, \beta, \lambda)$ if and only if $...

**8**

votes

**0**answers

61 views

### Is recognizing if a Latin square is isotopic to its transpose more efficient than computing its symmetry group?

Ihrig and Ihrig (2007) described a mathematical method for determining if a Latin square is isotopic to its transpose (where isotopic Latin squares vary by permuting the rows, columns and symbols). ...

**8**

votes

**0**answers

327 views

### When do almost all these invariants of tensors vanish?

Let $A,B,C,D$ be $n$-dimensional vector spaces over a field $k$.
There is a natural homomorphism from the $mn^m$th tensor power $A^{\otimes (m n^m)} $ of $A$ to $k$ given by the determinant map $A^{\...

**8**

votes

**0**answers

184 views

### Tree-width of a union of two trees

Is it possible to unite two $n$-vertex trees such that the resulting graph has bounded tree-width?
Formally, does there exists a constant $k$ such that given two $n$-vertex trees $T_1$ and $T_2$ ...

**8**

votes

**0**answers

176 views

### Applications of the Frankl's union closed conjecture

Does anyone know any concrete applications of the union closed conjecture that are interesting in their own right? (As opposed to being interesting reformulations of the conjecture.)
The only ...

**8**

votes

**0**answers

211 views

### Subdivision of pentagon into six congruent pieces

I posted this on math.stackexchange, but got no answers.
It is easy to divide a 2-gon into 3 congruent line segments. It is also easy to divide a triangle into 4 smaller triangles that are congruent. ...

**8**

votes

**0**answers

383 views

### A relation between intersection and product on boolean interval of finite groups

Let $[H,G]$ be a boolean interval of finite groups (i.e. the lattice of intermediate subgroups $H \subseteq K \subseteq G$, is boolean). For any element $K \in [H,G]$, let $K^c$ be its lattice ...

**8**

votes

**0**answers

292 views

### What is intuition behind sets with more sums than differences?

There exist finite sets $A$ in, say, $\mathbb{Z}$, such that $|A+A|>|A-A|$. The minimal such set contains 8 elements and consists of, say, 0, 2, 3, 4, 7, 11, 12, 14. How should I find such an ...

**8**

votes

**0**answers

180 views

### Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...

**8**

votes

**0**answers

200 views

### A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ non-...

**8**

votes

**0**answers

146 views

### Product of Partial Orders

Define the transpose product of a partial order $P$ over a set $S$ in the following way. The direct product of a partial order $P \subseteq S \times S$ and its converse, $P^{op}$, gives a partial ...

**8**

votes

**0**answers

144 views

### Edge-colorings of plane graphs: do you know references where the following questions are studied?

Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...

**8**

votes

**0**answers

176 views

### De Bruijn sequence inside De Bruijn sequence

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$.
What is ...

**8**

votes

**0**answers

548 views

### What can I further assume about the speeds of runners of Lonely Runner Conjecture WLOG?

Lonely Runner Conjecture is the following problem, and the conjecture was proven to be true for $k\leq 7$:
Let $V$ be the set of $k$ distinct positive integers with $v_1<v_2<...<v_k$ Then ...

**8**

votes

**0**answers

257 views

### Mass Transportation Through Wonderful Roller

There is a wonderful roller that transports mass from A to B and there is a pile of sand with weight $W$ in point A and we want to transport it to B.
Wonderfulness of roller comes from this property ...

**8**

votes

**0**answers

325 views

### What's the analogue of a Young symmetrizer in the Brauer algebra?

According to Schur--Weyl duality, the centralizer of $\mathrm{GL}(V)$ acting diagonally on $V^{\otimes N}$ is the group algebra of the symmetric group $\mathbb S_N$. An equivalent formulation is the ...

**8**

votes

**0**answers

319 views

### Inversion, Koszul duality, combinatorics and geometry

According to this MO answer Koszul duality is related to operations on generating series;
1) multiplicative inversion for quadratic algebras,
2) compositional inversion for quadratic operads,
3) ...

**8**

votes

**0**answers

225 views

### Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...

**8**

votes

**0**answers

582 views

### How many ways can a snake lie?

This is essentially a question about counting nonintersecting short paths in a
cubic lattice, but with a twist. (One constraint that I did not make clear below
is that when to turn is already chosen:...

**8**

votes

**0**answers

286 views

### Littlewood-Richardson coefficients for Jack symmetric functions

Let $\Lambda$ be the algebra of symmetric functions over $\mathbb{Q}(\alpha)$.
We define a scalar product $\langle \cdot,\cdot\rangle_\alpha$ on $\Lambda$ by setting $\langle p_\mu,p_\nu\rangle_\...

**8**

votes

**0**answers

270 views

### A strong sum-product “for translates” in finite fields

In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...

**8**

votes

**0**answers

180 views

### Erdös-Fuchs Theorem for multivariate linear forms

Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$.
It is not very difficult to show that if $r(n) > 0$ ...

**8**

votes

**0**answers

188 views

### A Product Related to Partitions with Largest Part n

This is a finite version of a problem of mine entitled "A product related to unrestricted partitions." It has the advantage that, at least for small values of n, it is easily solved.
Begin with the ...

**8**

votes

**0**answers

187 views

### Generalised Polya's urn with i.i.d. replacement

Let $\mu$ be a fixed measure (possibly with moment conditions) on $\mathbb N$ and $X_1,X_2,\dots$ be i.i.d. samples from $\mu$. Start with one white and one black ball in the urn. At the $n$-th step, ...

**8**

votes

**0**answers

237 views

### Generalized flag complex?

Assume we glue an $n$-dimensional simplicial complex $K$
from copies of an $n$-simplex $\Delta$ with fixed spherical metric.
We may think that $\Delta$ has colored vertices
and we glue so that the ...

**8**

votes

**0**answers

200 views

### What are the known algorithms for computing the inverse of a group automorphism?

Given a finitely presented group $<x_1,x_2,...,x_n|R_1,R_2,...,R_n>$, one specifies an automorphism $\phi$ by its action on the generators, i.e. $\phi(x_i)=w_i$ for some (reduced) words $w_i$ in ...

**8**

votes

**0**answers

459 views

### det(A)det(B) = det(AB+correction), Capelli identities, “factorized” representation of $\mathfrak {gl}_n$

Context: Some probably know that there are Capelli identities which state
$$det(A)det(B) = det(AB+correction)$$ for some matrices with non-commuting elements, they go back to the 19-th century, but ...

**8**

votes

**0**answers

425 views

### Chern Classes of Exterior Products of a vector bundle.

This is mostly a question in combinatorics. Is there a clean way in terms of determinantal identities to write down $c(\wedge^k V)$ i.e. the individual summands in terms of the individual summands of $...

**8**

votes

**0**answers

407 views

### One more coloring question

This question is related to my previous questions, say, this one and this one. Let $G$ be an infinite graph of bounded degree, and $\lambda>0$. Let $k=k_G(\lambda)$ be the minimal number of colors ...

**8**

votes

**0**answers

341 views

### Matroids arising from simplicial complexes

I am somewhat of a newcomer to matroid theory, so I apologize if this is elementary.
Suppose we consider the boundary matrix of a simplicial complex with coefficients in $\mathbb{Z}/2\mathbb{Z}$. We ...

**8**

votes

**0**answers

669 views

### Path connected set of matrices?

Consider the collection of $n$ by $n$ matrices
$$S=\{ A: A_{ij}\le0,\quad (-1)^{c_i}\det A(P_i;Q_i)<0 \quad \text{for} \quad i=1,\ldots, k\}$$
where $c_i\in \{0,1\}$, $P_i$ and $Q_i$ are disjoint ...

**8**

votes

**0**answers

174 views

### Motivation behind Panyushev's “constant-averages-along-orbits” conjecture

In his article "On orbits of antichains of positive roots" (European Journal of Combinatorics 30 (2009) 586–594; sorry, it's an Elsevier journal, so there's no freely available online version for me ...

**8**

votes

**0**answers

497 views

### Can one give a “nice” expression for this determinant?

I am asking this question on behalf of a senior faculty member who is sometimes intimidated by computers. It is motivated by a problem in invariant theory. Unfortunately the question is a bit vague.
...

**8**

votes

**0**answers

575 views

### The name for a partial order

In a recent paper of mine, my co-authors found that a partial order that we were using was contained in a paper by Kundgen. In it, he called it "right-shifted partial order". I was curious, and found ...

**8**

votes

**0**answers

402 views

### An extremal problem for graphs having every edge contained in a 4-clique

This is a follow-up to Graphs with many triangles but few complete graphs on 4 vertices
I'm looking for an upper bound for the difference between the number of edges and the number of 4-cliques in a ...