Unanswered Questions
3,130 questions with no upvoted or accepted answers
16
votes
0
answers
1k
views
Optimal monotone families for the discrete isoperimetric inequality
Background: the discrete isoperimetric inequality
Start with a set $X=\{1,2,...,n\}$ of $n$ elements and the family $2^X$ of all subsets of $X$.
For a real number $p$ between zero and one, we consider ...
- 62.3k
15
votes
0
answers
264
views
Lie theoretic meaning to $e^{\text{cycle}} = \text{permutation}$?
It is well known that exponentiating the EGF(exponential generating function) for cycles gives the EGF for permutations: link here. Usually summarized under the catchy slogan ...
- 1,201
15
votes
0
answers
246
views
Generalization of Newton's identities to Schur functions
In some recent work, I've stumbled across the following identity for $\lambda \vdash n$:
$$
n s_\lambda = \sum_{k=1}^n p_k \sum_{\mu \nearrow_k \lambda} (-1)^{\mathrm{ht}(\lambda/\mu)} s_\mu.
$$
Here, ...
- 1,909
15
votes
0
answers
732
views
Wherefore art thou a Borcherds Product?
This question essentially asks how can one recognize (or rule out) that a generating function of combinatorial origin may be given as a Borcherds type product. I'll start with a motivational example: ...
- 85.2k
15
votes
0
answers
387
views
References on Discrete field theory vs Discrete differential geometry vs Combinatorial topology
Let me ask several related questions on discretization of classical field theory:
In topological folklore, it is known that cochains are "discrete analogues" of differential forms, and coboundary ...
15
votes
0
answers
444
views
The rank of a "triangle-free" matrix
This is a version of the question I asked recently, but the assumptions got now strengthened substantially.
Suppose that $A=(a_{ij})_{1\le i,j\le n}$ is a square matrix with all elements in $\{0,\...
- 23k
15
votes
0
answers
468
views
Maximizing the number of semistandard Young tableaux
Is anything known about the following question? Given a positive
integer $p$ and a real number $0<\alpha<1$, what partition $\lambda$
whose parts sum to $\alpha p^2$ (asymptotically) and whose ...
- 23.1k
15
votes
0
answers
484
views
Word complexity of primes mod 4
For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
- 16.8k
15
votes
0
answers
582
views
On some special spanning trees of grid graphs
I would like to know if there are existing results on the following objects:
spanning trees of a grid graph, with no corridor
where a corridor is a vertex having exactly two neighbors, on opposite ...
- 6,149
15
votes
0
answers
443
views
Best known constant for parallel sorting
I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because ...
- 28.8k
15
votes
0
answers
2k
views
Covers of $Z^k$
This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ ...
CommunityBot
- 1
14
votes
0
answers
337
views
Poset defined on pairs of subgroups
Let $G$ be a group. Consider the set $P(G)$ of all pairs $(H,N)$ of subgroups of $G$ such that $N$ is a normal subgroup of $H$. Consider the relation $\leq_G$ on $P(G)$ defined as follows: $(H,N)\...
- 7,608
14
votes
0
answers
273
views
A conjectured rational generating function
In regard to my question here, let $G_n$
be a sequence of positive integers satisfying
$\lim_{n\to\infty}G_n=\infty$, such that the generating function
$\sum_{n\geq 1} G_nx^n$ is rational. Let
$$ P_n(...
- 49.9k
14
votes
0
answers
269
views
A symmetry of lattice paths
The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity.
...
- 2,866
14
votes
0
answers
1k
views
The threshold for a perfect matching in a random subgraph of a regular bipartite graph?
The following question seems very natural.
It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...
- 1,623