Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

8
votes
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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 ...