# Questions tagged [co.combinatorics]

6,442 questions

**3**

votes

**0**answers

63 views

### Maximum spanning paths in a graph

Is there any research on the question of finding a spanning subgraph in the form of a collection of independent paths with a maximum number of edges? If the paths are simply edges we have the maximum ...

**7**

votes

**1**answer

174 views

### Counting spanning trees of a planar graph

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...

**3**

votes

**0**answers

51 views

### How likely is a matrix with exactly $n$ number $1$s per row to avoid a large wide empty submatrix?

Consider the finite collection $M(N,n)$ of all $N \times N$ matrices with exactly $n$ entries per row equal to $1$ and all other entries equal to zero $0$.
By an $a \times b$ submatrix of $M$ we ...

**11**

votes

**2**answers

368 views

### Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$

Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...

**5**

votes

**1**answer

107 views

### What is the minimum worst-case length of an element removal game?

A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...

**3**

votes

**0**answers

92 views

### Shifted schur function and holonomic

Now let us denote by $\Lambda^{*}(n)$ the algebra of polynomials in $x_{1},\ldots,x_{n}$ that become symmetric in new variables
$$ x_{i}'=x_{i}-i+c, \ i \in 1,\ldots,n.$$
Here c is a arbitrary fixed ...

**1**

vote

**0**answers

87 views

### Minimal-information description of sudoku solution (Latin square)

Sudoku puzzles consist of a $9 \times 9$ grid of cells in which some cells contain integers from the set $\{ 1, \ldots, 9 \}$ and the task is to fill in the remaining cells such that the numbers $1$ ...

**9**

votes

**0**answers

121 views

### Minimal number of colours in distinguishing colouring of biconnected graphs

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...

**10**

votes

**4**answers

578 views

### A divisibility of q-binomial coefficients combinatorially

Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient ${a+b \choose a}$. I know how to prove this combinatorially - for example after choosing an ordered set ...

**4**

votes

**4**answers

216 views

### Bijective operations on finite simple graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...

**10**

votes

**2**answers

155 views

### The set of polytopes with given $f$-vector

Let $f=(f_0,\ldots f_n)$ be a vector in $\Bbb N^{n+1}$. Let $X$ be the set of all (ordered) $f_0$-tuples in $\Bbb R^n$ whose convex hull has $f$ as its $f$-vector. Assume that $X$ is non-empty. Is ...

**2**

votes

**2**answers

97 views

### Spectral decomposition of a combinatorial matrix/Random walks on $s$-sets

