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