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.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
147