$\newcommand{\Z}{\mathbb{Z}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\la}{\lambda}
\newcommand{\1}{\mathbf{1}}
\newcommand{\R}{\mathbb{R}}$
Take any $n\in[3;\infty]$. Here and in what follows, $[k;\...

**8**

votes

**2**answers

245 views

### Matrix rescaling increases lowest eigenvalue?

Consider the set $\mathbf{N}:=\left\{1,2,....,N \right\}$ and let $$\mathbf M:=\left\{ M_i; M_i \subset \mathbf N \text{ such that } \left\lvert M_i \right\rvert=2 \text{ or }\left\lvert M_i \right\...

**6**

votes

**1**answer

230 views

### Is this bound uniform in $N$?

I encountered this small combinatorial problem and do not quite know how to solve it:
Consider a set $\mathbf N:=\left\{1,2,....,N \right\}.$ This set has $\binom{N}{2}$ many subsets of cardinality $...

**3**

votes

**0**answers

275 views

### Random walk on $\mathbb{R}$ with “sticky” origin

Let $P_i$, $N_i$, and $Z_i$, $i\in\mathbb{N}$ be r.v.'s with the $P_i$, $N_i$, and $Z_i$ being identically distributed with known pdf's $f_P$, $f_N$, and $f_Z$, respectively; and with no dependence ...

**2**

votes

**1**answer

163 views

### The largest number $y$ such that $(x!)^{x+y}|(x^2)!$

Since the multiplication of $n$ consecutive integers is divided by $n!$, then $(n!)^n|(n^2)!$ with $n$ is a positive integer.
Are there any formula of the function $y=f(x)$ that shows the largest ...

**9**

votes

**0**answers

266 views

### Why does Loday call the permutohedra “zylchgons”?

Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...

**2**

votes

**1**answer

77 views

### On submatrices: size bound

Let $M$ be a generic $2n\times 2n$ matrix and fix $k\leq n$.
Suppose $\mathcal{F}$ is a family of submatrices under the conditions that $A\in\mathcal{F}$ provided
(a) $A$ is a $k\times k$ ...

**2**

votes

**1**answer

137 views

### Decide if a system of arithmetic sequences is an $m$-cover of $\mathbb{N}$

Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences.
For a positive integer $m$...

**1**

vote

**1**answer

140 views

### Reference request: Catalan number of type B

Are there some generalized Catalan number of type $B$ such that the sequence of the numbers is $3,9,29,97,333$ for $n=2,3,4,5,6$?
As discussed in this previous question, there are at least two types ...

**13**

votes

**2**answers

503 views

### Seeking a more symmetric realization of a configuration of 10 planes, 25 lines and 15 points in projective space

I've got ten (projective) planes in projective 3-space:
\begin{align}
&x=0\\
&z=0\\
&t=0\\
&x+y=0\\
&x-y=0\\
&z+t=0\\
&x-y-z=0\\
&x+y+z=0\\
&x-y+t=0\\
&x+y-t=0
...

**1**

vote

**1**answer

86 views

### $k$-substrings of a binary string

Let $k > 1,$ and $a=a_1a_2...a_{2k-1}$ be a binary string, i.e. $a_i\in \{0,1\}$. Consider contiguous substrings of $a$ of length $k (k-$substrings$): b_i := a_ia_{i+1}...a_{i+k-1}, 1\leq i\leq k$. ...

**3**

votes

**2**answers

285 views

### how to calculate the following integral related to Chebyshev polynomials

Chebyshev polynomials of the second kind $V_n(x)$ can be defined as
$$V_n(x)=\frac{\sin(n+1)\theta}{\sin\theta}, x=2\cos\theta$$
or through the recurrence relation
$$V_{n+1}=xV_n-V_{n-1}, V_0=1, V_1=...

**8**

votes

**1**answer

313 views

### A combinatorial property of uncountable groups, II

Problem 1. Is it true that each uncountable group $G$ contains two subsets $A,B\subset G$ such that
1) for any $x,y\in G$ the intersection $xA\cap yB$ is finite and
2) for any function $\...

**4**

votes

**1**answer

145 views

### Component properties in Euclidean graphs with distance threshold

In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...

**0**

votes

**1**answer

68 views

### Graphs represented by a subset of a metric space

Let $(X,d)$ be a metric space, and suppose $S\subseteq X$ is a finite subset in which all pairwise distances are distinct (formal definition here).
If $x\in S$ and $k$ is a non-negative integer with $...

**3**

votes

**2**answers

358 views

### Number of self avoiding paths on a grid graph?

