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

7,207
questions

**0**

votes

**0**answers

8 views

### Bound on the number of unlabeled tree on n vertices

By the Cayley's Theorem, the number of labeled tree on n vertices is at most n^{n-2}. On the other hand, what is the bound on the number of unlabeled tree on n vertices?

**0**

votes

**0**answers

49 views

### About a generalization of complete graphs

Does anyone know what are called (if there is any nomenclature for this class of graphs in the literature) the connected graphs such that each of their edge belongs to some triangle? For example, ...

**0**

votes

**0**answers

15 views

### Additive graph/digraph invariants $f$ and $g$ such that if $f(G)=\min(g(D):D\text{ is an orientation of }G)$ then $f(G)=\min(f(G/uv),f(G+uv))$

If we let $\rho(D)$ be the number of arcs in any digraph $D$ minus the number of arcs in any minimum equivalent subdigraph of $D$, then for every $2$-edge connected graph $G$, is it true for all $u,v\...

**1**

vote

**0**answers

47 views

### Does there exist a subset $E \in \mathbb{Z}_{p^2}^4$ such that $\Pi(E) \neq \mathbb{Z}_p$?

Denote $\mathbb{Z}_{p^2}$ be the ring residues modulo $p^2,$ i.e
$$ \mathbb{Z}_{p^2} = \left\{ 0,1,2,\dots, p^2-1\right\}.$$
$$\mathbb{Z}_{p^2}^{d} = \underbrace{\mathbb{Z}_{p^2} \times \dots \times ...

**3**

votes

**0**answers

65 views

### Counting self avoiding walks in a strip

Consider the strip $\{0,1,\ldots n\}\times\{0,1,2\}$ in $\mathbb{N}^2.$ Is a formula known for the total number of self avoiding walks in this strip starting at $(0,0)$ in terms of the parameter $n$?
...

**1**

vote

**1**answer

70 views

### Find the largest subset of all binary arrays of length $n$ with $r$ ones which have pairwise distance greater than $m$

Let $\Omega = \left\lbrace x : |x| = r \, \text{for} \, x \in \mathbb{Z}_2^n \right\rbrace$ for $r \in \mathbb{N}$. We want to find the the biggest subset of $\Omega$, $\Gamma = \left\lbrace x \in \...

**3**

votes

**0**answers

49 views

### Condition for non-existence of trivial matrix decomposition

Let $A_1,\dots,A_n$ be matrices, with no row or column of $0s$, and such that for every $i=1,\dots,n$ there does not exist a decomposition of $A_i$ of the form
$$
A_i = \oplus_{j=1}^n B_j \qquad (\...

**3**

votes

**1**answer

108 views

### Reference for Dedekind's problem

Dedekind's problem is about enumerating antichains in the Boolean lattice.
Is there an explicit reference where Dedekind stated this problem?
Is there a good motivation to study this problem except ...

**2**

votes

**0**answers

114 views

### Sum of products of irreducible characters of the symmetric group over a subgroup

When trying to build a dual formulation for lattice gauge theories using Weingarten integration I am getting sums of the kind
$$I^{m, n}_{\mu, \nu} (\sigma, \tau) = \sum_{\pi \in S_n} \chi_\mu (\pi \...

**0**

votes

**0**answers

21 views

### hypergraph product that preserve expansion properties

I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2.
The expansion property I am looking at is HD-random walk.
The product I am looking for is ...

**5**

votes

**4**answers

314 views

### Request for an exact formula related to a partition in number theory

The Frobenius equation is the Diophantine equation $$
a_1 x_1+\dots+a_n x_n=b,$$
where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$
must consist of non-...

**4**

votes

**0**answers

86 views

### program to compute hurwitz numbers

Is there a computer program available to compute Hurwitz numbers easily? In fact I only care about counting covers $C\to\mathbb{P}^1$ branched over $0,1,\infty$, and am even willing to restrict to the ...

**1**

vote

**1**answer

35 views

### Vertex connectivity of join of two graphs

Does there exist any results on the vertex connectivity of join of two graphs?
If $G_1$ and $G_2$ are two graphs what can we say about the vertex connectivity of $G_1\lor G_2$ where $G_1\lor G_2$ is ...

**2**

votes

**0**answers

60 views

### On the proportion of simplicial $d$-polytopes on $n$-vertices

I have a question regarding estimates for the proportion of simplicial $d$-polytopes on $n$-vertices.
Let $c_s(n,d)$ denote the number of combinatorial types of simplicial $d$-polytopes on $n$ ...

**1**

vote

**0**answers

130 views

### Questions about a certain sequence of naturals generated by primorials

I'm working on the following sequence of naturals (which is NOT listed in OEIS)
$$3,5,11,17,23,29,59,89,119,149,179,209,419,629,839,1049,1259,1469,1679,...$$
whose elements are generated this way
$$3=(...

**1**

vote

**2**answers

191 views

### Constructing a vector consisting of nonnegative entries

Consider constructing a vector $v=(a_1,a_2,\ldots,a_n)$ consisting of nonnegative integers such that $a_1=1$ and, if $a_j$'s are nonzero, then $a_j\equiv a_{n-j+2}+j-1 \pmod m\ \forall 1<j\le\frac{...

**1**

vote

**0**answers

30 views

### Lower bound for the chromatic number in terms of minimum feedback vertex set

Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$.
We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$
and this bound is sharp.
Is this known or trivial result?
This ...

**1**

vote

**0**answers

42 views

### Yet another graph characteristic

I wonder if the following graph-theoretical concepts have been considered before, and if so, under which name.
Consider a directed graph $G$ with $n$ nodes.
Let the cycle number $\gamma(\nu)$ be ...

**5**

votes

**1**answer

94 views

### Parity of shuffle permutations

A $(p,q)$-shuffle is a permutation $\sigma$ of the set $\{1, \dots, p, p+1, \dots,p+q\}$ such that $$\sigma(1)<\dots<\sigma(p)$$ and $$\sigma(p+1) < \dots<\sigma(p+q)\,.$$
It is known ...

**6**

votes

**0**answers

177 views

+150

### An extension of Erdos' distinct distances problem based on circles of various radii

Consider a collection $C_1,C_2, \dots, C_n$ of circles in the plane and suppose that the center of $C_i$ is $o_i$ and the radius of $C_i$ is $r_i$. We will define the relative distance between the ...

**0**

votes

**0**answers

25 views

### pseudo-Hadamard matrix

What can one say about the matrices M with the following properties:
1) the rows and the columns are indexed by the elements of a finite field with an even number q of elements;
2) All the matrix ...

**0**

votes

**1**answer

85 views

### Question of expected number of consecutive coin flip with increasing bias [closed]

This is a question I found on the book and I don't know how to tackle it. Thanks to any help or hint in advance.
I have a coin that, I could get the head 100% at the first flip, $\frac{1}{3}$ at the ...

**3**

votes

**0**answers

130 views

### A fusion ring identity

Fusion rings
I'll more or less stick to the presentation given in this question: [1]
We define a fusion ring as follows: consider a free $\mathbb{Z}$-module $\mathbb{Z}\mathcal{B}$ with finite basis ...

**12**

votes

**1**answer

313 views

### Yet another real-rooted polynomial

In this entry I asked for the real-rootedness of a polynomial, and two very interesting answers were given: one using Malo's theorem and the other a clever rewriting of the expression using Jacobi ...

**0**

votes

**0**answers

41 views

### A ballot-casting problem

For any set $X$ and cardinal $\kappa$ let $[X]^\kappa$ denote the collection of subsets of $X$ with cardinality $\kappa$. If $n$ is a positive integer, let $[n]:=\{1,\ldots,n\}$.
Let $V$ and $K$ be ...

**2**

votes

**0**answers

91 views

### Solving general two-dimensional recurrence relation

Any techniques for deriving a closed form solution for the following recurrence relation? Or bounds on asymptotic behavior for large $n$?
$$a_{n+1,k} = \sum_{0 \le i \le n} \frac{n!}{i!} a_{i,k-1}$$
...

**5**

votes

**1**answer

211 views

### RSK correspondence

Up to now, what are the difference ways we know to define RSK correspondence? I already know:
By insertion and recording tableau.
Ball construction or Viennot's geometric construction.
Growth diagram ...

**1**

vote

**0**answers

44 views

### Partitionability and colorability of hypergraphs

Motivation. If $\kappa\neq\emptyset$ is a cardinal, then a simple, undirected graph $G=(V,E)$ is $\kappa$-colorable if and only if there is a partition of $V$ into at most $\kappa$ blocks such that ...

**4**

votes

**2**answers

282 views

### Are $n \times n$ special orthogonal matrices, all the entries of which have the same absolute value, possible for $n \neq 4$?

As I noted in my preceding question https://math.stackexchange.com/questions/3510189/give-a-general-class-to-which-a-specific-4-times-4-special-orthogonal-matrix
in equation (62) of their recent ...

**0**

votes

**0**answers

110 views

### Reference for discrete Laplacian on $\mathbb{Z}$

For $x\in \mathbb{R}^\mathbb{Z}$, let the discrete Laplacian be defined as
\begin{align*}
(\Delta x)_k = 2x_k-x_{k+1}-x_{k-1}.
\end{align*}
I am looking for good references about its spectrum (or ...

**0**

votes

**1**answer

53 views

### Matching book embedding of Cartesian products of graphs

In the book embedding of a graph $G$ , each vertex of $G$ is placed on the spine and each edge is placed in the pages without crossing each other edge. If vertices have degree at most one in each ...

**17**

votes

**3**answers

722 views

### Cyclic action on Kreweras walks

A Kreweras walk of length $3n$ is a word consisting of $n$ $A$'s, $n$ $B$'s, and $n$ $C$'s such that in any prefix there are at least as many $A$'s as $B$'s, and at least as many $A$'s as $C$'s. For ...

**7**

votes

**1**answer

129 views

### 3 term van der Waerden with large step size

Let $P(n)$ be the statement "any $n$ coloring of $\mathbb{N}$ contains a monochromatic progression $a, a+d, a+2d$ such that $d>a$".
For which $n$ is $P(n)$ true?
It's easy to see that $P(2)$ is ...

**5**

votes

**1**answer

120 views

### Using irreducible characters of the orthogonal group as basis for homogeneous symmetric polynomials

The irreducible characters of the orthogonal group $O(2N)$ are given by
$$ o_\lambda(x_1,x_1^{-1},...x_N,x_N^{-1})=\frac{\det(x_j^{N+\lambda_i-i}+x_j^{-(N+\lambda_i-i)})}{\det(x_j^{N-i}+x_j^{-(N-i)})}...

**2**

votes

**1**answer

84 views

### construct a bijective map between subsets of binary sequence

Consider the binary sequence $\{0,1\}^N$ where $N$ is an even integer (for simplicity). Let $M_k := \{\beta\in \{0,1\}^N \rvert \sum_{j=1}^N \beta_j = k\}$ (i.e., $M_k$ is the set that contains all ...

**7**

votes

**2**answers

189 views

### Does minimal degree $n$ imply a $K_n$ minor

Is it true that any finite graph has a $K_n$ minor, where $n$ is a minimal vertex degree?

**5**

votes

**0**answers

58 views

### Partitioning the set of Pauli words into abelian pieces

Let $\sigma_x,\sigma_y,\sigma_z$ be the Pauli matrices. A Pauli word of length $n$ is defined as the tensor product $\otimes_{i=1}^n\sigma_i$ of operators $\sigma_1,\dots,\sigma_n\in\{\mathbf 1,\...

**18**

votes

**2**answers

1k views

### Real rootedness of a polynomial

Let's consider $m$ and $n$ arbitrary positive integers, with $m\leq n$, and the polynomial given by:
$$ P_{m,n}(t) := \sum_{j=0}^m \binom{m}{j}\binom{n}{j} t^j$$
I've found with Sage that for every $...

**3**

votes

**0**answers

57 views

### Relations between double coinvariants and affine Springer fibers

Diagonal coinvariants have an interpretation from https://arxiv.org/abs/math/0201148 in terms of the Hilbert scheme.
There are two recent papers https://arxiv.org/pdf/1801.09033.pdf and https://arxiv....

**0**

votes

**0**answers

22 views

### Tutte 1-factor theorem to prove total chromatic number of complete multipartite graphs

Consider a complete multipartite graph on $n$ vertices having maximum degree $\Delta$. Then, it is known that the total chromatic number of the graph is $\le\Delta+2$. The proof uses the fact that a ...

**3**

votes

**1**answer

71 views

### Bounding number of k-cycles in a graph

Fix any $k \geq 3$, and suppose I have a simple undirected graph $G=(V,E)$. I want a bound on the number of $k$ cycles in $G$ as a function of $|E|$. In particular, I would like to prove the following ...

**8**

votes

**3**answers

418 views

### Looking for a “cute” justification for a Catalan-type generating function

The Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ have the generating function
$$c(x)=\frac{1-\sqrt{1-4x}}{2x}.$$
Let $a\in\mathbb{R}^+$. It seems that the following holds true
$$\frac{c(x)^a}{\sqrt{1-...

**1**

vote

**0**answers

80 views

### Relation between the number of spanning trees and the chromatic number of a graph

The number of spanning trees $\tau(G)$ of a simple graph $G$ is seen to satisfy the deletion-contraction recurrence:
$$\tau(G)=\tau(G-e)+\tau(G.e),$$
where $e$ is an edge of the graph $G$ and $G-e$ ...

**4**

votes

**1**answer

210 views

### Does the lattice of partitions map onto the lattice of subsets?

Let $X\neq \emptyset$ be a set and let $X^X$ denote the collection of all functions $f:X\to X$. We put a binary relation (reflexive and transitive), the composition preorder on $X^X$ by setting for $f,...

**16**

votes

**3**answers

574 views

### Plane partitions with equal margins

A plane partition of $n$ is an table of integers $A=(a_{ij})$ which add up to $n$ and non-increase in rows and columns. For example,
$$A= \begin{matrix} 331 \\
32 \ \ \\
11 \ \
\end{matrix}
$$
is a ...

**2**

votes

**1**answer

72 views

### Nash equilibria for “presidential election” game

Suppose, in a country there are $m$ different social issues, positions on which are being indexed with numbers $[-1; 1]$, with radicals on the opposing ends and moderates in the center. In this ...

**4**

votes

**0**answers

56 views

### Frobenius dimensions of Nakayama algebras

The Frobenius dimension $F(A)$ of an Artin algebra $A$ is given by the dimension of $Hom(D(A),A)$ (see the answer in On nearly Frobenius algebras ).
Question 1: Is it true that $F(A) \geq gldim(A)$ ...

**5**

votes

**3**answers

568 views

### Update on “Hopf algebras: their status and pervasiveness” by Hazewinkel

Hazewinkel wrote this article in 2005. Perhaps it's time for an update.
For example, updating item
34: Ordinary differential equations much work has been done on the underlying Hopf algebra (HA) of ...

**16**

votes

**4**answers

967 views

### Can I build infinitely many polytopes from only finitely many prescribed facets?

Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$.
Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...

**2**

votes

**1**answer

129 views

### How to show that $x_{k+1}+x_{k+2} + \cdots + x_n < 2m$?

Let $k \le n$ be positive integers and let $m$ be a positive integer. Assume that $x_1, \ldots, x_n$ are non-negative integers and
\begin{align}
& x_1^2 + x_2^2 + \cdots + x_n^2 - (k-2) m^2=2, \\
&...