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

**2**

votes

**2**answers

831 views

### Invariants of Matrix Reordering

are there any invariants of matrices, that are not affected by row- and/or column permutations?
To me it seems that the sequence of singular values could be such an invariant; am I right, resp. are ...

**2**

votes

**1**answer

144 views

### Number of members of a separating union-closed family whose universe has given cardinality

If I'm not wrong, it is easy to prove the following statement:
If $n \leq 4$ is a natural number, if $\mathcal{F}$ is a union-closed family of non-empty sets, if the universe of $\mathcal{F}$ (i.e. ...

**2**

votes

**1**answer

98 views

### Neighborhood maps for graphs $G$ with $\delta(G) \geq 2$

Let $G= (V,E)$ be a simple, undirected graph. For $v\in V$ we set $N(v) = \{w\in V: \{v,w\} \in E\}$. Note that we always have $v\notin N(v)$. A function $f:V\to V$ is said to be a neighborhood map if ...

**2**

votes

**4**answers

445 views

### Discriminants of indefinite integral binary quadratic forms admitting 3 or 6 torsion.

Are there any results known about the discriminants of indefinite integral binary quadratic forms admitting automorphisms of order 3 or 6? It seems reasonable to expect that any permissible ...

**2**

votes

**0**answers

117 views

### Link of a power series by the Bernoullis for a Riccati equation to zonotopes?

On pg. 85 of The Rise and Development of Theory of Series up to the Early 1820s by Ferraro is a series soln. of
$$ d^2z/z = -x^2dx^2 $$
related to the reputed first appearance of a Riccati-type eqn.,...

**2**

votes

**1**answer

399 views

### Proof that the $\omega$-language consisting of all words containing every finite word as a factor is not rational/regular

Let $\eta$ be an $\omega$-word over $X = \{0,1\}$ and let $F_k(\eta)$ denote the factors of $\eta$ of length $k$. Define the following $\omega$-languages
$$
L_k := \{ \xi : F_k(\xi) = X^k \} = \{ \xi ...

**2**

votes

**1**answer

164 views

### Asking for an example of a graph $G$ satisfying the following property

This question comes from another question I submitted earlier.
Let $G$ be a finite graph. For any independent set $S$ in $G$ with $|S|\geqslant2$ and $v\in S$, define
$$d_S(v)=\mid\{u\in V(G)\...

**2**

votes

**2**answers

315 views

### Irreducible Polynomials from a Reccurence

This question is inspired by a recent one : Let $c$ be a variable and define a sequence by $a_0=0$ $a_1=1$ and $a_{n+1}=a_{n}c-a_{n-1}$ . So
$$\begin{align*}
a_2 &= c
\\ a_3 &={c}^{2}-1= \...

**2**

votes

**0**answers

140 views

### Sylvester-Gallai-type theorem for quadratic polynomials

Let $F_1, F_2$ and $F_3$ be finites sets of irreducible polynomials in $\mathbb{C}[x_0, \ldots, x_n]$ of degree at most $2$ such that $F_1 \cap F_2 \cap F_3 = \varnothing$ and for every $Q_1, Q_2$ ...

**2**

votes

**1**answer

115 views

### Asymptotic behaviour of fixed points in permutations

For any $n\in\mathbb{N}$ let $S_n$ denote the set of all permutations (bijective maps) $\pi:\{1,\ldots, n\} \to \{1,\ldots,n\}$. For $\pi \in S_n$ we set $$\text{fix}(\pi) = \{x\in \{1,\ldots, n\}: \...

**1**

vote

**0**answers

66 views

### Number of misplaced elements for a partition of a set of coloured items

We are given a set $V$ of $n$ items, where each item is tinted with exactly one color in $C=\{c_1, c_2, \ldots, c_k\}$, in such a way that for each $i\in [k]$ there exists at least one item tinted ...

**1**

vote

**2**answers

2k views

### On the number of antichains of a poset

I am not an expert in combinatorics, but I need to count (or to approximate) the number of antichains of a poset.
The idea relies on approximating this number by embedding my poset into another one, ...

**1**

vote

**1**answer

181 views

### Infinite graph with degrees given

Let $\kappa$ be an infinite cardinal and suppose $$n, d: \kappa \to \big((\kappa+1)\setminus \{0\}\big) = \{1, \ldots, \kappa\}$$ are arbitrary functions.
Is there $E \subseteq \big\{\{x,y\}: x\neq y ...

**1**

vote

**1**answer

449 views

### Some divisibility constraints in Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...

**1**

vote

**2**answers

144 views

### A recursive Double sequence related to uniform Cardinal B-spline

Given a sequence $A_n(k)$ defined as follows:
$A_0(0)=1$, $A_0(k)=0$ for all nonzero integers $k$ and
$$A_{n}(k)=(n+1-k)^2A_{n-1}(k-1)+2(n(n+1)-k^2)A_{n-1}(k)+(n+1+k)^2A_{n-1}(k+1)$$
for all positive ...

**1**

vote

**0**answers

95 views

### cospectral graphs have isomorphic adjacency matrices?

Let $G$ and $H$ be two cospectral graphs, then can we say that their adjacency matrices are isomorphic?

**1**

vote

**1**answer

283 views

### Relationship of clique, independence, and chromatic numbers

For any graph $G=(V,E)$ let $\bar{G}$ be the complement graph. Is $$\text{inf}\big\{\frac{\omega(G)+\omega(\bar{G})}{\chi(G)} : G \text{ is a finite graph}\big\}$$ known? If not, what lower bounds are ...

**1**

vote

**0**answers

128 views

### Indecomposability of image transformations (pure algebra). Open questions

W-transformations -- definitions
We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...

**1**

vote

**1**answer

651 views

### Pros and cons of probability model for permutations

I am studying probability model of random permetuation
Let $b(n; k)$ denote the number of permutations of {1,...,n} with precisely k
inversions ($inv(\pi)$). The analytic approach was considered by L....

**1**

vote

**1**answer

142 views

### linear recurrence inequality of positive terms

This is a follow up on my previous linear recurrence inequality question.
I have some matrices which satisfy a linear recurrence formula of the form
$$
A_{n+1} = \alpha A_{n} + \beta A_{n-1},\qquad n\...

**1**

vote

**2**answers

46 views

### Achieving every possible ranking by rearranging weights

This problem actually arose as a question in the real world (see the paragraph "Origin of the problem" below).
Let $\mathbb{N}$ denote the set of the positive integers and let $n\in\mathbb{N}$. If $...

**1**

vote

**1**answer

315 views

### Is the number of vertices bounded for fixed max degree and fixed diameter?

Are there positive integers $\Delta, d$ such that the following statement is true?
For every $n\in \mathbb{N}$ there is a graph $G = (V,E)$ such that $|V| = n$,
$\Delta(G) \leq \Delta$ (...

**1**

vote

**4**answers

383 views

### All possible linear combinations of positive half-integers with coefficients +/- 1

This will be a simple problem on paper, but the brute force method is not really suitable for a computer, so I'm after a tricky algorithm that works in practice too: if $n$ positive half-integers $p_i$...

**1**

vote

**2**answers

164 views

### Linear Extension of the $n\times n$ lattice

I am looking at a particular integer sequence, the number of $n\times n$ Young Tableaus (see OEIS). In the comments at OEIS, Mitch Harris stated that the same sequence also defines the
Number of ...

**1**

vote

**1**answer

212 views

### Odd permutations $\tau\in S_n$ with $\sum_{k=1}^nk\tau(k)$ an odd square

For any positive integer $n$, as usual we let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each integer $n>3$ there is an odd permutation ...

**1**

vote

**1**answer

199 views

### Generating function for $t$-residues of partitions using Heisenberg + $\hat{sl_t}$ representation theory

Recall that for $t\geq2$, a partition is a $t$-core if none of its hooklengths is divisible by $t$. It is known that the $t$-cores are parametrized by ${\mathbb Z}^{t-1}$. More precisely, let $(n_0,\...

**1**

vote

**1**answer

426 views

### Coefficients in the sum $\sum_{k=0}^{n-1}\sum_{j=0}^{m}A_{j,m}(n-k)^jk^j=n^{2m+1}, \ m=1,2,…$

Consider a sum $$\sum_{k=0}^{n-1}\sum_{j=0}^{m}A_{j,m}(n-k)^jk^j$$
which returns an odd power $n^{2m+1}$ of $n$, for $\ m=0,1,2,...$ given fixed $A_{0,m}, \ A_{1,m}, \ ..., \ A_{m,m}$. The ...

**1**

vote

**3**answers

162 views

### A problem with an edge labeling on the boolean lattices

Let $B_n$ be the boolean lattice of rank $n$. Let $\hat{0}$ and $\hat{1}$ be the minimum and the maximum, respectively.
We identify the notion of edge with the notion of interval $[a,b]$ of cardinal $...

**1**

vote

**1**answer

139 views

### Linear independence of +/- 1 strings/vectors

Let $V=\left\{-1,1\right\}^{n}$. Consider three vectors $v_1,v_2,v_3\in V$. I would like to know whether these vectors are linearly independent over $\mathbb{Z}$. To be more precise - I need a ...

**1**

vote

**0**answers

87 views

### Hook-content polynomial 2

Recently I have proven the following identity
\begin{align}
\sum_{\lambda\in \text{different hook of size d}} \frac{1}{d!} (-1)^{ht(\lambda)-1} \, \dim \lambda \, \prod_{\Box \in \lambda} \frac{1}{1-...

**1**

vote

**0**answers

78 views

### Does the convex-hull of a set contain zero (II)?

Let $(\lambda_1, \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Suppose we have $k$ non-zero vectors $\alpha^{(j)} = (\alpha^{(j)}_1, \cdots , \alpha^{(j)}_d) \in \mathbb{Z}^d$, ...

**1**

vote

**1**answer

347 views

### Nested De Bruijn Sequences

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1 a_2 \dots a_{2^n},$ with $a_i \in \{0,1\},$ and such that each of the $2^n$ binary $n$-uples occurs exactly once in $S.$
Is ...

**1**

vote

**1**answer

182 views

### Can this particular random matrix model be converted/related to any existing graph theory model?

Context:
This a sequel to the question: Is the Erdős–Rényi giant component result applicable here?
Consider a matrix whose elements are independently assigned a value
$1$ with probability $p$ ...

**1**

vote

**0**answers

345 views

### Has anyone seen this version of ring toss (combinatorial object) before?

In reference to a
question on work of Westzynthius and another
question relating to Jacobsthal's function, I have formed a game which I immodestly call Paseman's Ring Toss. I hope that it has been ...

**0**

votes

**1**answer

97 views

### Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...

**0**

votes

**1**answer

210 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**0**

votes

**1**answer

92 views

### Walking “withouth gaps” through a set of sets

Let $X\neq \emptyset $ be a finite set and suppose that ${\cal C}$ is a set of subsets of $X$ with the following properties:
$X\notin {\cal C}$, and
for all $x,y\in X$ there is $A\in {\cal C}$ such ...

**0**

votes

**0**answers

164 views

### Parity of number of partitions of $n!/6$ and $n!/2$

The parities of the number of partitions of $n!/6$ and $n!/2$ appear to be non-random initially, as follows — is there an explanation for this other than chance? With $p$ being the partition ...

**0**

votes

**1**answer

390 views

### Asymptotic behaviour of Binomial Sum

I am interested in the behaviour of:
$\gamma_k=\sum_{i=0}^{k} {n \choose i}$
as n becomes large and where $k$ could potentially be a function of $n$ rather than a constant. One line of attack I can ...

**0**

votes

**0**answers

117 views

### Permutations $\pi\in S_n$ with $p_k+p_{\pi(k)}+1$ prime for all $k=1,\ldots,n$

As usual, let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is my following conjecture true?
Conjecture. For any positive integer $n$, there is a permutation $\pi\...

**0**

votes

**0**answers

159 views

### A combinatorial 0-1 matrix problem

Let $M \in \{0, 1\}^{n\times n}$.
Given a constant integer $c \ge 2$, let the number of $1$s in each row be equal to $n/c$ (assuming $c$ is a divisor of $n$).
Given a constant $\beta \in (0,1)$, we ...

**-1**

votes

**2**answers

249 views

### Selection problem in a collection of non-empty sets

Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ of non-empty subsets of $X$ with the following properties?
$a\in {\cal F} \implies |a|\geq 2$,
$...

**-1**

votes

**1**answer

264 views

### Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun.
Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$.
Is it true that, for every $n \ge 8$, there is at least one even permutation $\...

**-2**

votes

**1**answer

82 views

### Hadwiger partitions where one block is always a singleton

Let $G=(V,E)$ be a simple, undirected graph.
We call a partition ${\cal P}$ of a non-empty subset of $V$ a Hadwiger partition if
every block (member of ${\cal P}$) is non-empty and connected, and
if ...

**-2**

votes

**1**answer

79 views

### Identifying two non-adjacent vertices and the effect on the Hadwiger number [closed]

Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
What is an example of a graph $G_0=(V_0, ...

**-4**

votes

**1**answer

70 views

### Regular graph such that $2$ distinct vertices have same neighborhood set [closed]

If $G=(V,E)$ is a simple, undirected graph and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$.
Is there an integer $k>1$ and a connected $k$-regular graph $G=(V,E)$ such that there are $v\neq ...