# 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

**7**

votes

**0**answers

236 views

### When does a graph have a minimally strong orientation?

Given any asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for every arc $a\in A$ the digraph $D−a=(V,A\setminus\{a\})$ is not strongly ...

**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?

**14**

votes

**7**answers

2k views

### A special type of generating function for Fibonacci

Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$.
Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them:
$$\...

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

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

**5**

votes

**4**answers

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

**20**

votes

**1**answer

570 views

### To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where
$$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$
I found that if the path $P$ satisfies:
...

**4**

votes

**2**answers

388 views

### What generalizes symmetric polynomials to other finite groups?

Multivariate polynomial indexed by ${1, \ldots, n}$ are acted on by $S_n$: for $\sigma \in S_n$, define $\sigma(x_i) = x_{\sigma(x_i)}$, etc. Symmetric polynomials are those polynomials which are ...

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

**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$?
...

**19**

votes

**1**answer

3k views

### Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq:
Gonthier, Georges. Formal proof—the four-color theorem.
Notices Amer. ...

**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

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

**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 (\...

**6**

votes

**1**answer

296 views

### Rank and frequency of permutations

(a) Let $[n] = \{1,\dotsc,n\}$, and let $\pi:[n]\to [n]$ be a permutation. Define an $n$-by-$n$ matrix $A=A(\pi)$ as follows: $A_{i,j}=1$ if $j>i$ and $\pi(j)>\pi(i)$, $A_{i,j}=-1$ If $j<i$ ...

**8**

votes

**3**answers

509 views

### Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?

**1**

vote

**1**answer

79 views

### Circular (bracelets) permutations with alike things(reflections are equivalent) using polya enumeration

Circular permutations of N objects of n1 are identical of one type, n2 are identical of another type and so on, such that n1+n2+n3+..... = N?
A similar question exists but it doesn't address the case ...

**1**

vote

**1**answer

3k views

### Number of graphs with $n$ edges

I have been trying to count the number of graphs up to isomorphism which are:
Simple
Connected
Have $n$ edges.
I apologize in advance if there is ample documentation on this question; however, I ...

**5**

votes

**2**answers

1k views

### A sum involving irreducible characters of the symmetric group

Recently, during the research, I came across a sum, denoted by $H(n,L)$, involving irreducible characters of the symmetric group,
\begin{equation}
H(n,L)\colon=\sum_{Y_{i,j,w}} \frac{\chi^{Y_{i,j,w}([...

**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{...

**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 \...

**30**

votes

**5**answers

5k views

### How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...

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

**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$ ...

**11**

votes

**2**answers

250 views

### Big mono-chromatic subgraphs of vertex 2-colourings

I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V \...

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

**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

**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=(...

**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

**1**answer

53 views

### Finding a cycle of a specific length in an edge-weighted graph

I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph.
For example, imagine my phone tells me that I need to walk three miles today. It ...

**113**

votes

**61**answers

24k views

### Important formulas in combinatorics

Motivation:
The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...

**6**

votes

**2**answers

239 views

### Multivariate Lagrange inversion with zero powers

(Also asked on MSE)
The multivariate Lagrange inversion formula, which I found in a couple of papers (such as this and this), is as follows. If $f_i=t_ig_i(f)$, $1\le i\le k$, then
$$ [t^n]h(f(t))=\...

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

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

**4**

votes

**1**answer

288 views

### Is there an integral fusion ring which is not of Frobenius type?

Combinatorially, a fusion ring $\mathcal{F}$ is nothing but a finite set $B=\{b_1, \dots, b_r\}$ (generating the $\mathbb{Z}$-module $\mathbb{Z} B$) together with fusion rules: $$ b_i \cdot b_j = \...

**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

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

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

**8**

votes

**2**answers

323 views

### Are these two combinatorially-defined sets of integers disjoint?

Fix an integer $n\geq 8$. For each integer $i\leq n/2$, denote by $X_i$ the set
$$X_i = \left\{ \frac{n-i+1-k}{n-i+1}\binom nk\binom{k-1}{i-1} ~\middle|~~ i\leq k\leq n-i\right\}.$$
The ...

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

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

**4**

votes

**1**answer

176 views

### Information for discovering an item-colour assignment in a combinatorial game

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...

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

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

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