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

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

9,422
questions

-5
votes

0
answers

31
views

An n by n matrix with nonnegative real entries is called nice if each row and each column
sums to 1. An n-by-n matrix is called a permutation matrix it has exactly one 1 in each row
and column and has ...

1
vote

0
answers

37
views

The graph removal lemma says that for any graph $H$ and any $\epsilon>0$, there is a $\delta>0$ such that any $n$-vertex graph which contains at most $\delta n^{v(H)}$ copies of $H$ can be made $...

1
vote

0
answers

42
views

Suppose $Q$ and $Q'$ are two quivers. I am curious as to what relation $\mathbb{C}Q$ bears to $\mathbb{C}Q'$ when $Q$ and $Q'$ share the same underlying graph and only differ by direction.
Since ...

0
votes

0
answers

45
views

I started studying on the subject of discrete Mathematics and I came across the following question:
Let $a_n := \lvert\{\pi \in S_n : \text{$\pi(i) \neq i$ for all odd $i$}\}\rvert$ and we denote the ...

1
vote

1
answer

101
views

I have a cube $X\in \mathbb R^{N\times N\times N}$ such that no matter how the cube is rotated by $90^\circ$ along any of the axes, the result is unchanged. What is the maximum number of distinct ...

1
vote

1
answer

93
views

Recently, I came across the notion of quasi-isometries, while thinking of "discrete spaces which are surrogates for approximate continuous ones".
What (metric)/geometric properties are ...

2
votes

0
answers

29
views

Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side.
For sets $X \subseteq U$ and $Y \subseteq V$,
let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...

2
votes

1
answer

81
views

If $X$ is any set, we let $[X]^2:=\big\{\{x,y\}:x\neq y\in X\big\}$. If $G=(V,E)$ is an undirected graph and $v\in V$, we define $N_G(v) = \{w\in V:\{v,w\}\in E\}$.
For $i =1,2$, let $G_i=(V_i,E_i)$ ...

2
votes

1
answer

135
views

Given a simple graph $G=(V,E)$, we can consider matchings, $M\subseteq E$,
where $M$ is a matching iff no vertex is shared between different edges.
The number of edges in $M$ is denoted $|M|$.
The ...

2
votes

0
answers

67
views

We call a graph $G=(V,E)$ $k$-sparse if there is a partition $E = \bigcup_{i = 1}^k E_i$ of the edges into $k$ disjoint parts such that each graph $(V,E_i)$ is a forest.
I am trying to prove that $k \...

6
votes

1
answer

315
views

I work with centrosymmetric matrices and recently have started exploring the question of the existence of centrosymmetric Hadamard matrices.
Definition: An $n \times m$ matrix $A = (a_{i,j})$ is ...

7
votes

0
answers

391
views

In their landmark paper from 1977 named "A Variational Problem for Random Young Tableaux" Logan and Shepp obtained a number of results concerning asymptotic properties of Young Diagrams ...

1
vote

0
answers

86
views

