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

**15**

votes

**0**answers

2k views

### Covers of $Z^k$

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ ...

**15**

votes

**0**answers

858 views

### Polynomials with presumably positive coefficients

After seeing that some positivity problems get their solutions on MO,
I am quite enthusiastic of posing my (and not only) problem of positive flavour.
In order to state it, I have to introduce the ...

**15**

votes

**0**answers

866 views

### Is every k-edge-connected graph also k-trail-ordered?

This is an old question of Aradhana Narula-Tam and Philip Lin that I think deserves wider circulation. It appeared in Discrete Math. 257 (2002), page 613, but not many people have looked at it and it ...

**15**

votes

**0**answers

875 views

### Optimal Monotone Families for the Discrete Isoperimetric Inequality

Background: the Discrete Isoperimetric Inequality
Start with a set X={1,2,...,n} of n elements and the family $2^X$ of all subsets of X.
For a real number p between zero and one, we consider a ...

**14**

votes

**0**answers

190 views

### A symmetry of lattice paths

The number of $n$-step NSEW lattice paths from $(0,0)$ to $(a,b)$ that intersect the line $y=k$ precisely $t$ times is independent of $k$, for $0\leq k\leq b$, where we assume $b\geq0$ for simplicity.
...

**14**

votes

**0**answers

229 views

### References on Discrete field theory vs Discrete differential geometry vs Combinatorial topology

Let me ask several related questions on discretization of classical field theory:
In topological folklore, it is known that cochains are "discrete analogues" of differential forms, and coboundary ...

**14**

votes

**0**answers

348 views

### The rank of a “triangle-free” matrix

