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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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 ...
