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

7,304
questions

**0**

votes

**0**answers

18 views

### Permutations of successive “jumps” in linear extensions

Given a poset $P$ on an $n$ element set $X$ if $L=(X,\leq)$ is a linear extenstion of $P$ then we index $\{x_1,\ldots x_n\}=X$ such that $x_1\leq \ldots \leq x_n$ - now if $C=(x_{i+1},\ldots x_{i+k})$ ...

**0**

votes

**0**answers

24 views

### Why do we not have a closed form expression for counting transitivity?

https://en.wikipedia.org/wiki/Transitive_relation.
Are there any theoretical reasons out there which show us that why do we still not have a closed-form expression for transitivity counting. If you ...

**0**

votes

**0**answers

12 views

### Sequence estimate for slow variation to study the wandering rate of a set

Consider the two matrices
$$
M_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 &
1 \end{pmatrix} \quad \text{and} \quad M_{2}
= \begin{pmatrix} 0 & 0 &...

**0**

votes

**1**answer

61 views

### How to check if you have the asymptotic solution of some equation?

Suppose I have an analytic function $f : \mathbb{R} \to \mathbb{R}$ and I have the asymptotic expansion of some $x_0$ up to a few terms in terms of $\epsilon$ for some $\epsilon \to 0$ which I believe ...

**9**

votes

**1**answer

179 views

### Poset-troids …?

In many respects,
spanning tree : graph :: linear extension : poset
For instance, the number of spanning trees/linear extensions is a measure of the "richness" or "complexity" of the graph/poset. ...

**8**

votes

**1**answer

219 views

### Transfinite algorithms

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...

**1**

vote

**0**answers

43 views

### Configuration of the irregular pairs in Szemeredi's regularity lemma

Szemeredi's regularity lemma states
For every $ε > 0$ and positive integer $m$ there exists an integer $M$ such that if $G$ is a graph with at least $M$ vertices, there exists an integer $k$ in ...

**0**

votes

**0**answers

54 views

### Concentration results for the number of non-empty bins throwing $n$ balls into $n$ bins

We throw $n$ balls uniformly at random into $n$ bins. What is easiest way to calculate the probability that at least $an$ bins are not empty, where $a\in \left(0,\left(1-\frac{1}{e}\right)n\right)$? ...

**1**

vote

**1**answer

122 views

### Bike lock graph

Motivation. I have a bike lock with 4 dials, and I was wondering whether I can reach any combination by always turning a fixed number $k$, say $k=2$, of the dials, by $1$ position, instead of just ...

**1**

vote

**1**answer

224 views

### Does $g+A\subseteq A+A$ imply $g\in A$?

Suppose that $A$ is a subset of a (large) finite cyclic group such that $|A|=5$ and $|A+A|=12$. Given that $g$ is a group element with $g+A\subseteq A+A$, can one conclude that $g\in A$?

**1**

vote

**0**answers

19 views

### Standard terminology for these “coarsening” and “refining” operations for compositions and ordered set partitions?

