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.

3
votes
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
4answers
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
4answers
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
2answers
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
2answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
2answers
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
3answers
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
0answers
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
1answer
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
0answers
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
4answers
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
1answer
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
1answer
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
0answers
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
4answers
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
2answers
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
1answer
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
2answers
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
3answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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}$. ...