All Questions
Tagged with co.combinatorics reference-request
335 questions with no upvoted or accepted answers
3
votes
0
answers
62
views
Almost quadratic difference sets
Does there exist a characterization of sets $S$ such that $|S-S|$ is "almost quadratic" in $|S|$? For instance, what are some examples of sets such that $|S-S|$ is on the order of $\frac{{|S|}^2}{\log ...
- 31
3
votes
0
answers
346
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 ...
- 265
3
votes
0
answers
123
views
Tableaux switching
I'm reading the article Tableau Switching: Algorithms and Applications by Benkart, Sottile, and Stroomer. Do you know if there are any articles or books that talk more about the properties of tableau ...
- 320
3
votes
0
answers
92
views
Terminology for set systems: "trace" or "projection"?
Although the following question is not in itself mathematical, it is the expertise/breadth of the research community in mathematics that I wish to appeal to, beyond the filtered/trained search results ...
- 25.8k
3
votes
0
answers
127
views
$\left< 15\right>^7/15$-womcode construction
In the article Womcodes constructed with projective geometries Frans Merkx constructed several good wom-codes (write-once memory codes, see How to reuse a "write-once" memory by Rivest & Shamir ...
- 12.3k
3
votes
0
answers
87
views
References for Littelmann Path models and related combinatorial objects
I am looking for a reference (preferably textbook or lecture notes) having Littelmann path models and it's uses in representation theory, combinatorics. I am aware of the original papers by Littelmann....
- 427
3
votes
0
answers
134
views
Permutation of a sequence, such that $y_i+y_{i+1}$ are all distinct
The sequence $x_1, x_2, ..., x_n$ of positive integers contains at least $\frac {2n}{3}+1$ distinct numbers and each of them appears at most three times. How to prove that there is a permutation $y_1, ...
- 3,153
3
votes
0
answers
101
views
Hermitian sublattices of a given type
Consider an unramified quadratic extension $E/F$ of non-archimedean local fields, and suppose that $\langle\cdot,\cdot\rangle$ is a fixed Hermitian form on $E^d$ such that $\mathcal{O}_E^d$ is self-...
- 2,516
3
votes
0
answers
272
views
Reference request: Representing posets by integer divisibility
Does anyone know of an early published reference for the (very easy) fact that all finite posets can be represented as the poset of divisibility of a finite set of integers?
Page 1 of Birkhoff's ...
- 18.6k
3
votes
0
answers
37
views
Finding linear order of set maximising number of consecuitive subsets
I have the following combinatorial optimisation problem of which I think someone has probably solved it before. Has someone come across this problem before, maybe in a different setting than in the ...
- 31
3
votes
0
answers
102
views
The ring generated by a convex polytope and its faces
Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in $V$ with multiplication induced by Minkowski ...
- 3,079
3
votes
0
answers
62
views
How likely is a matrix with exactly $n$ number $1$s per row to avoid a large wide empty submatrix?
Consider the finite collection $M(N,n)$ of all $N \times N$ matrices with exactly $n$ entries per row equal to $1$ and all other entries equal to zero $0$.
By an $a \times b$ submatrix of $M$ we ...
- 1,955
3
votes
0
answers
239
views
T-equivariant homology of affine Grassmannian
Let $G=SL_n$, denote the affine Grassmannian $Gr:=Gr_{G}=\mathcal{G}/\mathcal{P}$, where $\mathcal{G}=G(\mathbb{C}((z)))$ and $\mathcal{P}=G(\mathbb{C}[[z]])$. We know that $R:=H_*^T(Gr)\cong H_*^T(\...
- 849
3
votes
0
answers
119
views
Multivariable Gaussian polynomials
Let the (homogeneous) Gaussian numbers be defined as $[n]_{x,y} = \frac{x^n-y^n}{x-y}$, and define Gaussian factorials as $[n]_{x,y}! = [n]_{x,y}[n-1]_{x,y}\dots [1]_{x,y}$, and the Gaussian binomials ...
- 2,242
3
votes
0
answers
122
views
Generalization of fisher inequality
What upper bounds are known on the size of a family $\mathcal{S}$ of subsets $S_i \subset [N]$ such that:
i) each $S_i$ is of size $pk$.
ii) for $i \neq j$, $|S_i \cap S_j| \bmod p \in U$, for some ...
- 131
3
votes
0
answers
100
views
Applications of finite Bolyai-Lobachevsky planes
Google scholar gives more than 200 articles comcerning finite Bolyai-Lobachevsky (BL) planes. Usually they devoted to construction of such objects (axioms may be different).
Are their any ...
- 12.3k
3
votes
0
answers
111
views
When does the constant term in the following expansion is nonzero?
Dyson's Theorem
The constant term in the expansion of
$$\prod_{1\leq i\neq j\leq n}\left(1-\frac{x_i}{x_j}\right)^{a_i}$$
is the multinomial coefficient
$$\frac{(a_1+\cdots+a_n)!}{a_1!\cdots a_n!},$$
...
- 1,997
3
votes
0
answers
86
views
$\mathbb Z$-torsion for some quadratically presented Lie rings
$\newcommand{\Z}{\mathbb{Z}}$
I asked this question on MSE but no answer so far, so I'm also asking it here.
Let $L$ be a Lie ring (a Lie algebra over $\Z$) with generators $x_1,\dots,x_n$ and ...
- 8,524
3
votes
0
answers
55
views
Efficiently drawing graph of maximum degree $3$ with at most $o(n^2)$ crossings
Let $G$ be simple finite graph of order $n$ and maximum
degree $3$.
Can we efficiently draw $G$ with at most $o(n^2)$ crossings?
"Efficiently" means in time polynomial in $n$ or at worst
$\exp{o(n^2)...
- 25.4k
3
votes
0
answers
303
views
Exchangeable or iid random variables and linear conditioning
Let $X_1,\ldots ,X_N$ be independent identically distributed random variables (or, more generally, exchangeable random variables,
but let's assume independence for simplicity). Then
$$
E(X_i\mid X_1+\...
- 1,765
3
votes
0
answers
219
views
First to note/document the relation between permutohedra and multiplicative inversion
The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...
- 10.5k
3
votes
0
answers
268
views
A generalization of Rogers-Ramanujan identity
The generalized Rogers-Ramanujan identity has the following form
$$\sum_{k_1\geq\cdots\geq k_r\geq 0}\frac{x^{k_1^2+\cdots +k_r^2+k_i+\cdots +k_r}}{(x)_{k_1-k_2}\cdots (x)_{k_{r-1}-k_r}(x)_{k_r}}=\...
- 1,305
3
votes
0
answers
133
views
Kruskal-Katona for multisets?
Following Fedor Petrov's remarks, here is a "set-theoretic version" of the
question I asked a while ago.
For integer $n\ge 1$, denote by $\mathcal M_n$ the family of all (finite)
multisets with the ...
- 23k
3
votes
0
answers
342
views
Finding many disjoint sub-trees with many leaves
Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
- 419
3
votes
0
answers
186
views
Which Dihedral Groups are $\text{CI}$-Groups?
Let $D_{n}$ denotes the dihedral group of order $2n$. Firstly, for self-referencing of the question, I give some definitions which are standard.
Let $G$ be a finite group. A subset $S$ of group $G$ ...
- 4,784
3
votes
0
answers
216
views
A "nice" Orthogonal Basis for Translation Invariant Symmetric Polynomials
It is going to be a rather long question, so I will first state it and then try to explain and motivate it.
Take $\Lambda_n $ as the graded ring of symmetric polynomials of a field $F$ in $n$ ...
- 613
3
votes
0
answers
130
views
Where does this identity involving sums of Hankel-like determinants over partitions come from?
For a partition $\lambda=( \lambda_1,\dots,\lambda_n)\vdash n$ with $\lambda_1\ge\dots\ge\lambda_n\ge0$ and any function $f:\mathbb Z\to\mathbb C$, define a Hankel-like $n\times n$ matrix $$M_f(\...
- 13.4k
3
votes
0
answers
391
views
Dissection of a polygon into convex polygons
Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...
- 935
3
votes
0
answers
124
views
Reference for MacMahon on Overpartitions
In the literature on overpartitions Percy A. MacMahon is usally cited as the genesis of the theory. Often the reference is to his 1916 textbook -- but, having recently checked this out of my school's ...
- 647
3
votes
0
answers
135
views
Citation for subset complement result
Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* $R(S)=\...
- 4,589
3
votes
0
answers
208
views
References for properties/examples of breadth in (semi)lattices
This is in some sense following up on my earlier question Is there existing terminology for this technical condition on semilattices? and the answer given by NN.
I am currently revising the paper ...
- 25.8k
3
votes
0
answers
195
views
Is there a name for this property in set-valued analysis?
Consider a set-valued, finite-valued map $F$ from a set $X$ to subsets of $X$. Consider the following property: $|F(x)| \geq |F(y)|$ for all $x,y$ such that $y \in F(x)$.
I have defined this property ...
- 61
3
votes
0
answers
156
views
Large Deviation Bounds for Number of Forests (or Tutte polynomial) in G(n,p)
Does anyone know of results/references related to large deviation bounds on the number of subforests (or the Tutte polynomial) in G(n,p) (Erdos-Renyi random graphs)?
- 53
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
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
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
2
votes
0
answers
352
views
On characters of the symmetric group: Part 1
Given an integer partition $\lambda$, denote $\ell(\lambda)=$ length, $\vert\lambda\vert=$ size and $\lambda=$ conjugate of $\lambda$. Allow to write $\lambda\vdash n$ either as $(\lambda_1,\dots,\...
- 43.2k
2
votes
0
answers
286
views
Is Sturm's theorem able to do these?
$\newcommand{\Ord}{\operatorname{Ord}}$Let $p$ be a positive integer and $F(q)=\sum A(m)q^m$ be a formal power series with integer coefficients. Then $\Ord_p(F(q))$ is defined by
$$\Ord_p(F(q)):=\min\{...
- 43.2k
2
votes
0
answers
73
views
An iterative formula for the Kreweras-Voiculescu polynomials (reference request)
Let
$$N(x) = 1 + \sum_{k \ge 1} N_k(h_1,h_2,...,h_k) \;x^k$$
$$ = 1 + h_1 x + (h_1^2 + h_2) x^2 + (h_1^3 + 3h_1h_2 + h_3)x^3 + (h_1^4 + 6 h_2 h_1^2 + 4 h_3 h_1 + 2 h_2^2 + h_4) x^4 + \cdots$$
be the ...
- 10.5k
2
votes
0
answers
79
views
Skewed plane partition with only row fillings reversed
The number of plane partitions in a bounded box is well-studied and dates back to MacMahon, at the start of this paper by Sam Hopkins and Tri Lai, p9, they summarized current results on the ...
- 51
2
votes
0
answers
172
views
Lattice paths avoiding holes
Consider lattice paths from $(0,0)$ to $(2n,2n)$ with steps $N=(0,1)$ and $E=(1,0)$ avoiding the points $(2i-1,2i-1)$ for all $1\leq i\leq n$. There are Catalan many $C_{2n}=\frac1{2n+1}\binom{4n}{2n}$...
- 43.2k
2
votes
0
answers
99
views
Combinatorics on non-associative words
In my P.h.d research, I deal (among other things) with non-associative words, which we call monomials, and we need to consider two types of operations with these monomials.
The first one is simply ...
2
votes
0
answers
228
views
Ramanujan's theta functions and hook lengths?
Given an integer partition $\lambda\vdash n$ of $n$, one may associate a Young diagram $Y(\lambda)$ to it followed by a computation of hook length $h_{\square}$ for each cell $\square=(i,j)$ in $Y(\...
- 43.2k
2
votes
1
answer
358
views
q-polynomials in terms of a basis
Consider the polynomials
$$f_n(q)=\prod_{j=1}^n(1+q^j) \qquad \text{and} \qquad g_m(q)=1+q+q^2+\cdots+q^m.$$
I'll list a few examples to motivate my question. Direct calculations show that
$$f_1=g_1, \...
- 43.2k
2
votes
0
answers
65
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
2
votes
0
answers
209
views
Literature on Lyndon words and the Lie commutator
Since I lost my paper notes in a domestic conflagration in Japan some ten years ago, I've occasionally tried to recall one particular author who wrote in the 1900s about Lyndon words / strings, or ...
- 10.5k
2
votes
0
answers
77
views
Flexagons and noncrossing partitions
Turns out a couple of series related to the faces of flexagons
popped up in my explorations of combinatorial reciprocities in a group algebra for sets of partition polynomial (ParPs) related to the ...
- 10.5k
2
votes
0
answers
110
views
Asking for a generating function for an arithmetic sequence
For fixed integer $n\geq1$, let $c_m(n)$ be the number of divisors $d$ of $m$ such that $n<d\leq 2n$. Here is an experimental generating function for which I ask:
QUESTION. Is this true?
$$\sum_{m\...
- 43.2k
2
votes
1
answer
220
views
Is the 3-sum of two graphic matroids a graphic matroid?
A regular matroid is a matroid which is representable over any field. It is a famous theorem of Seymour's that the any regular matroid is obtained by performing 1,2, and 3 sums on graphic, cographic ...
- 153