All Questions
Tagged with combinatorics or co.combinatorics
3,202 questions with no upvoted or accepted answers
17
votes
0
answers
917
views
Combinatorial identity involving the Coxeter numbers of root systems
The setup is:
$R$ = irreducible (reduced) root system;
$D$ = connected Dynkin diagram of $R$, with nodes numbered $1,2,...,r$;
$\hat D$ = extended Dynkin diagram, nodes numbered $0,1,2,...,r$;
$\...
- 2,449
16
votes
0
answers
557
views
Identity involving Schur polynomials, binomial coefficients and contents of partition
Let $C_{\lambda,\mu}$ be the coefficients defined as
$$ s_\lambda\left(\frac{x_1}{1-x_1},...,\frac{x_N}{1-x_N}\right)=\sum_{\mu\supset \lambda}C_{\lambda\mu}s_\mu(x_1,...,x_N),$$
where $s$ are the ...
- 2,552
16
votes
0
answers
255
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,989
16
votes
0
answers
363
views
Combinatorial characterization of intersecting intervals in the plane
Consider $n$ points $A=\{A_1,\dotsc,A_n\}$, and another set of points, $B=\{B_1,\dotsc,B_n\}$ in the plane. We can assume they are all disjoint.
For each permutation $\pi$, consider the collection of ...
- 15.8k
16
votes
0
answers
988
views
A Combinatorial Game: the Snake and the Hunter
The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
- 3,707
16
votes
0
answers
298
views
Realization spaces of 3-dimensional polytopes with fixed face areas
It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible.
A proof of this theorem can be found for instance in ...
- 31.2k
16
votes
0
answers
454
views
A Product Related to Unrestricted Partitions
Start with the product for unrestricted partitions:
$(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...$
Now replace some of the plus signs with minus signs and expand the product into a series. Is it ...
- 2,143
16
votes
0
answers
784
views
How to explain the picturesque patterns in François Brunault's matrix?
How to explain the patterns in the matrix defined in François Brunault's
answer to the question Freeness of a Z[x] module depicted below? --
Choosing colors according to the highest power of 2 which ...
- 19.6k
16
votes
0
answers
824
views
Capelli determinant = Duflo ( determinant) - was it known ?
Question briefly. Was this fact known: Capelli determinant = Duflo (determinant) ? (This is an equality of the two central elements in universal enveloping of Lie algebra $gl_n$).
I googled a lot ...
- 24.9k
16
votes
0
answers
558
views
Catalan objects associated to a univariate polynomial
Given a monic degree $n$ polynomial $f(z)$ with no double roots, and a phase $0\leq \theta < \pi$, there are natural constructions which associate to this data:
a noncrossing matching on $2n$ ...
- 6,282
16
votes
0
answers
910
views
Polynomials with presumably positive coefficients
After seeing that some positivity problems get their solutions on MO,
I am quite enthusiastic of posing my (and not only) problem of positive flavour.
In order to state it, I have to introduce the ...
- 13.5k
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 ...
- 24.7k
15
votes
0
answers
347
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)\...
- 1,462
15
votes
0
answers
271
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,221
15
votes
0
answers
767
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.6k
15
votes
0
answers
398
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
446
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
475
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 ...
- 50.8k
15
votes
0
answers
487
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 ...
- 17k
15
votes
0
answers
591
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 ...
- 3,587
15
votes
0
answers
448
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 ...
- 29k
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$ ...
15
votes
0
answers
899
views
Is every k-edge-connected graph also k-trail-ordered?
This is an old question of Aradhana Narula-Tam and Philip Lin that I think deserves wider circulation. It appeared in Discrete Math. 257 (2002), page 613, but not many people have looked at it and it ...
- 82.6k
14
votes
0
answers
276
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(...
- 50.8k
14
votes
0
answers
270
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,896
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,633
14
votes
0
answers
378
views
A hard Lefschetz theorem for nilCoxeter algebras
Let $W$ be a finite Coxeter group and $\mathcal{N}(W)$ its nilCoxeter
algebra (over the reals, say), as defined at
https://en.wikipedia.org/wiki/Nil-Coxeter_algebra. $\mathcal{N}(W)$ has
a natural ...
- 50.8k
14
votes
0
answers
618
views
Chasing a 1950s thesis from the University of Dhaka on block designs
On behalf of a friend I am searching for a thesis on block designs from the 1950s. The details are below.
Author: Qazi Motahar Husein (Sometimes Husain or Hussein).
Title of the Thesis: Symmetrical ...
- 6,162
14
votes
0
answers
254
views
Is combinatorial automorphism of symmetric convex polytope always antipodal?
The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
- 109k
14
votes
0
answers
629
views
Probability of many overlapping zero inner products on a circle
[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
- 3,377
14
votes
0
answers
262
views
Polytopes with few vertices and few facets
I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...
- 278
14
votes
0
answers
416
views
Monotone embedding of complete binary tree in hypercube
Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...
- 18.7k
14
votes
0
answers
857
views
A Conjecture About Directed Graphs that are the Union of Two Trees
Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed
spanning trees. Suppose that
There no subset X of vertices so that
there is precisely one directed edge
from X to its ...
- 24.7k
14
votes
0
answers
522
views
Reconstruction conjecture and partial 2-trees
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature,...
- 281
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
14
votes
0
answers
457
views
How much must deleting a spanning tree reduce edge-connectivity?
Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What ...
- 1,288
14
votes
1
answer
625
views
On certain order-automorphisms of the rationals
Consider the rationals $\mathbb{Q}$ with the usual order $\leq$. Now let $A$ be a subset of $\mathbb{Q}$, such that foreseen with the induced order $\leq$, $(A,\leq)$ is a dense linear order.
...
- 4,547
13
votes
1
answer
536
views
Some questions related to meanders
Let $A_n$ denote the set of noncrossing fixed point free involutions
in the symmetric group $S_{2n}$. "Noncrossing" means that if
$a<b<c<d$, then not both $(a,c)$ and $(b,d)$ can be ...
- 50.8k
13
votes
0
answers
188
views
Why is $ULU=NU$ (a refinement of $|N|=q^{n^2-n}$)?
Let $G=GL_n(\mathbb{F}_q)$, $U$, $L$, $N$ the subsets of upper-triangular unipotent, lower-triangular unipotent, all unipotent matrices respectively. Then $ULU=NU$ means that for any $g\in G$ the ...
- 3,772
13
votes
0
answers
221
views
A game based on the Euclidean algorithm
The following game is based on a somewhat "stupid" version of the Euclidean algorithm (where we allow only subtractions).
Positions are given by finite non-empty multisets (repeated elements ...
- 17.9k
13
votes
0
answers
257
views
Is the set of power matrices decidable?
Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a ...
- 48.8k
13
votes
0
answers
740
views
Is there a weak strong regularity lemma?
A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...
- 29k
13
votes
0
answers
2k
views
Identifying poisoned wines, with a twist
(This is a joint musing with Andrew Gordon and Wyatt Mackey)
There is a classic, elementary riddle, discussed before on MO and math.SE: suppose you have 1000 bottles of wine, and one is poisoned. The ...
- 303
13
votes
0
answers
1k
views
Pointwise (Hadamard) matrix product and the rank
$\DeclareMathOperator{\rk}{rk}$
Suppose that $A$ is a square matrix of order $n$. If, for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 2$, we have
$$ P(A)\circ Q(A^t) = P(1)Q(1)\, I_n \tag{$\...
- 23k
13
votes
0
answers
323
views
Reference request: exponential growth rates of subword-closed languages are integers
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters (...
- 2,339
13
votes
0
answers
349
views
Some $q-$analogues of $ \sum\limits_{j = - k}^k {{{( - 1)}^{ j}}}\binom{n}{k-j}\binom{n}{k+j}=\binom{n}{k}.$
Let ${\left( {a;q} \right)_n}=\prod\limits_{j = 0}^{n - 1} {(1-{q^j}a} )$ and
let $ {{n}\brack{k}}_q$ denote a $q-$binomial coefficient.
I am interested in $q-$analogues of the identity $ \sum\...
- 5,612
13
votes
0
answers
412
views
Transitivity of balanced mass transport in Z
Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...
- 19.7k
13
votes
0
answers
289
views
Why must commuting maps (of an interval) without common fixed points have at least 11 fixed points for the composition?
I've been looking at the examples of commuting functions on a closed interval which have no common fixed points. These were discovered in 1967 by William M Boyce and J Philip Huneke.
Earlier work by ...
- 553
13
votes
0
answers
293
views
Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once
I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length $...
- 261
13
votes
0
answers
189
views
Does a huge set of random points in the plane almost surely have a checkerboard-triangulation
A set of $n$ points in the plane in generic position (no alignement of three points) has at least $2.012^n$ different triangulations
of its convex hull involving only the set of given points.We call ...
- 17.9k