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
Filter by
Sorted by
Tagged with
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}\...
Aaron's user avatar
  • 794
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 ...
Łukasz Grabowski's user avatar
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 ...
Douglas S. Stones's user avatar
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 (...
Arsenii Sagdeev's user avatar
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 \...
Amritanshu Prasad's user avatar
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. ...
Dylan Thurston's user avatar
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 ...
Gil Kalai's user avatar
  • 24.2k
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\...
Seva's user avatar
  • 22.8k
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 ...
Martin Rubey's user avatar
  • 5,533
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 ...
Benjamin Steinberg's user avatar
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$ (...
Jens Renders's user avatar
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 ...
Sebastien Palcoux's user avatar
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 ...
Gil Kalai's user avatar
  • 24.2k
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$....
T. Amdeberhan's user avatar
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 $...
T. Amdeberhan's user avatar
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 ...
hkju's user avatar
  • 121
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$. ...
John Machacek's user avatar
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 ...
Joseph Van Name's user avatar
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_{...
Matt Samuel's user avatar
  • 2,008
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 ...
nasosev's user avatar
  • 221
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 ...
Michał Kukieła's user avatar
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 ...
Richard Stanley's user avatar
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 ...
Gordon Royle's user avatar
  • 12.3k
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 ...
Douglas S. Stones's user avatar
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 $...
Stefan Kohl's user avatar
  • 19.5k
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 ...
John's user avatar
  • 121
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 ...
Maritza Sirvent's user avatar
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 ...
Gjergji Zaimi's user avatar
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.$$ ...
Alexander Moll's user avatar
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_{...
Vasu vineet's user avatar
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,...
Fabio Tonini's user avatar
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 ...
ilyaraz's user avatar
  • 1,771
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}\...
T. Amdeberhan's user avatar
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 ...
domotorp's user avatar
  • 18.3k
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 ...
CHUAKS's user avatar
  • 775
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 ...
Pierre-Yves Gaillard's user avatar
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 ...
Sam Hopkins's user avatar
  • 22.7k
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{...
Pietro Majer's user avatar
  • 56.5k
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\{...
Abdelmalek Abdesselam's user avatar
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, ...
Adam P. Goucher's user avatar
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 ...
Johann Cigler's user avatar
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 $...
Zach Teitler's user avatar
  • 6,197
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 ...
user94267's user avatar
  • 305
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 ...
JonCC's user avatar
  • 211
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 $\...
Igor Makhlin's user avatar
  • 3,493
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 ...
Gro-Tsen's user avatar
  • 29.9k
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....
kakia's user avatar
  • 389
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 ...
Bugs Bunny's user avatar
  • 12.1k
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 ...
domotorp's user avatar
  • 18.3k
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}...
Matt Samuel's user avatar
  • 2,008

1 2
3
4 5
61