All Questions
Tagged with co.combinatorics reference-request
334 questions with no upvoted or accepted answers
1
vote
0
answers
91
views
Large deviation inequalities for number of coupon types collected by a coupon collector with fixed budget
In the generalized Coupon Collector's Problem, there are $N$ types of coupon, and for any $i \in [N] := \{1,2,\ldots,N\}$, $p_i \ge 0$ is the probability of obtaining a type-i coupon on any trial. ...
- 6,853
1
vote
0
answers
158
views
Hankel transform of certain $\pm1$ sequences
The present discussion finds its motivation in the comments by Ira Gessel to my earlier MO question. More specifically,
$$\prod_{i\geq0}(1-x^{2^i})=\sum_{k\geq0}(-1)^{s_2(k)}x^k$$
where $s_2(k)$ is ...
- 43.2k
1
vote
0
answers
100
views
Super Catalan (super ballot) numbers
We refer to this article by Ira Gessel. In section 6, page 10, equation (28), the Super Catalan numbers are defined as
$$S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}.$$
On page 12, equation (31), there goes ...
- 43.2k
1
vote
0
answers
103
views
How many convex polygons can be made from $n$ identical right angle triangles?
Whilst working on a Tangram problem, I came across the need to find the total number of convex shapes that can be produced from $16$ identical (isosceles) right angle triangles (since the Tangram can ...
- 147
1
vote
0
answers
74
views
Keller's cubing conjecture but with arbitrary cubes of side $1$
These days I have been reading about Keller's cube tyling conjecture, which asks if in any covering of $\mathbb{R}^n$ by translates of $[0,1]^n$ with disjoint interiors there are two cubes sharing one ...
- 10.6k
1
vote
0
answers
91
views
Asymptotic densities of rules of elementary cellular automata
In Tables of cellular automata, p.542, Wolfram defines the density $\delta$ of a rule to be the asymptotic density of nonzero sites when the initial configuration has density $1/2$. Wolfram quotes ...
- 9,720
1
vote
0
answers
87
views
Doubly log-concave or doubly log-convex
Suppose $(a_k)_{k\geq0}$ is a sequence of real numbers. Consider the operator $\mathcal{L}a_k=a_k^2-a_{k-1}a_{k+1}$.
We say $(a_k)_k$ is log-concave (resp. log-convex) provided $\mathcal{L}a_k\geq0$ (...
- 43.2k
1
vote
0
answers
105
views
Does this inequality follow from doubly log-concave?
On a sequence $(a_k)_{k\geq0}$ of positive integers, define the operator $\mathcal{L}a_k=a_k^2-a_{k-1}a_{k+1}$. Then, $(a_k)_k$ is called log-concave if $\mathcal{L}a_k\geq0$ for all $k\geq0$.
One may ...
- 43.2k
1
vote
0
answers
154
views
Volume of a polytope as its degenerates to be lower dimensional
Consider a polytope $P$ defined by the usual inequalities $A\mathbf{x}\leq \mathbf{b}$; let me assume that $P$ is not contained in a proper subspace. A result which I believe to true, but am not ...
- 44.7k
1
vote
0
answers
129
views
$\mathfrak{sl}_2$-action on Young diagrams
Let $\mathcal{Y}$ be a vector $\mathbb{Q}$-space of all Young diagrams. Denote by $\delta_\lambda$ the Young diagram of the partition $\lambda$ and $c(\square)$ be
the content of the square $\...
- 656
1
vote
0
answers
79
views
Partitioning of a set family that avoids small intersections
Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
- 135
1
vote
0
answers
381
views
Counting number of spanning trees of the complete bipartite with given vertex-degrees
For given $n_1,n_2 \in \mathbb{N}$ let $K_{n_1,n_2}$ be the complete bipartite graph. I have seen a few sources proving that the number of spanning trees $t(K_{n_1,n_2})$ is given by $n_1^{n_2-1} n_2^{...
- 1,295
1
vote
0
answers
72
views
Factorizable partition polynomials
Let $p(n)$ denote the number of (unrestricted) integer partition of $n$ which has the product generating function
$$\sum_{n\geq0}p(n)\,x^n=\prod_{j\geq1}\frac1{1-x^j}.$$
On the other hand, for the ...
- 43.2k
1
vote
0
answers
159
views
A follow up on Bergeron's conjecture and a question
We say two polynomials satisfy $P(x)\geq Q(x)$ iff $P(x)-Q(x)$ has non-negative coefficients. Recall $(n)_q!=\prod_{j=1}^n(1-q^j)$ and the Gaussian polynomials $\binom{n}k_q=\frac{(n)_q!}{(k)_q!(n-k)...
- 43.2k
1
vote
0
answers
203
views
Generalizing "partition into odd parts=partition into distinct parts"?
The number of partitions into distinct parts is known to agree with the number of partitions with odd parts. For instance, this follows from
$$\prod_{k=1}^{\infty}(1+q^k)=\prod_{n=1}^{\infty}\frac1{1-...
- 43.2k
1
vote
0
answers
94
views
Automated, algorithmic construction of bijective proofs of combinatorial identities
Let $a_n$ and $b_n$ be two different expressions in natural $n$ with values in the set of all nonnegative integers such that we have the identity $a_n=b_n$ for all $n$. As a simplest example, we may ...
- 128k
1
vote
0
answers
61
views
Rook polynomials with several sets of rooks?
Is there some article or other reference where the notion of
several sets of rook placements on Ferrers boards is considered?
That is, one might have, say black rooks and white rooks, and each set ...
- 15.8k
1
vote
0
answers
69
views
LGV scheme: Any situations where the weights shift differently for each path?
In Cylindric partitions, Proposition 1, Gessel and Krattenthaler prove a formula for lattice paths on a cylinder
In our particular problem, we again have paths $((P_{1},k_{1}),...,(P_{r},k_{r}))$ but ...
- 5,474
1
vote
0
answers
152
views
Is this graph theory paper in German translated into English?
I recently read such a paper and want to understand the proof idea of this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
- 1,851
1
vote
0
answers
90
views
Dimension of a certain space of symmetric functions: Part II
This is the second installment of my earlier MO question.
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. Denote the set of all partitions with distinct parts by $\...
- 43.2k
1
vote
0
answers
43
views
Correspondence between monomer-dimer heaps and words in 2 alphabets
For background and some illustrative pictures, refer to this preprint by A M Grasia and G Ganzberger: Fibonacci polynomials. For the present purpose, it suffices to read into pages 4 and 5.
The part ...
- 43.2k
1
vote
0
answers
35
views
Term or reference for a set of integer edge weights to guarantee distinct weighted degrees
I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...
- 11
1
vote
0
answers
118
views
Rowmotion for general lattices
Let $L$ be a finite lattice and $x \in L$ with covers $r_1,...,r_l$ in $L$.
One can define $row(x):= \min \{ y | y \leq r_1 \lor \cdots \lor r_l $ and $ y \nleq r_1 \lor \cdots \lor \overline{r_t} \...
- 26.5k
1
vote
0
answers
134
views
Counting unions of unlabelled connected graphs
My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...
- 183
1
vote
0
answers
97
views
bijection mapping a transversal to a transversal
The following must certainly be a standard result, so what I'm looking for is a reference, or the name of this theorem. I don't have any combinatorics books at my fingertips, but I could see this ...
- 11
1
vote
0
answers
121
views
Cheeger constant of truncated hypercube
Look at the $d$-dimensional hypercube and truncate it. This means one replaces each vertex by a cycle (of length $d$) in such a way the the new graph is 3-regular.
Question 1: What is the asymptotic ...
- 4,432
1
vote
0
answers
107
views
A maximization problem with permutations
Consider a partition $f:S_n\rightarrow [n]$ of $S_n$ into $n$ parts. Denote the permutations that map $j$ to $k$ by $s(j,k)$. Set $S(f):=\Sigma_{1\leq i,j\leq n}max_{1\leq k\leq n}|f^{-1}(i)\cap s(j,k)...
- 422
1
vote
0
answers
90
views
Is there any name/occurence to this sequence of numbers?
I am curious if there is any name for this sequence of numbers, or any occasion that this sequence is used.
The sequence is $(c_1,c_2,c_3,\cdots)$ with recursive formula
$$c_n=\frac{1}{2n+1}\sum_{i=...
- 323
1
vote
0
answers
174
views
Matroids with no relaxations (~ weak maps)
There's an operation in matroid theory which is called "relaxation".
To keep things simple, let's consider a matroid $M$ with set of bases $\mathcal{B}$. If $M$ has a subset $H$ of $M$ that is both ...
- 1,889
1
vote
0
answers
80
views
Packing almost-subgroups into a group
We consider a group finite $G$. We say a set $A\subset G$ injects a set $B$ if $|A+B| = |A||B|$, and let $I(B) = \max \{|A| :A\text{ injects } B\}$.
For a subgroup $H$, it is well-known that $I(H) = |...
- 3,499
1
vote
0
answers
49
views
Realizing 0/1-polytopes with shortest possible edge lengths
Has there been something written about the following question?
Question: Given a 0/1-polytope, what is the shortest edge lengths with which this polytope can be realized as a 0/1-polytope.
The ...
- 13.6k
1
vote
0
answers
93
views
Has this result about the number of permutations of a given cycle type (or centralizers) been proved?
I was playing with the cardinality of conjugacy classes of the symmetric groups, which we know is the number of permutations of a given cycle type and there is a natural one-to-one correspondence ...
- 151
1
vote
0
answers
81
views
Matchings in infinite, not necessarily bipartite, graphs
Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs.
Is there a similar generalization of Tutte's theorem on ...
- 48.9k
1
vote
0
answers
50
views
Approximately partitioning large $t$-wise intersections with few sets
Fix a family of $m$ sets $A_1,\dots,A_m\subseteq \{0,1\}^n$. For some integer parameter $t$, consider the class $\mathcal{S}$ of sets of the form $S(i_1,\dots,i_t):=\bigcap_{j=1}^{t}A_{i_j}$, for ...
- 43
1
vote
0
answers
29
views
Reference request for blocking sets in graphs
Let $G = (V,E)$ be a DAG and $S$ be a subset of $V$. I will call $S$ $k$-blocking if on every path of length $k~$ there is at least one node from $S$.
This parameter sounds reasonable enough, so I ...
- 673
1
vote
0
answers
151
views
Asymptotic estimation of numbers of unlabeled graphs whose degrees of vertices are bounded
It is known(Enumeration of graphs with a given and bounded degree sequence) that there is no a closed form formula for number of (labeled) graphs with bound on degree of vertices. Thus what I want to ...
- 8,071
1
vote
0
answers
116
views
Does this expression involving the order complex of a poset ring a bell?
Let $\mathcal{L}$ be a meet-semilattice, and denote by $\Delta(\mathcal{L})$ the poset of chains in $\mathcal{L}\setminus\{\hat 0\}$, where $\hat 0$ is the minimum element of $\mathcal{L}$.
Let $\...
- 2,788
1
vote
0
answers
54
views
Constructing graphs from subsets of a minimal alphabet
From an alphabet of $N$ letters, choose $n$ pairwise distinct subsets $ v_1,\dots,v_n$ of a fixed size $k$ and define a graph on $V=\{v_1,\dots,v_n\}$, which has an edge for each pair of vertices that ...
- 13.4k
1
vote
1
answer
298
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
- 11
1
vote
0
answers
52
views
Invariants of Permutations with Predicate and Equivalency Relation
Has the following kind of problem been investigated previously and, where can I find information about it:
Given
the set $\mathbb{P}_{n_0}$ of all permutations of $n_0$ elements
a predicate $P: p\...
- 13.2k
1
vote
0
answers
39
views
Colorful Neighborhoods
Given:
$G:=\{V= \{v_1,\ ...\ v_n\},E\subset V\times V\}, n<\infty$, a symmetric complete, simple graph
$w:=\ \ E \ni e_{ij}\mapsto \mathbb{R}^+$, a weight function for the edges of $G$
$K:=\{c_1,\ ....
- 13.2k
1
vote
0
answers
21
views
Properties of Optimal k-Tour Spanners
Let the edge set of a Optimal k-Tour Spanner of a graph $G$ be equal to the edges of $G$ that lie on at least one optimal tour through exactly $3<k<n$ distinct vertices of $G$.
I would like ...
- 13.2k
1
vote
0
answers
178
views
Estimates for derivatives of a positive discrete harmonic function
There is the following estimation (Duffin, Discrete potential theory, Theorem 5):
Let $f$ be a discrete harmonic function in a sphere of radius $R$ with the center $p$, all in $\mathbb Z^3$. Then, if ...
- 5,053
1
vote
0
answers
61
views
Generalizing Concepts of Planar Euclidean Geometry to Symmetric TSP-Instances
To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view.
Examples are:
the diagonals of the convex hull of a set of points in the euclidean plane; ...
- 13.2k
1
vote
0
answers
83
views
Empty node in cactus construction
Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...
- 11
1
vote
0
answers
255
views
An extrasensory perception strategy :-)
I asked this question at MSE some months ago
but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
- 5,409
1
vote
0
answers
64
views
Complexity of in-dominating set
Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than $\frac{n-2}{4}$, in particular)? --
I'm mainly looking for a reference.
Thanks for any answer!
1
vote
0
answers
95
views
Generating series of free PROs
Let
\begin{equation}
G := \biguplus_{p \geq 0} \: \biguplus_{q \geq 0} G(p, q)
\end{equation}
be a bigraded set of generators and $\mathcal{F}(G)$ be the free PRO generated by $G$ (see [1] for a net ...
- 437
1
vote
0
answers
71
views
Integral Leray Number?
The Leray number of a finite simplicial complex $K$ relative to a field $\Bbbk$ is defined to be the least $d\geq 0$ such that $\widetilde H^n(C,\Bbbk)=0$ for all $n\geq d$ and all induced ...
- 38.6k
1
vote
0
answers
372
views
counting k-cliques not also (k+1) on random graphs
consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges.
looking for a formula that counts the number of these graphs that have a $k$-clique but not a $(k+...
- 529