All Questions
Tagged with co.combinatorics reference-request
335 questions with no upvoted or accepted answers
4
votes
0
answers
176
views
Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?
This is not a concrete question, just some thoughts.
The Komlos Conjecture is as follows-
There exists an absolute constant $C>0$, such that the following holds:
For all $d$ and any set of vectors ...
- 150
4
votes
0
answers
205
views
Dimension of a certain space of symmetric functions: Part I
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. A partition $\lambda$ is called a $t$-core if none of its hook lengths are multiples of $t$.
QUESTION. Consider the ...
- 43.2k
4
votes
0
answers
130
views
"Baues poset" of shellings of simplicial polytope?
Let me start with some background I want to use as analogy.
Consider a (convex) polytope $P$ and its set of triangulations. Among all the triangulations, a well behaved subset are the regular ones: ...
- 24.2k
4
votes
0
answers
427
views
Rota's cross-cut theorem - special case?
A question on accurate attribution/description:
Lemma.- Let $Q$ be a collection of subsets of a finite set $V$, and let $S_0\subset Q$. Then $$\left|\mathop{\sum_{S_0\subset S\subset Q}}_{\bigcup S = ...
- 20.2k
4
votes
0
answers
68
views
Asymptotics of the number of minimal strongly connected digraphs
Is anything known about the number of minimal strongly connected digraphs on $n$ labeled nodes? (``Minimal’’ meaning that on the deletion of any arc, strong connectivity is lost.) Some values are ...
- 1,112
4
votes
0
answers
64
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 ...
- 453
4
votes
0
answers
123
views
Bijections of Littlewood-Richardson coefficients
Let $c^{\lambda}_{\mu\nu}$ be the Littlewood-Richardson coefficients, where $\lambda,\mu,\nu$ are partitions. We know that $c^{\lambda}_{\mu\nu}= c^{\lambda}_{\nu\mu}$. Up to now, what are the ...
- 320
4
votes
0
answers
228
views
How many arrangements of $n$ points with $k$ edge lengths exist in $d$ dimensions?
[Asking on behalf of a high school mathematics course, but responses written at any level are welcome!]
I was recently reading over a nice puzzle called the four points, two distances problem:
...
- 7,831
4
votes
0
answers
282
views
Reference for results about planar graphs
A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the ...
- 2,339
4
votes
0
answers
68
views
Lower and upper (combinatorial) discrepancy
(I will state my question in terms of combinatorial discrepancy, but the same could be also asked about measure-theoretic discrepancy as well.)
The combinatorial discrepancy of a family $\mathcal F$ ...
- 18.7k
4
votes
0
answers
98
views
Ref. request: Enumerating elements of Bruhat cells
Given a field $F$ and a natural number $n$, let $B$ be the group of lower triangular, invertible $n \times n$ matrices over $F$. Then
$$GL_n(F) = \biguplus_{\pi \in S_n} B \pi B,$$
where we embed the ...
- 809
4
votes
0
answers
174
views
Determine binary function $f(x)$ by partial observation of $x$
Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function
$f:...
- 1,551
4
votes
0
answers
188
views
Distributions over permutation groups $\mathcal{S}_n$
Partly inspired by recent developments in enumeration of pattern avoiding permutations, which is known to be connected with Brownian excursions [Hoffman&Rizzolo]. The exciting milestone is the ...
- 8,071
4
votes
0
answers
207
views
Have wiring diagrams been generalized to arbitrary digraphs?
A "combinatorial wiring diagram" is a way to define a permutation by a drawing of a particular planar digraph. For example, this wiring diagram corresponds to the permutation $(3412)$:
In Coxeter ...
- 1,389
4
votes
0
answers
136
views
An upper bound on diagonal k-colored Ramsey number
I need a reference on any upper bound on $R(n, n, \dots, n)$ with $k$ arguments.
For example, the standard recurrent bound gives something like $k^{kn}$, but I cannot find any written explicit bound.
- 41
4
votes
0
answers
76
views
Comparing parametrizations of unipotent radical
Let ${G}$ be a simple algebraic group over $\mathbb{C}$ with maximal torus $T$ and set of simple roots $\{\alpha_i\}_{i\in \Delta}$. We then have a Borel supgroup $B=TU$ with unipotent radical $U$. ...
- 2,516
4
votes
0
answers
213
views
Counting the polytopes of the translates of the resonance hyperplane arrangement inside the unit hypercube
Let $n$ be a positive natural number. For all $\emptyset \subset S \subseteq \{1, \ldots, n\}$ and $k \in \mathbb{Z}$, define the hyperplane $H(S,k)$ in $\mathbb{R}^n$ given by the equations
$$H(S,k):=...
- 283
4
votes
0
answers
123
views
A color interpolation lemma
I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof.
Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \...
- 2,479
4
votes
0
answers
55
views
Looking for a Collection of Examples and Counter Examples for Assumptions about the Properties of Planar Euclidean TSP Instances?
Where can I find example and counter examples to seemingly plausible assumption about the properties of optimal solutions of planar euclidean TSP instances?
The reason for asking is that the ...
- 13.2k
4
votes
0
answers
158
views
Reference for the notion of polyhedra "degenerations"
Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that:
a) $P(0)=P$;
b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ (...
- 3,513
4
votes
0
answers
546
views
The original proof of Szemerédi's Theorem
Nowadays there are plenty of different proofs of the celebrated Szemerédi's Theorem but for historical reasons I would like to read and understand the original proof. The proof is very tricky and, for ...
- 1,561
4
votes
0
answers
114
views
Kruskal-Katona for homocyclic groups?
I need a version of the Kruskal-Katona theorem (better still, of the Lovasz "approximate" version thereof) for the elementary abelian / homocyclic groups, in the following spirit:
What is the ...
- 23k
4
votes
0
answers
111
views
A relaxation of proper coloring
I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...
- 7,875
4
votes
0
answers
248
views
Permutations with all cycles odd
I have recently needed to compute the number of permutations in $S_n$ with all cycles odd, and while this is easy using Flajolet-Sedgewick theory (the exponential generating function seems to be $\...
- 96.4k
4
votes
0
answers
188
views
A non-matroidal notion of dependence on a set of ideals
Assume we are given a set of ideals $I_1, \dots, I_s$ in a commutative polynomial ring. Let's define a subset indexed by $A\subseteq [s] = \{ 1,2,\dots, s\}$ as dependent if there exists an $a\in A$ ...
- 1,961
4
votes
0
answers
189
views
Slices of Simplices that are Simplices, Reference?
I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...
- 41
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
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
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
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
3
votes
0
answers
117
views
Is the exact formula for the trace moments of an isotropic complex Wishart matrix known?
Let $\mathbb{X}_{p,n}$ be a $(p \times n)$ random matrix whose entries are iid complex standard normal random variables. The hermitian random matrix $\mathbb{S}_{p,n} = \frac{1}{n} \mathbb{X}_{p,n} \...
- 1,295
3
votes
0
answers
151
views
Extension of work by Novelli and Thibon on noncommutative symmetric functions and Lagrange inversion
(Edit May 12, 2023: I just put up a brief summary of some of my notes on the partition polynomials described below in my WordPress mini-arXiv at "As Above, So Below". It contains multinomial ...
- 10.5k
3
votes
0
answers
233
views
A bridge between the algebraic / differential geometry of $\frak{sl}_2(\mathbb{C})$ and the Sheffer-Appell calculus and combinatorics
In "Four examples of Beilinson-Bernstein localization", Anna Romanov introduces the basis
$m_k = \frac{(-1)^k}{k!} \partial^k \delta $
on p. 9, where $\partial$ is a partial derivative and $\...
- 10.5k
3
votes
0
answers
116
views
A theory of refined h- and f-polynomials for the permutahedra, associahedra, noncrossing partitions, and tropical Grassmannians (references)
Looking for references (insights) on a theory encompassing a notion of refined face polynomials and their associated refined h-polynomials that are generalizations of the relation between ordinary f-...
- 10.5k
3
votes
0
answers
115
views
Counting monomials modulo prime numbers
The present quest emanates from this study by R. Stanley, including his recent MO question. Define the product (polynomials after full expansion)
$$I_n(x)=\prod_{i=1}^n(1+x^{F_{i+1}})$$
based on the ...
- 43.2k
3
votes
0
answers
144
views
Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$
This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
- 269
3
votes
0
answers
185
views
"Circulant-Vandermonde" matrix: in search of a formula
An $n\times n$ circulant matrix $\mathbf{X}_n$ has the form
\begin{align}
\mathbf{X}_n= \begin{bmatrix}
x_1 & x_2 & \cdots & x_{n-1} & x_n \\
x_2 & x_3 & \cdots & x_n&...
- 43.2k
3
votes
0
answers
315
views
When does the Taylor coefficient of $e^{\sin x}$ vanish?
If $f(x)=\frac{a_1}{1!}x+\frac{a_2}{2!}x^2+\frac{a_3}{3!}x^3+\frac{a_4}{4!}x^4+\cdots$ is an exponential generating function for $\{a_k\}_{k\geq1}$ then
$$e^{f(x)}=1+\frac{a_1}{1!}x+\frac{a_1^2+a_2}{2!...
- 43.2k
3
votes
0
answers
93
views
"Skew-dimension" and discrete parallelepipeds
Let $(G,+)$ be an abelian group. Given a subset $B\subseteq G\setminus\{0\}$, define the "discrete span" of $B$, which I will denote $\langle B\rangle_d$, to be the set of all $\sum A$ for $...
3
votes
0
answers
207
views
On a variation of the Vandermonde matrix
The ubiquitous Vandermonde matrix, of entries $(x_i^{j-1})_{i,j}^{1,n}$, and its determinant
$$\prod_{i<j}^{1,n}(x_j-x_i)$$
have found many utilities in Combinatorics and Physics, among other ...
- 43.2k
3
votes
0
answers
66
views
Classification or bounds on "totally symmetric" arrangements of subspaces
Let $F$ be a field and let $W_1, \dots, W_k \subset F^n$ be a collection of $d$-dimensional subspaces of $F^n$ such that $W_i \cap W_j = \{0\}$ for all indices $i,j$. We say that such an arrangement ...
- 2,830
3
votes
0
answers
179
views
Polytope algebra and toric vareties
Let $\Pi$ denote the McMullen polytope algebra (over the field of rationals $\mathbb{Q}$) generated by convex polytopes with rational vertices in $\mathbb{R}^n$.
For a simple polytope $P$ let us ...
- 21.8k
3
votes
0
answers
123
views
$q$-series for the number of rectangles in a square lattice
Given a partition $\lambda\vdash n$ of $n$, look at its Young diagram $Y_{\lambda}$. Let $a(\lambda)$ be the number of squares (of all sizes) in $Y_{\lambda}$. For example, if $n=4$ then $a(4)=4, a(3,...
- 43.2k
3
votes
0
answers
54
views
Cliques in Incomplete block designs
I'm interested in inequalities that guarantee the presence of cliques in incomplete block designs. Here's the set-up:
I have an incidence structure $(V, B)$ which is an incomplete block design: $V$ is ...
- 11.2k
3
votes
0
answers
123
views
About finite posets without intervals of size 3
Let $P$ be a finite poset (partially ordered set).
I am wondering whether the following condition on $P$ has been studied somewhere:
(#) No interval $[a,b]$ in $P$ has $3$ elements.
Note that ...
- 3,587
3
votes
0
answers
203
views
A connection between the Bell numbers and Bell polynomial
Let $B(n,x) = \sum_{k=0}^n {n\brace k}x^k$ be the Bell polynomials and $B_n = B(n,1)$ be the Bell numbers.
I recently proved a nice relation between the two:
$$
B(n,x)^{1/n}/x \ge B_{n/x}^{x/n},
$$
...
3
votes
0
answers
95
views
When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?
This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...
- 183
3
votes
0
answers
81
views
Size of the kernel (minimal ideal) of a finite semigroup
Let $A$ be an irreducible nonnegative $N\times N$ integer matrix with constant row sum $D$. Let $A_1, \dots, A_D$ be nonnegative integer matrices, each with constant row sum $1$, such that $\sum_k A_k ...
- 695
3
votes
0
answers
195
views
Congruence for the polynomials $(t+1)^n$
An interesting polynomial congruence is given by
$$A_n(t^m)\equiv \left(\frac{1+t+\cdots+t^{m-1}}m\right)^{n+1}A_n(t) \qquad \mod (t-1)^{n+1}, \tag1$$
where $A_n(t)$ are the Eulerian polynomials with ...
- 43.2k
3
votes
0
answers
66
views
Parabolic invariants of coinvariant algebras for reflection groups
Let $W$ be a finite reflection group and $V$ its reflection representation (over $\mathbb{C}$). Let $S$ be the symmetric algebra on $V^*$, $I_W\subseteq S$ the ideal generated by the non-constant $W$-...
- 3,093