Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
12
votes
0answers
811 views
Sums of Partitions and Stirling's formula
Stirling's formula $$N! \sim \sqrt{2 \pi}\ N^{N+ \frac{1}{2}} e^{-N}$$ follows easily from Laplace's method in light of the famous integral representation $$N! = \int_0^{\infty} e^{-z} z^N dz.$$ ...
12
votes
0answers
421 views
Enumeration of Standard Young Tableau of bounded height
First for some notation
$$ l(\lambda) = \text{ number of parts in a partition } \lambda \vdash n$$
$$ f_{\lambda} = \text{number of standard Young tableau of shape } \lambda\vdash n$$
The number $f_{...
12
votes
0answers
644 views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
12
votes
0answers
492 views
A commutative monoid associated with a finite abelian group
Let $M$ be a finite abelian group, and denote by $e_m$, for $m \in M$, the canonical basis of $\mathbb{Z}^M$. For $m, n \in M$ define elements $v_{m,n} \in \mathbb{Z}^M/\langle e_0\rangle$ as
$$
v_{m,...
12
votes
0answers
325 views
Matroids with prescribed independent sets
Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
11
votes
0answers
148 views
Quantitatively characterizing the failure of the converse of Dirac's theorem
First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...
11
votes
0answers
275 views
Conjectural nonvanishing of some combinatorial sums (6j symbols)
From various considerations and with the help of J. Van der Jeugt, I was led to conjecture the following property of a class of Wigner 6j-symbols:
for any integers $k,m$ with $m\ge k\ge 2$,
$$
\left\{...
11
votes
0answers
320 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 ...
11
votes
0answers
302 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: ...
11
votes
0answers
146 views
Poset of nonvanishing minors of a matrix
This question was posed on MSE here three days ago, but hasn't gotten any answers or suggestions. I hope it's okay to ask it on MO, but if I should wait a little longer, please just let me know.
Say $...
11
votes
0answers
351 views
A congruence involving roots of unity
Let $f(x) \in \mathbb{Z}[x]$ and suppose $f(\omega^j) \in \mathbb{Z}$ for all $j= 1, \dots, n$ where $\omega = e^{2 \pi i/n}$ is a primitive $n^{\text{th}}$ root of unity.
Computational evidence ...
11
votes
0answers
199 views
Question on a reduction in Kirillov's paper on positivity of divided difference operators
As the title says, my question is on a specific argument in Kirillov - Skew divided difference operators and Schubert polynomials (journal, MSN) on positivity of divided difference operators. I recall ...
11
votes
0answers
206 views
Is there a term for this graph subset?
Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:
If $c:V(G)\rightarrow [k]$ is a vertex ...
11
votes
0answers
421 views
Wilf's conjecture: complementary Bell numbers
The complementary Bell numbers or Uppuluri-Carpenter numbers, denoted $\tilde{B}_n$, can be delivered by
$$G(x):=\sum_{n\geq0}\tilde{B}_n\frac{x^n}{n!}=e^{1-e^x}.$$
Definition. Fix an integer $m\geq0$....
11
votes
0answers
262 views
Connection between Gelfand-Tsetlin basis and SSYT basis in Schur module
Consider an $n$-dimensional complex vector space $V$ with a chosen basis $e_1,\ldots,e_n$. This basis defines a Cartan decompostion of $GL(V)\cong GL_n$ and for an (integral dominant) highest weight $\...
11
votes
0answers
178 views
Euclidean realizations of a configuration of $27$ points and $45$ lines
Let $GQ(2,4)$ denote the abstract configuration (=incidence structure) consisting of $27$ points and $45$ lines, with $3$ points on leach line and $5$ lines through each point, which can be described ...
11
votes
0answers
461 views
Converse of Frobenius
Enumerate the elements of a finite group $G$ as follows: $g_1,g_2,\dots,g_n$. Introduce $n$ variables indexed by the elements of $G$: $x_{g_1},\dots,x_{g_n}$.
Consider the matrix $X_G$ with entries $...
11
votes
0answers
512 views
Product of a Schubert polynomial and a double Schubert polynomial
Let $S_u(x)$ be a Schubert polynomial and let $S_v(x;y)$ be a double Schubert polynomial. Then their product can be expressed in terms of the double Schubert polynomials as
$$S_u(x)S_v(x;y)=\sum_w{c_{...
11
votes
0answers
363 views
Theorems proved using combinatorial nullstellensatz that have no other known proof
Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question. ...
11
votes
0answers
327 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 ...
11
votes
0answers
515 views
Evaluating products of cyclotomic polynomials at roots of unity
Are there general non-trivial conditions on $p(\cdot)$ and $n$, where $p(\cdot)$ is a product of cyclotomic polynomials and $n$ is a positive integer, such that all the coefficients of $p(\cdot)$ are ...
11
votes
0answers
224 views
When is a group Fibonacci sequence contained in a single conjugacy class?
First a definition: a Fibonacci sequence in a group is a sequence in which the first two elements may be arbitrary, and from there on each element is a product (using the group operation) of the ...
11
votes
0answers
710 views
Erdos multiplication problem revisited
The well-known problem is acquiring a cardinality of the set of distinct numbers in the multiplication table n x m.
The very problem has been discussed in-depth and, as such, I require no further ...
11
votes
0answers
317 views
The Universal Labeling of graph
The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...
11
votes
0answers
402 views
Colouring a graph whose edge set is a special union of cliques
I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...
11
votes
0answers
286 views
Right-angled polytopes
%This question is motivated by the little discussion here at the bottom.
The following thing are known about hyperbolic right-angled polytopes:
Compact hyperbolic right-angled polytopes do not exist ...
11
votes
0answers
519 views
Ramanujan Digraphs?
In Gowers' paper on quasirandom groups, he suggests a spectral theory of bipartite graphs employ the singular values of the bipartite adjacency matrix. Accordingly, singular values appear to be a ...
11
votes
0answers
647 views
A basic question on Stone-Cech compactification of $\mathbb{Z}$
Can the identity isomorphism on the additive group $\mathbb{Z}$ be extended to a non-identity semigroup isomorphism on $\beta\mathbb{Z}$, and still preserves $\beta\mathbb{Z}\setminus\mathbb{Z}$? ...
11
votes
0answers
407 views
Linear eta product identities - how many are there?
For the Dedekind eta function, defined as usual by $\eta(q) = q^{\frac1{24}} \prod\limits_{n=1}^{\infty} (1-q^{n}) $, let for brevity $e_k:=\eta(q^k)$. With this notation, a blog entry of Michael ...
11
votes
0answers
776 views
Hamiltonian cycles and fundamental groups
I'm interested in the interplay between the Hamiltonian cycles of graphs and the compact surfaces they embed in. I was doing some reading on the Lovász conjecture for Cayley graphs, I started noticing ...
11
votes
0answers
347 views
Lower Bound on the Volume of Certain Polytopes
Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks
$$
\rho=\{B_1,B_2,\ldots,B_{k}\}
$$
we can define the set of equations
$$
E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in B_{i}}{x_j}\quad\text{...
11
votes
0answers
410 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,...
11
votes
0answers
646 views
A number theoretic identity
Let $n$ be a positive integer such that $2n+1$ is prime.
The elements of the factor group $G = \mathbb{F}^\times_{2n+1}/\{\pm 1\}$ can be represented by the integers $1,2,\ldots,n$. For every $x \in \...
10
votes
0answers
176 views
Fundamental circuit characterization of matroid independence complexes
I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...
10
votes
0answers
116 views
A combinatorial proof of the Harrow--Kolla--Schulman theorem
Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$.
For integers $0 \leq k \leq n$, define a ...
10
votes
0answers
331 views
Relation between a continued fraction and partitions
I am interested in the continued fraction
$$\sum\limits_k {{z^{{2^k} - 1}}} = \frac{1}{{1 - \frac{{{T_0}z}}{{1 - \frac{{{T_1}z}}{{1 - \frac{{{T_2}z}}{{1 -{ \ddots }}}}}}}}}.$$
OEIS A104977 states ...
10
votes
0answers
233 views
Looking for method to generalize parity argument for Klein's Theorem (Happy Ending Problem)
The famous "Happy Ending Problem" for quadrilaterals states:
Theorem Given a set of five points in the general position on the plane, there exists a subset of 4 which form the vertices of a convex ...
10
votes
0answers
137 views
Cospectral mate of rhombic dodecahedron
I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was ...
10
votes
0answers
264 views
$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan
There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....
10
votes
0answers
170 views
Asymptotics of subgraph densities in graphons
In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
10
votes
0answers
239 views
Greedy permutation of the set $\{1,2,\dots,n\}$ and prime numbers
Answering this question, another question came to my mind. For which $n$ will the greedy algorithm work?
We define a sequence of natural numbers $x_n$ recursively:
$$x_1 =1,$$
$$x_n \mbox{ is the ...
10
votes
0answers
341 views
Computing the ordinal of a rational language well-partially-ordered by the subword relation
Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...
10
votes
0answers
127 views
Ideals in strong Bruhat order
Recall that a (lower) ideal in a poset $(P, \le)$ is a subset $I\subset P$ such that $x\in I \Rightarrow y\in I$ for all $y\le x$. In am interested in ideals in finite Coxeter groups $W$ equipped ...
10
votes
0answers
143 views
types of generating functions (ordinary, exponential, ???) closed under substitution
A nice feature of ordinary and exponential generating functions is that they are closed under substitution: if $F(z)$ and $G(z)$ both have integer coefficients, then $F(G(z))$ also has integer ...
10
votes
0answers
164 views
Is there a nice formula for the “non-crossing substitution” of linear combinatorial species?
Background
A linear species is a functor
$$F : \mathrm{Lin} \to \mathrm{FinSet},$$
where $\mathrm{Lin}$ is the category of totally ordered sets and bijections and $\mathrm{FinSet}$ is the category ...
10
votes
0answers
295 views
Consequences of Zeeman's conjecture
Recall the Zeeman's conjecture: if $K$ is a contractible polyhedron of dimension 2, then $K\times I$ has a collapsible subdivision.
Zeeman showed that this implies the Poincaré conjecture in ...
10
votes
0answers
346 views
diameter as a Morse function
Consider the space $X_1$ of closed subsets not containing a pair of antipodal points of the unit circle. Here we have a kind of degenerate Morse function, defined by the diameter of the pointset. ...
10
votes
0answers
336 views
What are the homological properties of Young's lattice?
Young's lattice $Y$ is a graded poset and a distributive lattice whose elements are all the partitions of $n$ for $n \in \mathbb{N}$ with the poset relation coming from inclusion of Young diagrams. ...
10
votes
0answers
706 views
Reference/quote request: “All of combinatorics is the representation theory of $S_n$”
I think I remember reading somewhere a glib (or is it deep?) quote, perhaps due to Rota?, which was something like
"All of combinatorics is essentially [or can be reduced to?] the representation ...
10
votes
0answers
1k views
Generalization of Cauchy's identity
Let $ s_{\lambda} $ be the schur function associated to the partition $ \lambda $.
Cauchy's identity (as in Macdonald) states that
$$
\sum_{\lambda} s_{\lambda}(X)s_{\lambda}(Y) = \prod_{i,j}(1-...