This is a version of the question I asked recently, but the assumptions got now strengthened substantially.
Suppose that $A=(a_{ij})_{1\le i,j\le n}$ is a square matrix with all elements in $\{0,\...

**14**

votes

**0**answers

709 views

### A Combinatorial Game: the Snake and the Hunter

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...

**14**

votes

**0**answers

224 views

### Is combinatorial automorphism of symmetric convex polytope always antipodal?

The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...

**14**

votes

**0**answers

432 views

### Grothendieck on polyhedra over finite fields

In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most singular ...

**14**

votes

**0**answers

367 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**14**

votes

**0**answers

363 views

### Do the coefficients of these irreducible polynomials always become periodic?

Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_n\ne0$.
Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+...

**14**

votes

**0**answers

396 views

### Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...

**14**

votes

**0**answers

726 views

### A Conjecture About Directed Graphs that are the Union of Two Trees

Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed
spanning trees. Suppose that
There no subset X of vertices so that
there is precisely one directed edge
from X ...

**14**

votes

**0**answers

667 views

### Capelli determinant = Duflo ( determinant) - was it known ?

Question briefly. Was this fact known: Capelli determinant = Duflo (determinant) ? (This is an equality of the two central elements in universal enveloping of Lie algebra $gl_n$).
I googled a lot ...

**13**

votes

**0**answers

187 views

### Is the set of power matrices decidable?

Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a ...

**13**

votes

**0**answers

144 views

### Generalization of Newton's identities to Schur functions

In some recent work, I've stumbled across the following identity for $\lambda \vdash n$:
$$
n s_\lambda = \sum_{k=1}^n p_k \sum_{\mu \nearrow_k \lambda} (-1)^{\mathrm{ht}(\lambda/\mu)} s_\mu.
$$
Here, ...

**13**

votes

**0**answers

2k views

### Identifying poisoned wines, with a twist

(This is a joint musing with Andrew Gordon and Wyatt Mackey)
There is a classic, elementary riddle, discussed before on MO and math.SE: suppose you have 1000 bottles of wine, and one is poisoned. The ...

**13**

votes

**0**answers

411 views

### What is the geometric intuition behind Wilf-Zeilberger theory?

This problem is somehow inspired by a bunch of impressive posts of combinatorial identities by T. Amdeberhan. Earlier this month I learnt from computer scientists that they have a generic algorithmic ...

**13**

votes

**0**answers

319 views

### A hard Lefschetz theorem for nilCoxeter algebras

Let $W$ be a finite Coxeter group and $\mathcal{N}(W)$ its nilCoxeter
algebra (over the reals, say), as defined at
https://en.wikipedia.org/wiki/Nil-Coxeter_algebra. $\mathcal{N}(W)$ has
a natural ...

**13**

votes

**0**answers

535 views

### Special configurations on a circle from a homological algebra problem

Here is the short version of the combinatorial problem:
Given a positive integer $n \geq 2$. Draw a circle with $2n$ points indexed by the numbers from $\mathbb{Z}/ 2n \mathbb{Z}$. We colour the ...

**13**

votes

**0**answers

513 views

### Chasing a 1950s thesis from the University of Dhaka on block designs

On behalf of a friend I am searching for a thesis on block designs from the 1950s. The details are below.
Author: Qazi Motahar Husein (Sometimes Husain or Hussein).
Title of the Thesis: Symmetrical ...

**13**

votes

**0**answers

248 views

### Some $q-$analogues of $ \sum\limits_{j = - k}^k {{{( - 1)}^{ j}}}\binom{n}{k-j}\binom{n}{k+j}=\binom{n}{k}.$

Let ${\left( {a;q} \right)_n}=\prod\limits_{j = 0}^{n - 1} {(1-{q^j}a} )$ and
let $ {{n}\brack{k}}_q$ denote a $q-$binomial coefficient.
I am interested in $q-$analogues of the identity $ \sum\...

**13**

votes

**0**answers

382 views

### How large must $A$ be if $\{1, \ldots, N\} \subseteq A-A$?

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An ...

**13**

votes

**0**answers

223 views

### Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...

**13**

votes

**0**answers

192 views

### Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once

I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length $...

**13**

votes

**0**answers

335 views

### Are the zeros of Tutte polynomials dense in $\mathbb C^2$?

For the chromatic polynomials of graphs we have two nice theorems which describe the behavior of their zeros: Thomassen proved that the set of real zeros of all chromatic polynomials is the union of $\...

**13**

votes

**0**answers

583 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

3k views

### Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?

**13**

votes

**0**answers

402 views

### How much must deleting a spanning tree reduce edge-connectivity?

Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What ...

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

273 views

### Escaping from a centralizer

Let $G = Sym(n)$, $n$ even. Let $H<G$ be the stabilizer of the partition $\{\{1,2\},\{3,4\},\dotsc,\{n-1,n\}\}$, or, what is the same, the centralizer of $(1\;2) \dotsc (n-1\; n)$.
By Stirling's ...

**12**

votes

**0**answers

175 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

302 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

354 views

### What is this sequence?

This is again a question that I asked at Stack Exchange, but got no answer so far, so I am trying here.
Let:
$$ a_n=\sum_{k\ge0}(k+1) {n+2\brack k+2}(n+2)^kB_k$$
$B_k$ is the Bernoulli number. ${n\...

**12**

votes

**0**answers

315 views

### The threshold for a perfect matching in a random subgraph of a regular bipartite graph?

The following question seems very natural.
It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...

**12**

votes

**0**answers

567 views

### Pointwise (Hadamard) matrix product and the rank

$\DeclareMathOperator{\rk}{rk}$
Suppose that $A$ is a square matrix of order $n$. If, for any polynomials $P$ and $Q$ with $\deg P+\deg Q\le 2$, we have
$$ P(A)\circ Q(A^t) = P(1)Q(1)\, I_n \tag{$\...

**12**

votes

**0**answers

246 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

425 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

### Reference request: exponential growth rates of subword-closed languages are integers

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters. The ...

**12**

votes

**0**answers

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

**12**

votes

**0**answers

187 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

398 views

### Transitivity of balanced mass transport in Z

Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...

**12**

votes

**0**answers

200 views

### Why must commuting maps (of an interval) without common fixed points have at least 11 fixed points for the composition?

I've been looking at the examples of commuting functions on a closed interval which have no common fixed points. These were discovered in 1967 by William M Boyce and J Philip Huneke.
Earlier work by ...

**12**

votes

**0**answers

319 views

### On some special spanning trees of grid graphs

I would like to know if there are existing results on the following objects:
spanning trees of a grid graph, with no corridor
where a corridor is a vertex having exactly two neighbors, on opposite ...

**12**

votes

**0**answers

467 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

178 views

### Does a huge set of random points in the plane almost surely have a checkerboard-triangulation

A set of $n$ points in the plane in generic position (no alignement of three points) has at least $2.012^n$ different triangulations
of its convex hull involving only the set of given points.We call ...

**12**

votes

**0**answers

192 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

516 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

**0**answers

375 views

### Best known constant for parallel sorting

I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because ...