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