# 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.

**12**

votes

**0**answers

811 views

### Sums of Partitions and Stirling's formula

Stirling's formula $$N! \sim \sqrt{2 \pi}\ N^{N+ \frac{1}{2}} e^{-N}$$ follows easily from Laplace's method in light of the famous integral representation $$N! = \int_0^{\infty} e^{-z} z^N dz.$$ ...

**12**

votes

**0**answers

421 views

### Enumeration of Standard Young Tableau of bounded height

First for some notation
$$ l(\lambda) = \text{ number of parts in a partition } \lambda \vdash n$$
$$ f_{\lambda} = \text{number of standard Young tableau of shape } \lambda\vdash n$$
The number $f_{...

**12**

votes

**0**answers

644 views

### Regular languages of matrices and their generating functions

My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...

**12**

votes

**0**answers

492 views

### A commutative monoid associated with a finite abelian group

Let $M$ be a finite abelian group, and denote by $e_m$, for $m \in M$, the canonical basis of $\mathbb{Z}^M$. For $m, n \in M$ define elements $v_{m,n} \in \mathbb{Z}^M/\langle e_0\rangle$ as
$$
v_{m,...

**12**

votes

**0**answers

325 views

### Matroids with prescribed independent sets

Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...

**11**

votes

**0**answers

148 views

### Quantitatively characterizing the failure of the converse of Dirac's theorem

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...

**11**

votes

**0**answers

275 views

### Conjectural nonvanishing of some combinatorial sums (6j symbols)

From various considerations and with the help of J. Van der Jeugt, I was led to conjecture the following property of a class of Wigner 6j-symbols:
for any integers $k,m$ with $m\ge k\ge 2$,
$$
\left\{...

**11**

votes

**0**answers

320 views

### Is there a weak strong regularity lemma?

A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...

**11**

votes

**0**answers

302 views

### Wherefore art thou a Borcherds Product?

This question essentially asks how can one recognize (or rule out) that a generating function of combinatorial origin may be given as a Borcherds type product. I'll start with a motivational example: ...

**11**

votes

**0**answers

146 views

### Poset of nonvanishing minors of a matrix

This question was posed on MSE here three days ago, but hasn't gotten any answers or suggestions. I hope it's okay to ask it on MO, but if I should wait a little longer, please just let me know.
Say $...

**11**

votes

**0**answers

351 views

### A congruence involving roots of unity

Let $f(x) \in \mathbb{Z}[x]$ and suppose $f(\omega^j) \in \mathbb{Z}$ for all $j= 1, \dots, n$ where $\omega = e^{2 \pi i/n}$ is a primitive $n^{\text{th}}$ root of unity.
Computational evidence ...

**11**

votes

**0**answers

199 views

### Question on a reduction in Kirillov's paper on positivity of divided difference operators

As the title says, my question is on a specific argument in Kirillov - Skew divided difference operators and Schubert polynomials (journal, MSN) on positivity of divided difference operators. I recall ...

**11**

votes

**0**answers

206 views

### Is there a term for this graph subset?

Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:
If $c:V(G)\rightarrow [k]$ is a vertex ...

**11**

votes

**0**answers

421 views

### Wilf's conjecture: complementary Bell numbers

The complementary Bell numbers or Uppuluri-Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....

**11**

votes

**0**answers

262 views

### Connection between Gelfand-Tsetlin basis and SSYT basis in Schur module

Consider an $n$-dimensional complex vector space $V$ with a chosen basis $e_1,\ldots,e_n$. This basis defines a Cartan decompostion of $GL(V)\cong GL_n$ and for an (integral dominant) highest weight $\...

**11**

votes

**0**answers

178 views

### Euclidean realizations of a configuration of $27$ points and $45$ lines

Let $GQ(2,4)$ denote the abstract configuration (=incidence structure) consisting of $27$ points and $45$ lines, with $3$ points on leach line and $5$ lines through each point, which can be described ...

**11**

votes

**0**answers

461 views

### Converse of Frobenius

Enumerate the elements of a finite group $G$ as follows: $g_1,g_2,\dots,g_n$. Introduce $n$ variables indexed by the elements of $G$: $x_{g_1},\dots,x_{g_n}$.
Consider the matrix $X_G$ with entries $...

**11**

votes

**0**answers

512 views

### Product of a Schubert polynomial and a double Schubert polynomial

Let $S_u(x)$ be a Schubert polynomial and let $S_v(x;y)$ be a double Schubert polynomial. Then their product can be expressed in terms of the double Schubert polynomials as
$$S_u(x)S_v(x;y)=\sum_w{c_{...

**11**

votes

**0**answers

363 views

### Theorems proved using combinatorial nullstellensatz that have no other known proof

Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question. ...

**11**

votes

**0**answers

327 views

### Maximizing the number of semistandard Young tableaux

Is anything known about the following question? Given a positive
integer $p$ and a real number $0<\alpha<1$, what partition $\lambda$
whose parts sum to $\alpha p^2$ (asymptotically) and whose ...

**11**

votes

**0**answers

515 views

### Evaluating products of cyclotomic polynomials at roots of unity

Are there general non-trivial conditions on $p(\cdot)$ and $n$, where $p(\cdot)$ is a product of cyclotomic polynomials and $n$ is a positive integer, such that all the coefficients of $p(\cdot)$ are ...

**11**

votes

**0**answers

224 views

### When is a group Fibonacci sequence contained in a single conjugacy class?

First a definition: a Fibonacci sequence in a group is a sequence in which the first two elements may be arbitrary, and from there on each element is a product (using the group operation) of the ...

**11**

votes

**0**answers

710 views

### Erdos multiplication problem revisited

The well-known problem is acquiring a cardinality of the set of distinct numbers in the multiplication table n x m.
The very problem has been discussed in-depth and, as such, I require no further ...

**11**

votes

**0**answers

317 views

### The Universal Labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...

**11**

votes

**0**answers

402 views

### Colouring a graph whose edge set is a special union of cliques

I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...

**11**

votes

**0**answers

286 views

### Right-angled polytopes

%This question is motivated by the little discussion here at the bottom.
The following thing are known about hyperbolic right-angled polytopes:
Compact hyperbolic right-angled polytopes do not exist ...

**11**

votes

**0**answers

519 views

### Ramanujan Digraphs?

In Gowers' paper on quasirandom groups, he suggests a spectral theory of bipartite graphs employ the singular values of the bipartite adjacency matrix. Accordingly, singular values appear to be a ...

**11**

votes

**0**answers

647 views

### A basic question on Stone-Cech compactification of $\mathbb{Z}$

Can the identity isomorphism on the additive group $\mathbb{Z}$ be extended to a non-identity semigroup isomorphism on $\beta\mathbb{Z}$, and still preserves $\beta\mathbb{Z}\setminus\mathbb{Z}$? ...

**11**

votes

**0**answers

407 views

### Linear eta product identities - how many are there?

For the Dedekind eta function, defined as usual by $\eta(q) = q^{\frac1{24}} \prod\limits_{n=1}^{\infty} (1-q^{n}) $, let for brevity $e_k:=\eta(q^k)$. With this notation, a blog entry of Michael ...

**11**

votes

**0**answers

776 views

### Hamiltonian cycles and fundamental groups

I'm interested in the interplay between the Hamiltonian cycles of graphs and the compact surfaces they embed in. I was doing some reading on the Lovász conjecture for Cayley graphs, I started noticing ...

**11**

votes

**0**answers

347 views

### Lower Bound on the Volume of Certain Polytopes

Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks
$$
\rho=\{B_1,B_2,\ldots,B_{k}\}
$$
we can define the set of equations
$$
E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in B_{i}}{x_j}\quad\text{...

**11**

votes

**0**answers

410 views

### Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature,...

**11**

votes

**0**answers

646 views

### A number theoretic identity

Let $n$ be a positive integer such that $2n+1$ is prime.
The elements of the factor group $G = \mathbb{F}^\times_{2n+1}/\{\pm 1\}$ can be represented by the integers $1,2,\ldots,n$. For every $x \in \...

**10**

votes

**0**answers

176 views

### Fundamental circuit characterization of matroid independence complexes

I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...

**10**

votes

**0**answers

116 views

### A combinatorial proof of the Harrow--Kolla--Schulman theorem

Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$.
For integers $0 \leq k \leq n$, define a ...

**10**

votes

**0**answers

331 views

### Relation between a continued fraction and partitions

I am interested in the continued fraction
$$\sum\limits_k {{z^{{2^k} - 1}}} = \frac{1}{{1 - \frac{{{T_0}z}}{{1 - \frac{{{T_1}z}}{{1 - \frac{{{T_2}z}}{{1 -{ \ddots }}}}}}}}}.$$
OEIS A104977 states ...

**10**

votes

**0**answers

233 views

### Looking for method to generalize parity argument for Klein's Theorem (Happy Ending Problem)

The famous "Happy Ending Problem" for quadrilaterals states:
Theorem Given a set of five points in the general position on the plane, there exists a subset of 4 which form the vertices of a convex ...

**10**

votes

**0**answers

137 views

### Cospectral mate of rhombic dodecahedron

I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was ...

**10**

votes

**0**answers

264 views

### $L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan

There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....

**10**

votes

**0**answers

170 views

### Asymptotics of subgraph densities in graphons

In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...

**10**

votes

**0**answers

239 views

### Greedy permutation of the set $\{1,2,\dots,n\}$ and prime numbers

Answering this question, another question came to my mind. For which $n$ will the greedy algorithm work?
We define a sequence of natural numbers $x_n$ recursively:
$$x_1 =1,$$
$$x_n \mbox{ is the ...

**10**

votes

**0**answers

341 views

### Computing the ordinal of a rational language well-partially-ordered by the subword relation

Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...

**10**

votes

**0**answers

127 views

### Ideals in strong Bruhat order

Recall that a (lower) ideal in a poset $(P, \le)$ is a subset $I\subset P$ such that $x\in I \Rightarrow y\in I$ for all $y\le x$. In am interested in ideals in finite Coxeter groups $W$ equipped ...

**10**

votes

**0**answers

143 views

### types of generating functions (ordinary, exponential, ???) closed under substitution

A nice feature of ordinary and exponential generating functions is that they are closed under substitution: if $F(z)$ and $G(z)$ both have integer coefficients, then $F(G(z))$ also has integer ...

**10**

votes

**0**answers

164 views

### Is there a nice formula for the “non-crossing substitution” of linear combinatorial species?

Background
A linear species is a functor
$$F : \mathrm{Lin} \to \mathrm{FinSet},$$
where $\mathrm{Lin}$ is the category of totally ordered sets and bijections and $\mathrm{FinSet}$ is the category ...

**10**

votes

**0**answers

295 views

### Consequences of Zeeman's conjecture

Recall the Zeeman's conjecture: if $K$ is a contractible polyhedron of dimension 2, then $K\times I$ has a collapsible subdivision.
Zeeman showed that this implies the Poincaré conjecture in ...

**10**

votes

**0**answers

346 views

### diameter as a Morse function

Consider the space $X_1$ of closed subsets not containing a pair of antipodal points of the unit circle. Here we have a kind of degenerate Morse function, defined by the diameter of the pointset. ...

**10**

votes

**0**answers

336 views

### What are the homological properties of Young's lattice?

Young's lattice $Y$ is a graded poset and a distributive lattice whose elements are all the partitions of $n$ for $n \in \mathbb{N}$ with the poset relation coming from inclusion of Young diagrams. ...

**10**

votes

**0**answers

706 views

### Reference/quote request: “All of combinatorics is the representation theory of $S_n$”

I think I remember reading somewhere a glib (or is it deep?) quote, perhaps due to Rota?, which was something like
"All of combinatorics is essentially [or can be reduced to?] the representation ...

**10**

votes

**0**answers

1k views

### Generalization of Cauchy's identity

Let $ s_{\lambda} $ be the schur function associated to the partition $ \lambda $.
Cauchy's identity (as in Macdonald) states that
$$
\sum_{\lambda} s_{\lambda}(X)s_{\lambda}(Y) = \prod_{i,j}(1-...