Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

10
votes
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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$ ...