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

1,578 questions

**10**

votes

**0**answers

498 views

### Minimum spanning tree of a random graph

Consider $n$ points arbitrarily located on the plane. Consider a random graph $G$ drawn from $G(n, \frac12)$ on these points (i.e. the Erdos-Renyi random graph where every edge is selected with ...

**10**

votes

**0**answers

352 views

### Another combinatorial question about cyclic words

Here is a more general (and possibly more clearly stated) combinatorial version of this question, than this question. Let $u$ be a sequence of 0 and 1 of length $n$. Let $p,q,r$ be three natural ...

**10**

votes

**0**answers

264 views

### Are plactic classes convex under the right weak Bruhat order?

For those who are unfamiliar with the terminology, I'll explain a little.
The symmetric group $S_n$, as a type A Coxeter group, has generators $\{s_1,\ldots,s_{n-1}\}$ with relations (1) $s_i^2$ for ...

**10**

votes

**0**answers

432 views

### Has the technique of “sprinkling” been used in studying random matrices?

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...

**10**

votes

**0**answers

331 views

### Positivity of polynomial sequences via generating series

In this question I address
the problem of proving the nonnegativity of a numerical sequence
$a_0,a_1,a_2,\dots$ via generating series technique. In the notation
$A(x)=\sum_{n=0}^\infty a_nx^n\ge0$ ...

**10**

votes

**0**answers

398 views

### Maximizing the volume in a family of subsets of a cube

Starting from a question in probability, I arrived to the following optimization problem.
Let $I:=[0, 1],$ and let $A$ be a Lebesgue measurable subset of the $n$-dimensional cube, $A\subset I^n.$ ...

**9**

votes

**0**answers

383 views

### Positive integers written as $\binom{w}2+\binom{x}4+\binom{y}6+\binom{z}8$ with $w,x,y,z\in\{2,3,\ldots\}$

Let $\mathbb N=\{0,1,2,\ldots\}$. Recall that the triangular numbers are those natural numbers
$$T_x=\frac {x(x+1)}2\quad \text{with}\ x\in\mathbb N.$$
As $T_x=\binom{x+1}2$, Gauss' triangular number ...

**9**

votes

**0**answers

249 views

### Commuting matrix variety $[A,B]=0$ - can one geometrically explain divisibility of $F_ q$ point count by high powers of $q$?

$\DeclareMathOperator\Comm{Comm}\DeclareMathOperator\Id{Id}$Consider the variety $\Comm$ of commuting matrices $[A,B]=0$ over some field $K$. It is much studied, and interesting for various reasons.
...

**9**

votes

**0**answers

121 views

### Minimal number of colours in distinguishing colouring of biconnected graphs

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.
Problem. Is it true that each biconnected graph possesses a distinguishing ...

**9**

votes

**0**answers

267 views

### Why does Loday call the permutohedra “zylchgons”?

Today I was reading Jean-Louis Loday's classic paper, "Realization of the Stasheff polytope", in which he produces a simple and very pretty realization of the associahedra as convex polytopes. He ...

**9**

votes

**0**answers

435 views

### Which finite sets could be packed into a square?

This question is inspired by an interesting visualization of the finite levels of von Neumann's hierarchy on Adam P. Goucher's blog, Complex Projective 4-Space.
The problem starts with a two-...

**9**

votes

**0**answers

211 views

### Covering inequality for sets of intervals

Let $I$ and $J$ be finite sets of open intervals $(a,b)\subset\mathbb R$. For a finite set of points $P\subset \mathbb R$ we denote those subsets of intervals from $I$ and $J$ containing some point ...

**9**

votes

**0**answers

131 views

### Interactions between pseudoline arrangements and braid groups?

It is common to represent
pseudoline arrangements
as wiring diagrams:
Fig. from: "Hamiltonicity and colorings of arrangement ...

**9**

votes

**0**answers

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

**9**

votes

**0**answers

190 views

### How to count integer lattice points close to a subspace of $\mathbb R^n$?

Consider $m$ linearly independent vectors in $n$-dimensional Euclidean space, $v_1,...,v_m \in \mathbb R^n$ where $1\leq m<n$, and let $U := {\rm span}(v_1,...,v_m)$ denote the $m$-dimensional ...

**9**

votes

**0**answers

227 views

### Generating $S_n$ with a fundamental transposition and a big cycle

I apologize in advance if this is too amateur, this is not really my area, but I'm very curious.
We have a permutation $\pi \in S_n$ and we want to represent it as a product of $\sigma = (1\;2)$ and $...

**9**

votes

**0**answers

152 views

### Some quotients of Hankel determinants

This question has been inspired by Hankel determinants of binomial coefficients.
For a sequence $\{h_{n}\}_{n=0}^{\infty}$ denote by $H_n$ the Hankel matrix
$$H_{n}:=\begin{pmatrix}
h_{0} & h_{...

**9**

votes

**0**answers

226 views

### Fractional Matching version of Hall's Marriage theorem

Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...

**9**

votes

**0**answers

154 views

### Chromatic number of Voronoi diagrams of lattices

Let $L$ be a Euclidean lattice. Define a graph whose vertex set is $L$ and where two points $x,y\in L$ are declared to be adjacent whenever the cells of $x$ and $y$ in the Voronoi diagram of $L$ have ...

**9**

votes

**0**answers

253 views

### pattern-avoiding permutations vs multi-core partitions

Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. ...

**9**

votes

**0**answers

145 views

### Generating functions of real-rooted polynomials

Suppose $f_n(t)$ is a degree $n$ polynomial. Let $F(t,u) = \sum_n f_n(t)u^n$.
What conditions on $F(t,u)$ tell us that the $f_n(t)$ are real-rooted? Similarly, are there any conditions on $F(t,u)$ ...

**9**

votes

**0**answers

172 views

### Positivity of coefficients of Ehrhart polynomial of n-Tetrahedron

A set of positive integers $d_1, \dots, d_n$ describe two n-dimensional closed lattice tetrahedron:
$$ T = \left\{ (x_1, \dots, x_n) \in \mathbb{R}^n: \sum_{i=1}^n \frac{x_i}{d_i} \leq 1 \textrm{ and ...

**9**

votes

**0**answers

143 views

### Cycles of length $2^n - 2$ in the De Bruijn graph

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
...

**9**

votes

**0**answers

279 views

### Weighted sum of the Simsun (Andre) permutations

Let $ c_{n,k} $ be the Simsun permutations$^1$ defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1);$
$$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, \hspace{0....

**9**

votes

**0**answers

261 views

### An abstract zero-sum problem

I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...

**9**

votes

**0**answers

370 views

### Partition regularity in the squares

A linear equation $c_1x_1 + \cdots + c_sx_s = 0$ is partition regular if for every partition of the natural numbers into colour classes $A_1, \ldots, A_r$, there is a solution to the equation in which ...

**9**

votes

**0**answers

205 views

### Families of subsets with pairwise symmetric differences of cardinality at most $k$

Let $X$ be an $n$-element set and $\mathcal{F} \subseteq P(X)$ such that for all $A, B \in \mathcal{F}$, $|A△B| \leq k$ where $A△B$ denotes the symmetric difference of $A$ and $B$. Suppose $|\mathcal{...

**9**

votes

**0**answers

300 views

### Embedding $\beta\mathbb{N}$ into a product of Cantor sets

Let us consider $\beta\mathbb{N}$, the Stone-Čech compactification of the natural numbers (where we do not take $0$ to be a natural number, so the only idempotent elements are nonprincipal ...

**9**

votes

**0**answers

299 views

### Pattern Avoidance in Poset Permutations

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it.
A permutation on a $n$-...

**9**

votes

**0**answers

359 views

### Combinatorial results by Poincaré duality

For the n-dimensional Torus, the k-th homology group (with integer coefficients) is isomorphic to the direct sum of $n \choose k$ copies of $\mathbb{Z}$.
Poincaré duality thus gives us a somewhat ...

**9**

votes

**0**answers

143 views

### Is every planar point set the projection of vertices of a neighborly 4-polytope?

More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ that are vertices of a neighborly polytope.
This problem comes from a simple ...

**9**

votes

**0**answers

228 views

### Degree of a cone over the set of rank $r$ $n\times n$ matrices

Let $X_r\subset Mat_{n\times n}(C)$ denote the variety of rank at most $r$ matrices, set $k=n-r$ and assume $n\geq k^2-1$. Consider the cone over $X_r$ with vertex spanned by the first $k^2-1$ entries ...

**9**

votes

**0**answers

752 views

### Balls and bins — concentration bounds pertaining to the minimal load bin

Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...

**9**

votes

**0**answers

205 views

### A duality on partial permutations

A partial permutation matrix $\pi$ is one with at most one 1 in any row and column (the rest 0s). Given one, we can cross out to the East and South (but not Southeast) of each 1. Some boxes get ...

**9**

votes

**0**answers

426 views

### An identity for Hankel determinants

Is the following result about Hankel determinants known or a simple consequence of some known results?
Let
$f(x) = \frac{\displaystyle 1}{{\displaystyle 1 - \frac{{a x^{m + 2}}}{\displaystyle {1 - \...

**9**

votes

**0**answers

209 views

### An inequality for the ratio of standard Young tableau with {1,2,…,k} in the first row

For a partition $\lambda \vdash n$, define $\dim \lambda$ to be the number of standard Young tableaux of shape $\lambda$, and $\dim \lambda/(k)$ as the number of standard Young tableaux with $1,2,\...

**9**

votes

**0**answers

685 views

### Cliques in the Paley graph and a problem of Sarkozy

The following question is motivated by pure curiosity; it is not a part
of any research project and I do not have any applications. The question
comes as an interpolation between two notoriously ...

**9**

votes

**0**answers

367 views

### The number of rows in a tableau generated by the RSK algorithm.

It is well known that the number of rows in the semistandard Young tableaux correspondent to a two-line array via RSK is equal to the length of the longest (strictly) decreasing subsequence in the ...

**9**

votes

**0**answers

294 views

### Are each of these functions injective on their domains?

If $n\geq 2$, is the function
$$ f_n(a,b) := \left( \frac{\binom{n}{a}}{\binom{n}{b}}\right)^{\frac{1}{b-a}}$$
injective over the set $\{ (a,b) \;|\; 0\leq a<b \leq n, \; a+b \neq n \}$?
I heard ...

**9**

votes

**0**answers

199 views

### Reference for sparseness of incomparability graphs implying sparseness of covering graphs

If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the ...

**9**

votes

**0**answers

408 views

### Kruskal-Katona type question for union-closed families of sets

Question : Let $n,k$ be two positive integers with $n \geq k$. Let $\mathcal{F}$ be a family of $C(n,k)$ sets, each of size $k$, and let $\langle\mathcal{F}\rangle$ denote the union-closed family ...

**9**

votes

**0**answers

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

**9**

votes

**0**answers

178 views

### What is known about the number of permissible simplicial complexes given the number of k-cells?

Motivation: I am working on a problem that reduces to finding simplicial complexes given some data (details are unnecessary), but all I have managed to wrangle from my input is the number of cells of ...

**9**

votes

**0**answers

663 views

### Faa di Bruno and Free Probability?

It is possible to glean many combinatorial identities using Faa di Bruno’s formula for the coefficients of higher derivatives of a composite function. For many examples, see David Vella’s paper. The ...

**9**

votes

**0**answers

709 views

### Counting Lattice Points in Real Polytopes

Suppose one did have an exact formula for the number of $\mathbb{Z}^n$-lattice points intersecting an arbitrary dilate of a (not necessarily rational) finite, closed and convex $n$-polytope. As a ...

**9**

votes

**0**answers

173 views

### Asymptotics of packing

Define $m(n,k,l)$ as the maximal size of a family $k$-element subsets of $[n]$ having the property that the intersection of every two sets is less than $l$.
As stated on wikipedia, in 1985 Rödl ...

**9**

votes

**0**answers

1k views

### Weighted Hamming distance

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, for ...

**9**

votes

**0**answers

746 views

### Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another

Please consider the set of all possible strings of some finite size $M$ alphabet $\Sigma$, $\alpha$ $= a_1, a_2, ..., a_k, ..., a_n$, of length $|\alpha| = L$. The Levenshtein distance (or 'edit ...

**8**

votes

**0**answers

162 views

### q-analog of $(d/dx) \binom{x}{k}$?

It is not hard to find easy formulas for the derivative of the function $\binom{x}{k}$, for instance it is not too hard to see (for $k$ an integer) that
$\frac{d}{dx} \binom{x}{k} = \sum_{i=1}^k \...

**8**

votes

**0**answers

98 views

### Permutation groups with diameter $O(n \log n)$

I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:
Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...