Let $L$ be a link in $\mathbb{R}^3$, with $D, D'$ be diagrams in
$\mathbb{R}^2$ representing $L$. Khovanov constructed two graded
chain complexes $$C_{D} = (Ch_{D}, d_{D}) \quad C_{D'}=(Ch_{D'},
d_{D'}...

-4
votes

0
answers

79
views

Given a complete graph $K_n$. The rooted spanning tree is a directed spanning tree where each vertex has out-degree exactly 1 and the root vertex has out-degree zero.
What exactly is the number of ...

5
votes

0
answers

77
views

The $\tau$-function $H^\circ \big(t ;\vec{x} \big)$ associated with counting simple Hurwitz numbers is the formal power series
\begin{equation}
(\dagger) \quad H^\circ \big(t ;\vec{x} \big) \, =
\,
\...

3
votes

0
answers

146
views

+100

I have constructed two polyhedrons as follows:
There are $\binom{6}{3}$ triangles and $\binom{6}{2}$ squares. Every triangle is connected via an edge with $3$ distinct squares (one for each vertex of ...

8
votes

2
answers

162
views

For the symmetric group on $n$ objects $S_n$ the question of how to write its longest element $w_0$ as a reduced decomposition is an important combinatorical problem. As example, in this question the ...

0
votes

0
answers

81
views

Consider a vector of components which are listed in lexicographic order: $\boldsymbol{z} = (z_{1,2},z_{1,3},\dotsc,z_{1,K}, z_{2,3},z_{2,4},\dotsc,z_{2,K},\dotsc,z_{i,i+1},z_{i,i+2},\dotsc,z_{i,K},\...

2
votes

0
answers

76
views

Working on suitable closed form for A329369, I discovered very useful coefficients, which have the following recurrence relation:
$$T(0,1)=T(0,2)=1$$
$$T(n,1)=1, n>0$$
$$T(0,k)=0, k>2$$
$$T(2n+1,...

0
votes

0
answers

45
views

Let $A$ be the family of axis-parallel boxes in the $d$-dimensional unit cube $[0,1]^d$ having one vertex at the origin. It is known that the VC dimension of $A$ is $d$. Let $B$ be the family of all ...

4
votes

0
answers

62
views

This question is cross-posted from https://math.stackexchange.com/questions/4580314/asymptotic-expansion-for-the-number-of-self-avoiding-random-walks.
Let $c_n$ be the number of self-avoiding random ...

2
votes

0
answers

91
views

Let $q(n)$ be A007814, i.e., the number of trailing zeros in the binary representation of $n$. Here
$$q(2n+1)=0, q(2n)=q(n)+1$$
Let $a(n)$ be A329369. Here
$$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(...

1
vote

1
answer

81
views

Following to my previous question on the same topic, I would like to have some opinions whether the present refinement have some chances to work or is doomed to fail.
Given the positive integers $n$ ...

3
votes

1
answer

162
views

I recently asked in this thread about lower bounds on the complexity in the case where we have an aperiodic subshift. If I denote $c_n(\Omega)$ as the number of possible patterns on $Q_n= \big\{ 0,...,...

1
vote

1
answer

71
views

This question arises from a request for an algorithm to do such, from 9 sets of 12 elements, arrange 12 groups of the 9 elements, selecting 1 element from each set
Given a set, $S$, of sets, $S_i$, $\...

1
vote

2
answers

176
views

Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.
For which values of $n$ and $m$ does the following requirement hold:
$\forall G \in \...

1
vote

1
answer

228
views

We are given $1\leq S \leq 10^9$ and $1 \leq P \leq 10^9$.
We need to pick $k$ integers $x_1, x_2, \dotsc, x_k$ (all of which have to be $>1$) such that $\sum_k{x_k}=S$ and $\prod_k{x_k}=P$.
What ...

2
votes

1
answer

99
views

For a given integer $n$, I am interested in the number of different numerical semigroups one can make with a generating set consisting only of integers in $[n]$.
I have done some small examples. For $...

0
votes

1
answer

149
views

This question is on the same topic of this one, but simpler, and I have also included some numerical tests here.
Consider a $h \times (n-1-h)$ matrix $A$ with all entries $a_{ij}$, $1 \le i \le h$, $1 ...

3
votes

0
answers

77
views

It is well-known that many classes of graphs have matrix representations that can be written concisely. For example,
The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...

9
votes

1
answer

279
views

Let $n > 13$ be a positive integer. Is there any $n\times n$ circulant $(-1,1)$-matrix $A$ satisfying the following property:
$$AA^T=(n-1)I+J$$
where $I$ is the $n\times n$ identity matrix and $J$ ...

11
votes

2
answers

856
views

Suppose $m$ is a positive integer.
I am looking for finite sets with group actions such that the action is transitive on the set of $m$-element subsets, but NOT transitive on the set of $(m+1)$-...

1
vote

1
answer

76
views

$\DeclareMathOperator\inc{inc}$Let $|X|=n$ and $\inc(X,\leq)=\{\{x,y\} : \neg (x\leq y)\wedge \neg (y\leq x)\}$, where $(X,\leq)$ is poset (possibly unconnected). Define the function:
$$\pi(n,m):=|\{(...

1
vote

1
answer

102
views

(See also this similar question).
Consider a $h \times 4n-h$ binary matrix (a matrix with all entries $a_{ij}$, $1 \le i \le h$, $1 \le j \le 4n-h$, equal to $0$ or $1$). We know that each row has $2n$...

4
votes

0
answers

86
views

For a fixed partition $\lambda=(\lambda_1\geq\dots\geq \lambda_n)$ we say $\mu=(\mu_1\geq \dots \geq \mu_{n-1})$ $\textit{interlaces}$ $\lambda$ iff
$$\lambda_1\geq \mu_1\geq \dots \geq \mu_{n-1}\geq \...

0
votes

0
answers

22
views

It has been known for long (Molloy and Reed 1995) that in a supercritical undirected configuration model, that is when $E[D(D-2)]>0$, $D$ degree of a uniform vertex, the size of the second largest ...

3
votes

0
answers

169
views

Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...

11
votes

1
answer

276
views

Let $\phi(x,y,z)$ be an alternating trilinear form on a space $V$ over a field $K$.
Let $u \in \mathbb{P}(V)$ be a projective point over $V$, then we say that the rank of $u$ is equal to the rank of ...

0
votes

0
answers

92
views

Let $q(n)$ be A007814, i.e., number of trailing zeros in the binary representation of $n$. Here
$$q(2n+1)=0, q(2n)=q(n)+1$$
Let $a(n)$ be A329369. Here
$$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(2n-2^{...

1
vote

0
answers

70
views

These days I have been reading about Keller's cube tyling conjecture, which asks if in any covering of $\mathbb{R}^n$ by translates of $[0,1]^n$ with disjoint interiors there are two cubes sharing one ...

1
vote

0
answers

54
views

In an Erdos-Renyi graph with labeled vertices in $(1, ..., N)$, and for any pair of vertices $(r, s)$ with $r < s$ and a length $l$ in $(1, ..., s-r)$, I am looking for the probability of
there ...

5
votes

1
answer

192
views

As the title says. Which finite projective planes admit a symmetric incidence matrix?
I am not an expert in the field at all, but I consulted with one. He claimed that $PG(2, \mathbb F_q)$ can always ...

8
votes

1
answer

518
views

Given the famous Littlewood-Richardson rule, in terms of Schur polynomials:
$$s_\mu s_\nu=\sum_\lambda c^{\lambda}_{\mu\nu} s_\lambda,$$
is there a classification of the cases where the LR ...

0
votes

0
answers

62
views

For $\triangle f(x) = f(x + 1) - f(x)$ and $\triangle^{m}f(x) = \triangle(\triangle^{m - 1}f(x))$ (for $m$ a positive integer), is it true that $\triangle^{m}x^{n} = 0 \implies Re(x) = -\frac{m}{2}$ (...

1
vote

1
answer

73
views

For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...

1
vote

0
answers

80
views

Let $V = \mathbb{Z}_{\geq 0}$ be the set of integers and let $\mathcal{G} = (V, E)$ be an (undirected) Rado graph on $V$. Let $W = \bigoplus_{i = 0}^{\infty} \mathbb{F}_2$ and write $x_i$ for the $i$-...

7
votes

0
answers

137
views

We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...

2
votes

1
answer

183
views

History of the question. I was proposing a conjecture here, called Prop. 1. Fedor Pakhomov showed a counter-example. Here I am proposing a slightly weaker version of the conjecture, Prop. 2, that ...

3
votes

0
answers

136
views

Fix a $n \times m$ rectangle and consider the set $S_{n,m}$ of all its dominos tilings.
Here are examples with $n=m=8$.
The set $S_{n,m}$ is empty if and only if $nm$ is odd, and for small $nm$, its ...

8
votes

1
answer

190
views

EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. In this new question I propose a slightly weaker conjecture that holds even for that example and ...