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

796 questions
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 ...
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. ...
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 ...
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 ...
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.,...
399 views

315 views

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 ...
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, ...
181 views

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 ...
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-...
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$, ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
117 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 ...