Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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-...