Let $G$ be an $n \times n$ grid graph. Is there anything known about the asymptotic growth rate of the number of self avoiding paths from $(0,0)$ to $(n,b)$ (from the lower left corner to some ...

**11**

votes

**3**answers

374 views

### Cardinality of families of subsets of $\mathbb{N}$ whose intersections are finite

Does there exist an uncountable $P \subset \mathcal{P}(\mathbb{N}) $ with the property that for any distinct $x,y \in P$, $|x \cap y|$ is prime?
A more general, but likely harder, question: is it ...

**5**

votes

**0**answers

152 views

### $X$-rays of permutations

Consider the set of permutations $\mathfrak{S}_n$, on $\{1,2,\dots,n\}$, and identify each element $\pi\in\mathfrak{S}_n$ with the corresponding permutation matrix.
There has been some study (e.g. ...

**3**

votes

**1**answer

213 views

### Generating function for 3 -core partitions: Part II

Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...

**4**

votes

**0**answers

84 views

### Number of hereditary modules of a hereditary algebra

Let $Q$ always denote a Dynkin quiver.
Given a connected path algebra $A=kQ$ and a module $M$, is there a useful criterion on $M$ when $End_A(M)$ is again a connected quiver algebra?
Call a module ...

**5**

votes

**4**answers

303 views

### partial alternating sum involving binomial coefficients

I came across the following alternating sum
$$
\sum_{k=0}^n (-1)^k \binom{2n}{k} (n-k)^r,\quad 1\leq r < n.
$$
It seems that when $r$ is an even integer the sum is $0$ and when $r$ is an odd ...

**8**

votes

**1**answer

159 views

### Generating function for $3$-core partitions

Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...

**7**

votes

**1**answer

119 views

### equidistributed parameters on graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...

**4**

votes

**0**answers

167 views

### Two congruence conjectures modulo prime p

How to prove the following two congruences?
Question1: Let $p\equiv 1 \pmod 3$ be a prime, then
$$\sum_{k=0\atop k\neq(p-1)/3}^{(p-1)/2}\frac{\binom{2k}k}{3k+1}\equiv 0 \pmod p.$$
...

**42**

votes

**4**answers

2k views

### A curious process with positive integers

Let $k > 1$ be an integer, and $A$ be a multiset initially containing all positive integers. We perform the following operation repeatedly: extract the $k$ smallest elements of $A$ and add their ...

**7**

votes

**2**answers

182 views

### A link between hooks and contents: Part II

This is a question in the spirit of an earlier problem.
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$.
Recall also the notation for the content of a cell $...

**3**

votes

**1**answer

114 views

### On decomposition of finite Abelian groups

It is easy to see that for any finite Abelian group $G$ and any numbers $a,b$ with $|G|=ab$ there exist a subgroup $A\subset G$ and a subset $B\subset G$ such that $|A|=a$, $|B|=b$ and $G=A+B$, where $...

**6**

votes

**2**answers

136 views

### A link between hooks, contents and parts of a partition

Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Denote its conjugate partition by $\lambda'$. For example, if $\lambda=(4,3,1)$ then $\lambda'=(3,2,2,1)$.
...

**7**

votes

**3**answers

618 views

### Counting configurations on a 2xn board under restrictions [closed]

Find the number of ways of selecting k cells from a $(2\times n)$-board such that no two selected cells share a side (non-adjacent).
For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the ...

**5**

votes

**1**answer

97 views

### SYT and contents of a partition

Let $\lambda$ be an integer partition, denote the number of Standard Young Tableaux of shape $\lambda$ by $f_{\lambda}$. This number is computed by the formula
$$f_{\lambda}=\frac{n!}{\prod_{u\in\...

**2**

votes

**0**answers

23 views

### condition on rational polyhedral cone to guarantee dual cone is homogeneous

Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$).
Definition. The cone $\sigma$ is homogeneous if there are ...

**1**

vote

**0**answers

80 views

### Axiomatization of the shuffle decomposition

I am trying to figure out an axiomatization for Reedy categories such that the product of representables admits a shuffle decomposition. Cisinski suggested imposing a condition, which we will state ...

**9**

votes

**1**answer

253 views

### A binomial determinant formula: a new variant

In a previous MO question, the OP asks a proof for $\det_{1\leq i,j\leq n}\left(\binom{i}{2j}+\binom{-i}{2j}\right)=1$. Subsequently, Gjergji Zaimi generalized the problem to
$$\det_{1\le i,j\le n}\...

**4**

votes

**0**answers

66 views

### Sum of all projective dimensions of simple modules

Let $X_{n,t}$ be the set of all finite dimensional algebras (we can assume they are given by a connected quiver and admissible relations) that have global dimension equal to $n$ and $t$ simple modules....

**4**

votes

**1**answer

210 views

### Understanding proof about chromatic number

Consider an undirected graph $K(n,k,i)$, with the all $k$-element subsets of $\{1,\dots,n\}$ as vertices, and two vertices connected by an edge if their sets intersect in less than $i$ elements.
...

**3**

votes

**1**answer

67 views

### $|V|$ and $|E|$ in hypergraphs with a separation property

Let $H=(V,E)$ be a hypergraph. We call it $T_0$ if for all $x\neq y \in V$ there is $e\in E$ with $\{x,y\}\not\subseteq E$ and $\{x,y\}\cap e\neq \emptyset$ (i.e., $e$ contains exactly one of $x,y$).
...

**10**

votes

**1**answer

202 views

### Orientations of Planar Graphs

Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient
the edges of $G$ such that for each vertex $v$, there are no
three ...

**6**

votes

**2**answers

272 views

### On the parity of $|\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \ j(j+1)\ \text{mod}\ p\,>\,k(k+1)\ \text{mod}\ p\}|$ with $p$ prime

Let $p=2n+1$ be an odd prime, and let $a_1<\ldots<a_{n}$ be all the quadratic residues mod $p$ among $1,\ldots,p-1$. For $a\in\mathbb Z$ let $\{a\}_p$ be the least nonnegative residue of $a$ ...

**3**

votes

**1**answer

158 views

### Partitions and $q$-integers

Denote an integer partition of $n$ by $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_k)$ where $\lambda_k>0$. Also recall the $q$-analogues of integer $n$ given by $[n]_q=\frac{1-q^n}{1-q}$. ...