All Questions
Tagged with co.combinatorics reference-request
1,072 questions
1
vote
0
answers
25
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
3
votes
0
answers
73
views
While expanding Jack polynomials in monomial basis
Denote $\mathbf{z}=(z_1,\dots,z_n)$. Let $P_{\kappa}(\mathbf{z};\alpha)$ be the symmetric Jack polynomials and suppose they are expanded in terms of the monomial symmetric basis $m_{\rho}(\mathbf{z})$ ...
- 43.2k
8
votes
1
answer
671
views
Infinite series and sum of two squares
Consider the following infinite sequence $a(n)$ generated by
$$\sum_{n\geq0} a(n)q^n
=\frac{\sum_{k\geq0}F(2k+1)q^{\binom{k+1}2}}{\sum_{k\geq0} q^{\binom{k+1}2}}$$
where the $F(2k+1)$ are the odd ...
- 43.2k
3
votes
1
answer
405
views
Moments of a random variable related to uniform distribution on sphere
Let $u$ be taken uniformly from the unit sphere $\mathbb S^{n-1}$ and $D$ be a diagonal matrix. I'd like to find a general formula for
$$
\mathbb E[(u^\top D u)^m]
$$
for $m=1,2,3, \dots$, in terms of ...
- 1,608
4
votes
1
answer
197
views
Solving a three-parameter recursive sequence
Consider the triple-indexed sequence of integers defined by
\begin{align} \label{coefficientsV} \nonumber
f(\alpha,\beta,\gamma)
&:=(2\alpha+8\beta+12\gamma-1)\cdot f(\alpha-1,\beta,\gamma)...
- 43.2k
0
votes
0
answers
138
views
State of the art on attempts to solve the elliptic curve discrete logarithm problem through transfering the problem to a weaker curve
Let an elliptic curve $E$, and 2 points on such curve $P$ and $O$ the methods I’m talking about consist in creating a weaker elliptic curve $F$ and mapping $P$ and $O$ to $F$ while successfully ...
- 87
0
votes
0
answers
52
views
Reference request for the determinant of a matrix constructed from Pascal's triangle
One can prove by induction that the matrix $M^{(n)}$ given by
$$ \begin{pmatrix}
1 & 1 & 1 & 1 & \dots & \binom{n}{0} \\
1 & 2 & 3 & 4 & \dots & \binom{n+1}{1} \...
- 5,546
1
vote
1
answer
76
views
Determinant formula for a certain parametrized M-matrix
Let $P_{ij}$ be variables, and let $A \in \mathbb{R}^{n\times n}$ be the matrix defined by
$$
A_{ij} = \begin{cases}
-P_{ij} & i \neq j,\\
P_{i1} + P_{i2} + \dots + P_{in} & i=j.
\end{cases}
$$...
- 20.2k
8
votes
0
answers
244
views
Strengthening of Frankl's union-closed sets conjecture: An algebraic approach
Let $\mathcal F$ be a union-closed family of subsets of $[n]=\{1,2,...n\}$ and $n$ real numbers $x_1,x_2,...,x_n\geq 1$.
Conjecture: There exists $k\in [n]$ such that:
$$\sum_{k\in A,A\in \mathcal F}\...
- 1,462
3
votes
0
answers
101
views
Tuple rearrangement: a combinatoric problem emerging from the Hurwitz action on Coxeter groups
I am working on Artin Groups, so called Dual Artin groups and the conjecture that they are isomorphic. Tuples of $n$ group elements can be acted on by the braid group $B_n$ in a particular way called ...
- 31
10
votes
0
answers
287
views
Coefficients of polynomials vs trigonometric product
Let's consider the family of sequences of coefficients in the expansion
$$\prod_{i=0}^{n-1}(1+x^{3^i}+x^{3^{i+1}})=\sum_{k\geq0}a_n(k)\, x^k.$$
Remark. Evidently, the RHS is a finite sum.
Here is a ...
- 43.2k
2
votes
1
answer
431
views
Shadows of partitions of lcm
$\DeclareMathOperator\lcm{lcm}$Fix an integer $n\geq1$. Denote the least common multiple $L_n=\lcm(1,2,\dots,n)$.
QUESTION. Is the following true? For each integer partition $\lambda=(\lambda_1,\...
- 43.2k
2
votes
1
answer
276
views
Estimating a sum over set partitions
Let $[n]:=\{1,\dots,n\}$. Fix a set partition $\rho$ of $[n]$, with an abuse of notation we shall use $\rho\vdash [n]$.
I would like to estimate the following alternating sum.
QUESTION. Is this true?
...
- 43.2k
2
votes
0
answers
30
views
An algorithm to decompose a directly indecomposable permutation group into a wreath product
I am considering the following two binary operations on permutation groups:
the direct product, and
the wreath product.
It turns out that there is an efficient algorithm to factor a given ...
- 5,822
4
votes
0
answers
91
views
Reference for fact about flags of vexillary permutations
Vexillary permutations are an important family of permutations in Schubert calculus. There are several definitions, for example that they avoid the pattern 2143.
Recall the Lehmer code of a ...
- 1,989
8
votes
4
answers
1k
views
Counting with trees
Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
- 43.2k
23
votes
4
answers
2k
views
Identity for an infinite product
Here is an experimental "result" exhibiting the difference of two (formal) infinite products that "almost factorizes".
QUESTION. Is this true?
$$\prod_{n\geq1}(1+x^{2n-1})^{24} - \...
- 43.2k
3
votes
0
answers
61
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of ...
- 13.6k
11
votes
1
answer
340
views
Number of odd-dimensional irreducible representations of $S_n$
In this paper the structure of odd-dimensional irreducible representations of the symmetric group is described, but what is the asymptotic behaviour of the number of such representations? (Or, if it ...
- 109k
2
votes
1
answer
215
views
Number of binary matroids of rank $r$ on a ground set with $n$ elements
How many simple binary matroids are there, up to isomorphism, of rank $r$ on an $n$-element ground set, where $r \le n < 2^r$? Write this number as $a_r(n)$. Is there somewhere where I can get this ...
- 331
7
votes
1
answer
440
views
Road map and references for combinatorial Hodge theory
I'm a PhD student. I'm familiar with graduate level algebraic geometry and toric varieties.
I wanted to know a road map for getting into combinatorial Hodge theory and other prerequisites that I'll ...
- 839
4
votes
1
answer
170
views
About $CW(512,16^2)$
Definitions: A weighing matrix $W = W(n,k)$ with weight $k$ is a square matrix of order $n$ and entries $w_{ij}$ in $\{0, \pm 1\}$ such that $WW^T=kI$,
where $I$ is the identity matrix. A circulant ...
- 696
2
votes
1
answer
217
views
Number of distinct higher dimensional integer partitions
By a distinct partition, I mean a partition into distinct parts, i.e., $10 = 5+4+1$ is one, but $10=6+2+2$ is not. The number of distinct partitions of $k$ all whose parts are at most $n$ is given by ...
- 281
12
votes
1
answer
238
views
Number of planes generated by integer vectors
For fixed dimension $d$ and large $R$ consider all non-zero integer vectors in the ball $B(0,R)\subset \mathbb{R} ^d$ of radius $R$ centered at the origin. The number of such vectors grows as $c_d\...
- 109k
7
votes
1
answer
224
views
Generating set of permutation group such that generators do not "contain" other group elements
Let $(G, X)$ be a permutation group with domain $X$. Let $O=\{o_1,\dots,o_m\}$ be the set of orbits of $G$. I am interested in generating sets $S$ with the following property:
Let $g\in S$ be a ...
- 5,822
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 ...
3
votes
1
answer
162
views
Counting equal covering sets
Definition. We call a set $C$ of sets to be an equal covering set of $S$ if the elements of $C$ are all the same size and each element of $S$ is contained an equal number of times throughout the sets ...
- 33
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
15
votes
3
answers
1k
views
Does anyone remember what happened to the experimental search for polynomial identities for $\pi$?
So a while back I was on the internet and had encountered a website containing an experimental search for identities for $\pi$. My memory was that the page belonged to either Jonathan Sondow or ...
- 2,689
7
votes
1
answer
295
views
Is this known? As $p,q\to\infty$, most elements of the power set of $\{1,\dots,p\}\times\{1,\dots,q\}$ are in free $\Sigma_p\times\Sigma_q$-orbits
Let $p,q$ be nonnegative integers. The product of symmetric groups $\Sigma_p\times\Sigma_q$ acts on the power set $P(\{1, \dots ,p\}\times\{1, \dots ,q\})$ in the evident way. You can ask what ...
- 1,335
2
votes
0
answers
54
views
Transform connecting powers of integration and differentiation operators
Just by a chance, I found the following power series identity, which holds for any analytic function $F(\cdot)$, nonnegative integer $m$, and constants $u,v$ not depending on indeterminates $z,t$:
$$\...
- 34.3k
6
votes
1
answer
244
views
Linear independence over field of rational functions
To prove that functions $f_1(x), \dots, f_n(x)$ with $x \in \mathbb R$ are linearly independent, we only need to show that the Wronskian of these functions is non-zero at a certain value of $x$. Now ...
- 1,608
3
votes
1
answer
90
views
Asymptotic growth rate for primitve S-adic systems
It is known that for a primitive substitution $S:\mathcal{A}\to \mathcal{A}^+$, there exists constants $c,C>0$ such that
$$ c\theta_S^n \leq \vert S^n(a)\vert \leq C \theta_S^n \quad \text{for all} ...
- 633
3
votes
1
answer
140
views
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
- 129
3
votes
1
answer
343
views
Reference request: about “SNF” (Smith Normal Form)
I've read about some studies on the Paley I Construction. Among them I found the following notations ( See this page: https://documents.uow.edu.au/~jennie/matrices/32P02.html ).
$$SNF:1,2^a,4^{b},8^{b}...
- 41
3
votes
0
answers
125
views
Short path problem on Cayley graphs as language translation task (from "Permutlandski" to "Cayleylandski"(s) :). Reference/suggestion request
Context: Algorithms to find short paths on Cayley graphs of (finite) groups are of some interest - see below.
There can be several approaches to that task. One of ideas coming to my mind - in some ...
- 24.9k
0
votes
0
answers
117
views
An interesting identity involving skew-Schur functions
Denote $\rho=(-\frac12,-\frac32,-\frac52,\dots)$. I was reading this interesting paper, where in particular, the authors claim that one can get the expression in (2.9)
\begin{align*}
\prod_{k\geq1}(1+...
- 43.2k
0
votes
0
answers
57
views
Reference for packing property and König property
Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?
- 21
4
votes
0
answers
90
views
Symmetric functions and pattern avoidance
It is known that the number of $k$-regular simple graphs with vertices labeled by $1,2,\dots,n$ can be expressed as the coefficient of $x_1^k \dots x_n^k$ in a symmetric function, which is
$$
\prod_{1\...
- 1,608
4
votes
1
answer
261
views
What is the convergence rate of this "infinite monkey"-type probability?
Cross-posted from Math Stack Exchange, where it hasn’t received an answer yet:
Let $S$ be a finite set and $n,m\in\mathbb N$. Consider the process $R=(R_i)_{i\in\mathbb N}$ where all $R_i$ are iid ...
- 141
4
votes
0
answers
82
views
Expansion of Schubert polynomials into standard elementary monomials
I have an explicit formula for expressing any Schubert polynomial in terms of standard elementary monomials that may or may not be cancelation-free. I haven't determined this yet, but it seems likely ...
- 2,168
2
votes
0
answers
278
views
On $(k,\ell)$-sumfree sets
Call a set $\mathcal S \subset \mathbb N$ to be $(k,\ell)$-sumfree if there are no non-trivial solutions to the equation
$$x_1+\dots +x_k = y_1+\dots +y_\ell$$
in the set (for distinct $x_i$'s and $...
- 791
0
votes
2
answers
96
views
Isometric path cover number of the 2 dimensional grid graph
I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
- 1,305
5
votes
0
answers
141
views
If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?
Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
- 15.8k
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\...
6
votes
0
answers
102
views
The meet of two dominant permutations in weak order of $S_n$
A permutation is called dominant if its Lehmer code is a partition, or equivalently if it avoids the pattern $132$.
I can prove that given a permutation $v\in S_n$, there is a unique dominant ...
- 2,168
4
votes
1
answer
222
views
Double cover the edges of a complete graph by smaller complete graphs
Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...
- 43
2
votes
2
answers
77
views
Reference request for a subfamily of regular graphs
[Repost of same question math stack exchange which got no answers]
I'm looking for literature on the following family of graphs:
Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there ...
- 21
1
vote
0
answers
148
views
Exploring the Intersection of Expander Graphs, Number Theory, Representation Theory and Recent Computer Science Developments [closed]
I have a solid understanding of the basics of expander graphs and their properties and the recent development of High-Dimensional Expanders and their application to Random Walks, along with other ...
5
votes
0
answers
107
views
Generalized Puiseux series for diagonal reflections of the curves $y = \frac{x}{(1-ax)(1-bx)^m}$
Reflection of the curve $y = f_m(x) = \frac{x}{(1-ax)(1-bx)^m}$ through the diagonal line $y=x$ in the $xy$-plane can be regarded as local compositional inversion of the curve $y=f_m(x)$. ($x,y,a,b$ ...
- 10.5k