Let $[M]:=\{1,2,\dots, M\}$. (Part of the twelvefold way) as we all know, there is a bijection between surjective functions $[N] \to [B]$ and ordered set partitions of $[N]$ into $[B]$ blocks (of ...

**2**

votes

**0**answers

75 views

### Bijection between monoid of nilpotent decreasing self-maps and local subsemigroup

Let $\mathcal{C}_X\cong\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $X=\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$) and decreasing ($...

**0**

votes

**0**answers

28 views

### Age of the most recent common ancestor for the neutral Wright-Fisher model

The neutral Wright-Fisher model with $n$ individuals is a genealogical model often used in population genetics that can be described as follows: at all generations, there are exactly $n$ individuals, ...

**0**

votes

**0**answers

41 views

### Graph coloring to minimize maximum number of colors along paths

Given a graph $G$ and a pair of source-destination nodes $s$ and $t$. Each node in $G$ is to be colored. Let $C_i$ denote the available color set for node $i$. Under a coloring scheme $A$, for any $s-...

**4**

votes

**0**answers

44 views

### Stability of infinite root systems with a long path in their Coxeter diagrams

Given a Cartan matrix associated to a Coxeter diagram, I can modify it by replacing one of the edges in the diagram with a long chain of vertices connected by simply laced edges; for example, this is ...

**0**

votes

**1**answer

63 views

### Finding k items in a binary tree

Let us be given a binary tree of height $n$ (and $2^n$ leaves) among which we search $k$ items, where $k < < 2^n$. Suppose we have a test that shows if in the children and childrens-children ...

**2**

votes

**2**answers

122 views

+50

### Transforming an optimization problem to maxmin formulation

Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions ...

**0**

votes

**0**answers

17 views

### Does the polytope of solutions to this modified vertex cover LP relaxation have half-integer vertices?

Given a graph $G$, one can consider the vertex cover LP relaxation
$x_v\in\mathbb{R}$, $v\in V(G)$
$x_v\geq 0$ $\forall v$
$x_v+x_w\geq 1$ for all edges $vw\in E(G)$,
where we want to minimize
$\...

**5**

votes

**2**answers

472 views

### Order of product of group elements

Let $G$ be a finite non-commutative group of order $N$, and let $x, y \in G$. Let $a$ and $b$ be the orders of $x$ and $y$, respectively. Can we say anything non-trivial about the order of $xy$ in ...

**1**

vote

**0**answers

65 views

### Combinatorial problem in non-collinear chains on tableau $n\times n$

There are $n\times n$ points. How many chains exist in its vertices, in which there is no three collinear points and each point used at most one time.
I have drawn examples below (red is ok but green ...

**1**

vote

**0**answers

151 views

### Let $n \ge 5$. Show that, among the $s_n$ space parts, there are at least $(2n − 3)/4$ tetrahedra (HMO 1973) [closed]

Engel's first problem
Engel's Second problem Proof (problems are from the Hungarian Mathematics Olympiad, 1973).
I'm having problems interpreting the last part of the proof on the second problem. I ...

**2**

votes

**1**answer

191 views

### Number of non-crossing sets of intervals

Consider the integers $[1,n]=\{1,\dots,n\}$ and call subsets of the type $[a,b]=\{a,\dots,b\}$ with $1\le a < b\le n$ intervals. We say that two intervals $[a,b],[c,d]$ are crossing if either $a<...

**0**

votes

**0**answers

24 views

### balls and boxes optimization

There are $n$ balls, among which $m$ balls are bad, and hence $n-m$ are good. We are given a number of boxes. We want to put balls into boxes such that all the good balls (or most of them, e.g., $99$%)...

**1**

vote

**0**answers

54 views

### A countable expression expressible in $\mathrm{FO}_3$ with only one binary predicate?

Transitivity on a set is defined as follows
$$\forall x \forall y\forall z( T(x,y) \land T(y,z) \rightarrow T(x,z))$$
Now if we wanted to count total number transitive relations which are defined on ...

**7**

votes

**1**answer

141 views

### Random walks on infinite directed regular graphs

Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps).
Assume that $\Gamma$ is bi-regular, that is ...

**1**

vote

**0**answers

77 views

### Number of components of self-index complementary graphs

Let $G$ be a simple graph. We say this graph is self-index complementary (SIC) if $\lambda_1 (G)=\lambda_1 (\overline{G})$, where $\lambda_1(G)$ denotes the index of the adjacency matrix of the graph $...

**3**

votes

**0**answers

48 views

### Uniquely describing a polytopal complex by prescribing the local structure around its vertices

Let $C$ be a $d$-dimensional (abstract) polytopal complex.
Most of what I say below could be asked in this general setting, but for a start, let's further restrict to simple polytopal spheres, that is,...

**7**

votes

**1**answer

193 views

### Equal products of consecutive integers

Summary: What are the non-trivial solutions to the question: Find two sequences of consecutive integers whose products are the same. There are four known solutions, all of thich consist of small ...

**-1**

votes

**1**answer

72 views

### Sum of $\sum_{1\leq k\leq k'\leq n}\frac{k^{\alpha}}{k'^{\alpha}}$ [closed]

I want to calculute or estimate of order $O(n^{2-\varepsilon})$, where $\varepsilon>0$, of the following sum for $0<\alpha<1$
$$\sum_{1\leq k\leq k'\leq n}\frac{k^{\alpha}}{k'^{\alpha}}.$$

**0**

votes

**0**answers

69 views

### Constructing set with maximal independent subset

What is the minimal $m$ such that there exists a set $A = \{a_1,...a_n\}$ of vectors : $a_i \in \{0,1\}^m$ ($n$ is given) such that every subset of vectors of size $k$ is independent, but only with ...

**3**

votes

**0**answers

52 views

### Logconcavity of height of Dyck paths

A finite sequence $a_i$ is called logconvace in case $a_i^2 \geq a_{i-1} a_{i+1}$.
Question : For a fixed $n$, is the sequence $a_{n,k}$ giving the number of Dyck paths of semilength $n$ having ...

**2**

votes

**1**answer

82 views

### Distinct distances between adjacent equal elements

Let's call a sequence $a_1, \ldots, a_n$ suitable if for any positive integer $d$ there is at most one index $i$ such that $a_i = a_{i + d}$ and all elements $a_{i + 1}, \ldots, a_{i + d - 1}$ are not ...

**3**

votes

**0**answers

47 views

### Properties of sequences associated to Nakayama algebras

Assume Nakayama algebras are connected and given by quiver and relations. Note that such Nakayama algebras have global dimension at most $2n-2$ in case it is finite and the algebra has $n$ simples.
...

**0**

votes

**0**answers

58 views

### Maximize sum of supermodular functions over nested sets

Let $R$ be a function that maps a set and a positive integer to a real positive number. We have that for any positive integer $t$ and $S \subseteq \{1, \ldots, t\}$, $R(S, t)$ satisfies:
For all $t &...

**2**

votes

**0**answers

53 views

### Best known bound on feedback arcset in high-girth directed graphs?

Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every directed cycle in $G$ has length at least $m/k$. An arcset of $G$ is defined as a set of edges $X$ whose removal from $G$ ...

**5**

votes

**1**answer

93 views

### How to prove the relationship between Stern's diatomic series and Lucas sequence $U_n(x,1)$ over the field GF(2)?

I found the bit count of Lucas sequence $U_n(x,1)$ over the field GF(2) is Stern's diatomic series, I want to know the reason?
https://oeis.org/A002487 : Stern's diatomic series
https://oeis.org/...

**2**

votes

**1**answer

136 views

### Increasing the “shuffling distance” by iterating a permutation $\varphi: \omega \to \omega$

Motivation. I was wondering about the following when playing a card-shuffling game with my elder son.
If $\varphi: \omega \to \omega$ is a bijection, we define the shuffling distance of $\varphi$ by $...

**1**

vote

**0**answers

62 views

### Terminology for transforming a directed acyclic graph into a tree

I am looking for the term of converting a directed acyclic graph (DAG) into a tree by traversing its topologically ordered nodes and copying the subtrees of the nodes with in-degree $> 1$.
Such a ...

**6**

votes

**1**answer

145 views

### Minimal generating set for $S_\omega$

If $G$ is a group and $S\subseteq G$, let $\langle S \rangle$ be the intersection of all subgroups of $G$ containing $S$.
Let $S_\omega$ denote the group of all bijections $f:\omega\to\omega$ with ...

**0**

votes

**0**answers

20 views

### Algorithm for sampling stratification-constrained permutations

Let $\mathcal{X}$ be some base space, and let $\mathbf{S} =S_1, \ldots, S_N$ be a cover (not a partition, i.e. they can overlap) of $\mathcal{X}$. I will refer to the $S_i$ as strata, and to the cover ...

**5**

votes

**1**answer

108 views

### Is the number of commutation classes of reduced words of the longest element of $S_n$ even for $n\geq 3$?

Observably, the number of primitive sorting networks on $n$ elements (or the number of commutation classes of reduced words of the longest element of $S_n$) is even for $3\leq n\leq 15$. These are all ...

**6**

votes

**0**answers

71 views

### Girth and diameter of a graph with minimum degree at least 3

The problem is motivated by generalizing Moore graphs, graphs with maximum possible girth ($2\text{diam}+1$) given the diameter.
Question. Does there exist a graph $G$ with $\text{g}(G)-\text{diam}(...

**6**

votes

**1**answer

78 views

### Minors of low rank skew-symmetric matrix

Let $A$ be an $n\times n$ skew-symmetric matrix of rank $r$.
Given subsets $X$ and $Y$ of row and column indices respectively, let $A_{X,Y}$ denote the submatrix of $A$ obtained by only keeping rows ...

**0**

votes

**1**answer

46 views

### Maximal families of equal length intervals consist of equilateral triangles

My question is a follow up to How to find n points on a plane so that as many pair of points as possible have the same distance? -- see the conjecture at the bottom of this post.
Let $\ n\ $ be a ...

**9**

votes

**1**answer

837 views

### How can we find n points on a plane so that as many pairs of points as possible have the same distance?

There are $n$ points on the plane, and we need to maximize the number of pairs of points which have the same Euclidean distance.

**1**

vote

**1**answer

90 views

### Generating all pentominoes by cutting and pasting

Is it possible to place the twelve pentominoes around a circle in such a way that if two of the pentominoes find themselves next to each other, it is because one of the two can be obtained from the ...

**0**

votes

**1**answer

85 views

### longest possible chain from a collection of ordered pairs/ co-ordinates [closed]

I have a bunch of ordered pairs x, y where 0 < x < y <= n (some given upper bound)
like S = [(1,2), (1,3), (1,4), (2,3), (3,4)]
I need to find the Length of the longest subset where all the ...

**1**

vote

**1**answer

76 views

### Maximum distance of the numbers of players around a table

Suppose that a team of $ n $ players (numbered from 1 to $ n $) sit around a circular table and there are their numbers on their T-shirts.
Let $ a_1,a_2,..., a_n $ be the sequence of numbers around ...

**2**

votes

**1**answer

88 views

### Minimum real number for subset sum difference

Given a positive integer $n$, what is the minimum positive real number $b(n)$ such that for any $a_1,\ldots,a_n\in[0,1]$, some two subset sums differ by at most $b(n)$?
This is similar to subset sum ...

**1**

vote

**1**answer

59 views

### Asymptotic for restricted compositions into k parts

For every set of natural numbers $A$ and for all positive integers $n$, $k$, let $c_k^A(n)$ be the number of compositions of $n$ into $k$ parts from $A$, that is, the number of $(a_1, \dots, a_k) \in ...