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.
3,009
questions with no upvoted or accepted answers
13
votes
0
answers
733
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
13
votes
0
answers
703
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 ...
13
votes
0
answers
1k
views
Finding a chromatic polynomial by polynomial fitting
I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph ...
12
votes
0
answers
160
views
Can the optimal packing density in $\mathbb{Z}^d$ be irrational?
For a finite $S \subset \mathbb{Z}^d$, let $d_p(S)$ be its optimal packing density. That is, the maximal lower asymptotic density of $A+S$, where $A \subset \mathbb{Z}^d$ is such that $(a_1+S)\cap (...
12
votes
0
answers
504
views
$q$-analogue of the multinomial theorem?
The $q$-binomial theorem states that
$$
\prod_{k=0}^{n-1}(1+q^kt) = \sum_{k=0}^n q^{\binom k2}{n\brack k}_q t^k.
$$
This identity is a $q$-analogue of the binomial theorem
$$
(1+t)^n = \sum_{k=0}^n \...
12
votes
0
answers
253
views
Computing the number of ways to delete vertices sequentially without disconnecting a graph
Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph. ...
12
votes
0
answers
222
views
3-manifolds with stacked links
Stacked spheres
A triangulation of a 2-dimensional sphere is called a stacked sphere if it is obtained inductively from the boundary of a 3-simplex by deleting a 2-face (triangle) $T$ adding a new ...
12
votes
0
answers
447
views
Around the Erdős-Ginzburg-Ziv theorem
(Here is a problem that emerged in a conversation with Fedor Petrov and should really be a sort of "joint posting" if this format were supported.)
For any positive integers $k_1\le k_2\le\...
12
votes
0
answers
244
views
$\mathfrak{sl}_3$ webs without faces having a multiple of 4 sides
In settling the main conjecture of Cyclic action on Kreweras walks, see https://arxiv.org/abs/2005.14031, a rather interesting object popped up.
Recall from
Kuperberg, Greg, Spiders for
rank 2 Lie ...
12
votes
0
answers
311
views
Combinatorial proof of invertibility of a symmetric matrix associated to the ring of matrices over a finite field
Let $F$ be a finite field of $q$ elements with characteristic $p$. Let $M_n(F)$ be the ring of $n\times n$ matrices over $F$. We define a $q^{n^2}\times q^{n^2}$ symmetric matrix $L$ over the ...
12
votes
0
answers
100
views
How many upper sets in this decomposition of finite posets
Let $X$ be a finite poset.
If
$$X = X_1 \cup X_2$$
where $X_1$ and $X_2$ are strict upper sets, then a lot of properties of $X$ can be inferred from the smaller posets $X_1, X_2$ and $X_1\cap X_2$ (...
12
votes
0
answers
190
views
Non-Boolean Eulerian interval of finite groups
An Eulerian subgroup lattice is Boolean (see here), so it is natural to wonder whether it is also true for an interval of finite groups. The smallest non-Boolean Eulerian lattice is the following:
It ...
12
votes
0
answers
327
views
The number of labeled pairs of edge disjoint trees and related questions
I wonder what is known on the following:
1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices?
2) (harder, it seems) What ...
12
votes
0
answers
627
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$....
12
votes
0
answers
510
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 $...
12
votes
0
answers
266
views
Number of updown sequences of $1,1,2,2,\cdots,n,n$
I would like to count the updown sequences of the set $\{1,1,2,2, \cdots, n,n \}.$
Sequence $a_1, a_2, a_3, \ldots$ is an updown sequence if the sequence satisfies the following: $ a_1 \lt a_2 \gt a_3 ...
12
votes
0
answers
556
views
Computer searches for the $g$-conjecture
McMullen's $g$-conjecture aims the classify possible $f$-vectors of simplicial $d$-spheres. The $g$-conjecture has been proven for polytopal spheres and for simplicial spheres of dimension $d < 5$. ...
12
votes
0
answers
215
views
Do the Laver tables converge to the Sierpinski triangle with a line segment sticking out in the hyperspace topology?
Let $(\{1,...,2^{n}\},*_{n})$ denote the $n$-th Laver table.
Let
$$C_{n}=\{(\frac{x}{2^{n}},\frac{x*_{n}y}{2^{n}})|x,y\in\{1,2,3,...,2^{n}\}\}$$
for all $n\in\mathbb{N}$.
Then since $C_{n}$ is a ...
12
votes
0
answers
702
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_{...
12
votes
0
answers
220
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 ...
12
votes
0
answers
350
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 ...
12
votes
0
answers
498
views
A $q$-analogue of Foulkes' character related to alternating permutations
My paper "Alternating permutations and symmetric functions" at
http://math.mit.edu/~rstan/papers/altenum.pdf enumerates certain
classes of alternating permutations, such as those whose inverse is
...
12
votes
0
answers
448
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 ...
12
votes
0
answers
255
views
Proving that the set of $\lfloor n/3 \rfloor+1$ partial Latin squares given by Pebody is unavoidable?
Introduction
Cutler and Öhman (2006) attribute to Pebody (via personal communication) a construction of a set of $k:=\lfloor n/3 \rfloor+1$ partial Latin squares which are unavoidable (i.e., any ...
12
votes
0
answers
537
views
Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers
Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...
12
votes
1
answer
2k
views
Hobbled rook tour – Hamiltonian cycle on square grid
Consider a square grid of even side length ($2n \times 2n$). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...
12
votes
0
answers
595
views
Once differentiable, piecewise degree three polynomials on triangulated planar domains
Here is an easily described, but very difficult, problem that I
(and a number of other people) really would like to see solved during
our life times. The basic problem is to compute the dimension of ...
12
votes
0
answers
894
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 ...
12
votes
0
answers
857
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
0
answers
455
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
0
answers
524
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
0
answers
349
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
0
answers
266
views
Color your partitions by parity
Let $a_c(n)$ be the number of ways to partition a positive integer $n$ where each even part comes in $c$ colors. Then, we can supply the generating function
$$\sum_{n\geq0}a_c(n)q^n=\prod_{k\geq1}\...
11
votes
0
answers
479
views
Are there 100 points that are part of every half-density part of the plane?
Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$?
I am deliberately being vague ...
11
votes
0
answers
527
views
How to determine the sign for the sum over all simple paths in the graph
$\DeclareMathOperator\perm{perm}\DeclareMathOperator\len{len}$Let $A$ be the adjacency matrix of a tree $T$ for some ordering $v_1,...,v_n$ of the vertices, and let $D=xI-A$ its characteristic ...
11
votes
0
answers
272
views
Does every finite poset have a rigid endomorphism?
Crossposted on Mathematics.
In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...
11
votes
1
answer
676
views
Two remarkable weighted sums over binary words
This question builds off of the previous MO question Number of collinear ways to fill a grid.
Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting ...
11
votes
0
answers
159
views
Bijections $\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ with vanishing local means
This is just a summer-time curiosity arisen after a recent question by Dominic van der Zypen.
For a finite subset $S$ of $\mathbb{Z}\times\mathbb{Z}$ and a function $f$ on $\mathbb{Z}\times\mathbb{...
11
votes
0
answers
330
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
0
answers
173
views
Iterated automorphism groups of finite groups
Let $\mathcal{G}$ be the set of isomorphism classes of finite groups.
There is an operation $\mathrm{Aut} : \mathcal{G} \rightarrow \mathcal{G}$ which gives the automorphism group of a given group, ...
11
votes
0
answers
399
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 ...
11
votes
0
answers
244
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
0
answers
438
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
0
answers
225
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
0
answers
410
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
0
answers
232
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
0
answers
290
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....
11
votes
0
answers
275
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 ...
11
votes
0
answers
226
views
Is there a Ramsey theory for Kneser graphs?
Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...
11
votes
0
answers
234
views
Coefficients of universal Schubert polynomials
Let $e_i^j$ be the elementary symmetric polynomial in $x_1,x_2,\ldots,x_j$. Then the ordinary Schubert polynomial has an expansion of the form
$$S_u(x)=\sum_{i_1,i_2,\ldots,i_n}{a^{i_1,i_2,\ldots,i_n}...