All Questions
Tagged with co.combinatorics reference-request
335 questions with no upvoted or accepted answers
2
votes
0
answers
64
views
A particular generalization of free partially commutative monoids
A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
- 21
2
votes
0
answers
80
views
Inequality on polynomials
Recall $[n]_q=\frac{1-q^n}{1-q}, [n]!_q=[1]_q[2]_q\cdots[n]_q$ and the Gaussian polynomial $\binom{a}{b}_q=\frac{[a]!_q}{[b]!_q[a-b]!_q}$ with $[0]!_q:=1$.
Given two polynomials $U(q)=\sum_k\alpha_kq^...
- 43.2k
2
votes
0
answers
74
views
Formulas for special elements of the nil-Hecke ring
Kostant and Kumar introduced the nil-Hecke ring for a crystallographic Coxeter group, which we will take to be $S_\infty$, which is the ring generated as a left module over the polynomial ring $\...
- 2,168
2
votes
0
answers
165
views
Has Mac Lane's article "When can a graph be mapped on a torus?" been published anywhere?
I came across the following abstract of an article: Mac Lane, S., When can a graph be mapped on a torus?, Bull. Amer. Math. Soc. 42(9), 629 (1936). Abstract #341. MR1563375, JFM 62.0694.07.
Q. Does ...
- 1,446
2
votes
0
answers
117
views
A multi-variable "Fibonacci polynomial"?
There is a tremendous literature on the Fibonacci sequence, including its polynomial analogue $F_{-1}=0, F_0=1$ and
$$F_n(x)=xF_{n-1}(x)+F_{n-2} \qquad \text{for $n\geq1$}.$$
What I have found is the ...
- 43.2k
2
votes
0
answers
125
views
Almost subgroups of $\mathbb S^1$
Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1$ such that $|X+X|<(1+c )|X|$ for a sufficiently small $c\in(0,1)$. I believe that in such case there exists a subgroup $G=...
- 14.3k
2
votes
0
answers
92
views
A closure property of a set partition
Let $A$ be a finite set, $k\in\mathbb N$, $\tilde A\subset A^k$ and $\phi: \tilde A\to A$ be a map.
Consider the following property a set partition $P$ of $A$ might have:
$$
\forall B_1,\dotsc,B_k\in ...
- 5,822
2
votes
0
answers
87
views
Reference request on Plancherel measure for partitions whose parts differing by more than $1$
Given an (unrestricted) integer partition $\lambda$ of $n$, let $f_{\lambda}$ denote the number of standard Young tableaux (SYT) of shape the Young diagram $Y(\lambda)$ of $\lambda$. Then,
$$\sum_{\...
- 43.2k
2
votes
0
answers
413
views
A (really!) cute identity between product of binomials
As an off-shot of my earlier MO question, I have found a "really cute" identity. The connection is revealed in the limit $q\rightarrow 1$.
So, I would like to ask:
QUESTION. Is there a ...
- 43.2k
2
votes
0
answers
98
views
Two-variable generating functions over coprime pairs
I am studying a sequence $(\alpha_{p,q})$ indexed by a pair of coprime integers; this sequence arises naturally in the study of a particular set of spaces in geometric topology, but unfortunately the ...
2
votes
0
answers
161
views
Monotonicity of the cycle index polynomial under restriction
The cycle index (polynomial) of the symmetric group $\mathfrak{S}_n$ is given by the formula:
$$Z(\mathfrak{S}_n)(x_1,\dots,x_n)=\sum_{1j_1+2j_2+\cdots+nj_n=n}\prod_{k=1}^n\frac{x_k^{j_k}}{k^{j_k}j_k!}...
- 43.2k
2
votes
0
answers
59
views
Relations between LR coefficients and cores and quotients of partitions
I have a formula for certain coefficients in terms of Littlewood-Richardson coefficients and $p$-cores and $p$-quotients of partitions ($p$ is a prime). I would like to obtain some positivity ...
- 21
2
votes
0
answers
100
views
Sum of binary quadratic forms over inputs of equal Hamming weight
$\DeclareMathOperator{\field}{\mathbb{F}}$
Let $n$ be a positive integer, and let $q : \field_2^{n} \rightarrow \field_2$ be a quadratic form, specified in coordinates as
$$q(x)=\sum_{i =1}^n \alpha_i ...
- 980
2
votes
0
answers
157
views
On hypergeometric functions over finite fields
Let $\mathbb{F}_q$ be a finite field of $q$ elements. Let $A,B,C,\cdots$ denote the multiplicative characters over $\mathbb{F}_q$, and let $\overline{A}$ denote the inverse of $A$, i.e., $A(x)\...
- 93
2
votes
0
answers
301
views
Magic squares as sums of permutation matrices
A magic square of size $n$ and sum $k$ is a $n\times n$ matrix with non-negative integer elements, whose rows and columns all sum to $k$. A permutation matrix is a magic square of sum $1$. Every magic ...
- 2,552
2
votes
0
answers
85
views
Elements of the Hall basis described via permutations
Good morning,
Suppose that $\mathfrak{g}$ is a free graded Lie algebra generated by the elements $1,\dots, n$, i.e. assume that $\mathfrak{g}_1=\mathrm{span}\{1,\dots, n\}$. Let us focus on the Hall ...
- 277
2
votes
0
answers
84
views
symmetry for a pair of statistics on partitions
Let $\lambda\vdash n$ denote a partition $\lambda$ of $n$ and let $\square\in\lambda$ denote a box $\square$ in the Young diagram of $\lambda$.
QUESTION. Can you list a pair of (distinct) statistics $...
- 43.2k
2
votes
0
answers
147
views
Asking for a combinatorial proof of a binomial-sum
QUESTION. Is there a combinatorial proof of the below identity?
$$\sum_{k=0}^{n-1}\frac{2^{2k}}{2k+1}\frac{\binom{2n}n}{\binom{2k}k}=2^{2n}-\binom{2n}n.$$
REMARK. There are many other proofs (...
- 43.2k
2
votes
0
answers
130
views
Sources for describing the characteristic polynomial of a nonintegral hyperplane arrangement in terms of point counting?
I have a family of hyperplane arrangements, and I'd like to describe their characteristic polynomials. When the hyperplanes are defined over the integers, the easiest way for me to do this is to use ...
- 453
2
votes
0
answers
86
views
Optimal paths in set-weighted graphs
Let $G = (V,E)$ be an $n$-vertex graph, let $R$ be a finite set (to be specific, let us assume that $R = [n]$), and let $W : V \rightarrow 2^R$. Let us call the pair $(G, W)$ a set-weighted graph.
Now ...
- 655
2
votes
0
answers
495
views
Bijective proof of a combinatorial identity: $\sum\limits_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m$
Identity
\begin{equation}
\sum_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m \tag{1}
\end{equation}
was used in an answer here. As shown in that answer, (1) easily reduces to
\begin{...
- 128k
2
votes
0
answers
124
views
Graphs which are built from complete graphs : Reference request
Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$.
We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...
- 1,269
2
votes
0
answers
140
views
Lower bound for the chromatic number in terms of minimum feedback vertex set
Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$.
We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$
and this bound is sharp.
Is this known or trivial result?
This ...
- 25.4k
2
votes
0
answers
150
views
Projection of conormal bundle of Schubert variety under Springer resolution
Let $G=\mathrm{GL}_n(\mathbb{C})$ and $X_{\omega}=\overline{B_-wB/B}\subset G/B$ be a Schubert variety. Denote by $C(X_\omega)$ the conormal variety inside $T^*(G/B)$ ,
$\mu:T^*(G/B)\to \mathcal{N}$ ...
- 849
2
votes
0
answers
252
views
Understanding the geometry of $H_{n}=\{\vec{x} \in [-N,N]^n:\sum_{i=1}^n x_i = 0\}$
I am not an expert in convex geometry but if we define $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{R}$ and $S_n = \sum_{i=1}^n a_i$ I suspect that for arbitrary $N \in [1, \infty) $:
...
- 3,871
2
votes
0
answers
30
views
Graph vertex label dynamics, statistical model reference request
I am modeling some type of social interaction, and came up with the following natural question.
Let $K_n$ be the complete graph on $n$ vertices, with some initial edge labeling in some alphabet $A$.
...
- 15.8k
2
votes
0
answers
271
views
About relation between Kostka numbers and Littlewood-Richardson coefficient
The fact that Kostka numbers equals to Littlewood-Richardson coefficients for some partitions is already known $\colon$
\begin{align}
K_{\lambda \mu} = c_{\sigma \lambda}^\tau
\end{align}
where $\...
- 31
2
votes
0
answers
100
views
Publicly Accessible TSPLib95 Solutions
I have asked this question on MSE, but besides earning a TumbleWeed award, there was no feedback.
My question is, where I can download all optimal tours of the TSPLib95 library? I already did a lot ...
- 13.2k
2
votes
0
answers
50
views
An equation involving fractional covering number of hypergraphs
Let $\mathcal{H}=(S,\mathcal{X})$ be a hypergraph, where $S = \{ s_1, \ldots, s_n \}$, and $\mathcal{X} = \{ X_1, \ldots, X_m \}$.
The dual hypergraph $\mathcal{H}^*$ of $\mathcal{H}$ is the ...
- 655
2
votes
0
answers
91
views
Semigroups of nondecreasing functions
Consider some partially ordered set $(E,\leq)$. Assume either that it is countable with the discrete topology, or that it has some topology compatible with the order, preferably one that makes it into ...
2
votes
0
answers
85
views
An EKR type card deck of a childrens card game
You want to print a deck of cards of the following type: Each card shows $k$ items out of $n$ different items such that any two cards in the deck share exactly one item.
Question: What is the ...
- 3,271
2
votes
0
answers
276
views
Identity with Ramanujan's generalized continued fraction
Let $F(x,q)=\sum_{n\geq 0}x^n\dfrac{q^{n^2}}{(q)_n}$, where $(q)_n=(1-q)(1-q^2)\dots(1-q^n)$. Then:
$$H(x,q)=\frac{F(-xq,q)}{F(-x,q)}=\dfrac{1}{1-\dfrac{qx}{1-\dfrac{q^2x}{1-\dots}}}$$ is the ...
- 301
2
votes
0
answers
89
views
Rank-unimodality and Sperner property of higher dimensional partitions
I did a google-search but have not been able to find much reference on this problem. So I am asking it here hoping to get some information.
Consider the set of all 4-dimensional Ferrer's diagram ...
- 1,305
2
votes
0
answers
78
views
Maximum cardinality general factor of a graph
Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
2
votes
0
answers
265
views
How large can a set of nearly equidistant points be?
Suppose that $D$ is a set of points in $\mathbb{R}^{k}$ such that all pairwise distances between them belong to $[1,1+\epsilon]$.
It seems that such a set cannot be very large and that its ...
- 6,962
2
votes
0
answers
116
views
Isomorphic subcategories of directed graphs and presets
For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...
- 10.5k
2
votes
0
answers
70
views
Generalized separating systems
We call a set system $\mathcal{A}$ of subsets of the $n$ element universe $U$ a separating system if for any pair of elements $x,y \in U$ there is at least one set $A \in \mathcal{A}$ such that either ...
- 3,004
2
votes
0
answers
203
views
Schemes defined by a collection of Plücker coordinates
If $C \subset {[n]\choose k}$ is any collection of $k$-element sets, we can define a scheme $$ W(C) = \bigcap_{S\notin C} \{V \in Gr(k,n) : p_S(V)=0\} \qquad \subseteq Gr(k,n), $$ where $p_S$ is the ...
- 27.8k
2
votes
0
answers
153
views
(0,1)-matrices with certain properties
Fix $r,e >0$. Let $\mathfrak{B}$ be the set of $(r\times e)$-matrices with entries in $\lbrace 0,1\rbrace$. For $B \in \mathfrak{B}$ and $1 \leq s,t \leq r$, define
$\delta^B_+(t,s) = |\lbrace 1 \...
- 136
2
votes
0
answers
216
views
Polyhedral embeddings of large face-width where all faces have the same length
Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length?
By polyhedral embedding I mean an embedding of the graph on a ...
- 884
2
votes
0
answers
642
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of rectangular ...
2
votes
0
answers
95
views
A specific notion between the notions of transversal and system of distinct representatives.
Let $X$ be a set, let $\mathcal{C}$ be a collection of subsets of $X$, and let $x_1, \dots , x_k \in X$. Say that the sequence $\{x_i\}_{i=1\dots k}$ is a sequential transversal (of length $k$) ...
- 588
2
votes
0
answers
223
views
Explicit formulas for the action of the Hall algebra of the cyclic quiver on q-Fock space?
In their paper on the decomposition numbers of Schur algebra, Vasserot and Varagnolo introduce an action of the (twisted) Hall algebra of a cyclic quiver $\Gamma$ on q-Fock space.
Without q-shifts, ...
- 44.7k
1
vote
0
answers
23
views
Vertex coloring of the Rado graph
Is there a reference for the following fact about the Rado graph (the random countable graph) which came up in an answer to this question?
If the vertices of the Rado graph $G=(V,E)$ are colored with ...
- 13.4k
1
vote
0
answers
76
views
Shellable non-pseudomanifolds with dimension greater than 2
Shellability of simplicial balls and spheres (simplicial complexes whose geometric realizations are homeomorphic to balls and spheres) has been studied quite extensively. There are many explicit ...
1
vote
1
answer
232
views
Looking for q-analog of derangement anagrams for a word
I have already known QPermutationDerangement:
It describes the distribution
$$
d_n(q)=\sum_{\sigma \in D_n} q^{\operatorname{maj}(\sigma)}
$$
Where we sum over all derangements of an $n$ element set.
...
- 175
1
vote
0
answers
59
views
A question on generalized bases
I just came to know that it is possible to define a generalized base as an infinite sequence of natural numbers $\mathbf b=(b_1,b_2,\dots)$ where $b_i\ge 2$ for all $i$. With this definition, any $m\...
1
vote
0
answers
162
views
Triangular and pentagonal numbers in $q$-series
Consider the following two infinite series
$$\sum_{n\geq0}a(n)q^n=\prod_{k\geq1}\frac1{(1-q^k)^2(1-q^{5k})^2} \,\,\,\, \text{and} \,\,\,
\sum_{n\geq0}b(n)q^n=\prod_{k\geq1}\frac1{(1-q^k)^2(1-q^{7k})^2}...
- 43.2k
1
vote
0
answers
63
views
Factorization of the symmetric function identity $E(t)=1/H(t)$ with the refined Euler characteristic polynomials of associahedra / Lagrange inversion
I've come across two matrix identities, flagged with daggers below, relating the two sets of elementary and complete homogeneous symmetric polynomials/functions via the two sets of refined Lah and ...
- 10.5k
1
vote
1
answer
177
views
Spectral characterization of complete or complete bipartite graphs
The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:
Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
- 243