Tagged Questions
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
5
votes
0answers
129 views
Double Counting: Motivic Edition
One of the most important proof techniques in combinatorics is double counting: proving that both sides of an identity count elements of some set in two different ways. This question is an attempt at ...
0
votes
1answer
70 views
Can the union of difference sets in towers equal $\omega$?
We write $A\subseteq^* B$ if $A\setminus B$ is finite.
Let $(A_n)_{n\in\omega}$ be a sequence of subsets of $\omega$ such that for all $n\in\omega$ we have $A_n \subseteq^* A_{n+1}$ and $A_{n+1}\not\...
14
votes
2answers
267 views
Eigenvalues and eigenvectors of the matrix with entries $\dbinom{n+1}{2j-i}$ for $i, j = 1, 2, \ldots, n$
Let $n$ be a nonnegative integer, and let $B$ be the $n \times n$-matrix (over the rational numbers) whose $\left(i, j\right)$-th entry is $\dbinom{n+1}{2j-i}$ for all $i, j \in \left\{ 1, 2, \ldots, ...
3
votes
0answers
96 views
Halin Graphs with Highest Number of Hamilton Cycles
Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...
12
votes
2answers
293 views
Can we realize a graph as the skeleton of a polytope that has the same symmetries?
Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton.
A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
2
votes
0answers
130 views
The name for injective map $f:\mathbb{N}\rightarrow\mathbb{N}$ with $f(n)\geq n$ property
What is the name for map $f:\mathbb{N}\rightarrow\mathbb{N}$ (from natural numbers into natural numbers) with the following propeties:
1) $f$ is injective
2) $f(n)\geq n$ for every $n$?
4
votes
1answer
87 views
Two disjoint trees
Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which ...
2
votes
1answer
111 views
Colored balls and bins — asymptotic behavior
Suppose I have $N$ bins and a set of balls with $m$ different colors, where there are $n_i$ balls of color $i$. I also have values $0 < p_i \leq 1$ for all colors $i$. I throw all $\sum_i n_i$ ...
5
votes
3answers
163 views
Algorithm to decide if the union of a set system covers the power set
Assume that we have a set system $\mathfrak T = \{\mathcal T_1, \mathcal T_2, \dots, \mathcal T_N \}$ where each $\mathcal T_k$ is a collection of subsets of $[n] := \{1,\dots,n\}$ of the form
$$ \...
12
votes
1answer
290 views
A matrix identity related to Catalan numbers
Let $$C_n=\frac{1}{2n+1}\binom{2n+1}{n}$$ be a Catalan number. It is well-known that $$(\sum_{n\ge{0}}C_n x^n)^k=\sum_{n\ge{0}}C(n,k)x^n$$ with $$C(n,k)=\frac{k}{2n+k}\binom{2n+k}{n}.$$
It is also ...
2
votes
0answers
27 views
2-dimensional smooth lattice polytopes with minimal edge lengths
For each integer $k \geq 3$, does there exist a full-dimensional, $2$-dimensional, smooth lattice polytope $P$ with $k$ edges, such that each edge contains only two lattice points (i.e. only its ...
1
vote
0answers
58 views
Simple polytope with smooth facets
Let $P$ be a simple $3$-dimensional (and full-dimensional) lattice polytope such that every facet $F$ is a smooth polytope. Is then $P$ itself smooth?
EDIT: A full-dimensional lattice polytope $P$ is ...
4
votes
1answer
115 views
Minimal covers in hypergraphs with finite edges
Let $H=(V,E)$ be a hypergraph. We say that $C\subseteq E$ is a cover if $\bigcup C = V$. Let $H$ be a hypergraph with the following properties:
$\bigcup E = V$,
all members of $E$ are finite, and
$d,...
1
vote
0answers
137 views
+50
Combinatorial and computational problem related to Weyl groups and the coroot lattice
Let $W$ be a Weyl group with root system $R$ and with set of positive roots $R^+$. Let $\tilde{R}^+$ be the set of $B$-cosmall roots, i.e. positive roots $\alpha$ which satisfy $\ell(s_\alpha)=2\...
12
votes
2answers
279 views
Cycle generating function of permutations with only odd cycles
Let $\mathrm{ODD}(n)$ be the set of permutations in $\mathfrak{S}_n$ whose cycle lengths are all odd. It is known that
$$ \#\mathrm{ODD}(n) = \begin{cases} ((n-1)!!)^2 &\textrm{ if $n$ is even}; \\...
3
votes
1answer
103 views
What is the probability for a Binomial to be greater than other?
Let $X = B(n, p)$ and $Y = B(k, q)$ be two random variables with binomial distribution and, let $s$ be a positive integer. Assume that $n > k+s$ and $np \geq kq+s$.
What is the probability for $X$ ...
24
votes
1answer
459 views
Has the $E_8$-based generating function for squares numbers been proven?
In his 2004 paper Conformal Field Theory and Torsion Elements of the Bloch Group, Nahm explains a physical argument due to Kadem, Klassen, McCoy, and Melzer for the following remarkable identity. Let $...
2
votes
2answers
96 views
Set of strings $S$ such that no string from $S$ is a substring of another one
Let $X$ be a subset of $\{0,1\}^*$ with the following property: for every pair of distinct strings $x_1$, $x_2$ from $X$
$x_1$ is not a substring of $x_2$ and $x_2$ is not a substring of $x_1$.
How ...
2
votes
1answer
148 views
Maximality with respect to the splitting property
Let $X$ be a set and ${\cal P}(X)$ its powerset. We say that ${\cal F} \subseteq {\cal P}(X)$ has the splitting property (SP) if there is $A\in {\cal P}(X)$ such that for all $F\in {\cal F}$ we have $$...
3
votes
0answers
90 views
Dirichlet eta function and Stirling Permutations
The Stirling permutations of order $k$ is a permutation of the multiset $1, 1, 2, 2, ..., k, k$. The Dirichlet $\eta$-function is a function closely related to the Riemann $\zeta$-function.
According ...
5
votes
0answers
105 views
Polychromatic number of plane
Let $\chi$ be the least size of a partition of plane into pieces each of which omits unit distance. Let $\chi_p$ be the least size of a partition of plane into pieces each of which omits some distance....
5
votes
1answer
119 views
Counting promenades on graphs
Let a "promenade" on a tree be a walk going through every edge of the tree at least once, and such that the starting point and endpoint of the walk are distinct. What we mean by isomorphic promenades ...
2
votes
0answers
55 views
On the existence of a certain graph/hypergraph pair
Let $V$ be a finite set, $G$ a simple graph with vertex set $V$, and $H$ a hypergraph (i.e., set of subsets) with vertex set $V$ satisfying the following three conditions:
each pair of elements of $V$...
5
votes
0answers
98 views
How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?
Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...
1
vote
0answers
43 views
Matchings in infinite, not necessarily bipartite, graphs
Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs.
Is there a similar generalization of Tutte's theorem on ...
11
votes
1answer
713 views
A curious valuation of this sequence
The sequence $a_n$ given by
$$a_n=\sum_{k=0}^n\frac{n!}{k!}$$
is found at A000522 on OEIS with a description: total number of arrangements of a set with $n$ elements. Let $\nu_2(x)$ denote the $2$-...
2
votes
0answers
82 views
Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history
Two arrangements of (affine) hyperplanes in $d$-dimensional Euclidean space are combinatorially isomorphic (or combinatorially equivalent) if they have isomorphic posets of faces.
Counting the ...
5
votes
1answer
123 views
Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?
The sequence A006318 at OEIS stands for the Schröder numbers.
They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...
6
votes
1answer
132 views
Smallest set of nonzero vectors in $\mathbb F_2^n$ which intersects every 2-dimensional subspace
What is the smallest set of nonzero vectors in $\mathbb F_2^n$ which intersects every 2-dimensional subspace?
For example, for n = 3, the set {001, 010, 011} does the job, and is minimal. For n = 4, {...
2
votes
2answers
151 views
Random walk and isoperimetric constant
I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking.
Theorem(?): Let $\varepsilon>0$ ...
1
vote
1answer
93 views
A weaker version of Dirac's theorem
This is related to Dirac's theorem.
For any finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimal degree of all vertices.
Are there positive integers $n,c\in\mathbb{N}$ with ...
3
votes
1answer
60 views
variant of Motzkin-Rabin Theorem
The Motzkin-Rabin Theorem says:
If $A$ and $B$ are finite disjoint sets of points in the plane and $A \cup B$ is noncollinear, then there exists a line that contains at least two points from one of ...
4
votes
0answers
78 views
Ref. request: Enumerating elements of Bruhat cells
Given a field $F$ and a natural number $n$, let $B$ be the group of lower triangular, invertible $n \times n$ matrices over $F$. Then
$$GL_n(F) = \biguplus_{\pi \in S_n} B \pi B,$$
where we embed the ...
2
votes
1answer
134 views
How to estimate a summation?
For $v, w \in \{0,1\}^n$, denote $v w = (v_1 w_1, \ldots, v_n w_n)$ and $|v|=\sum_{i} v_i$.
Let $v_1, v_2 \in \{0,1\}^n$ and
\begin{align*}
f(x_1, x_2) = \sum_{d=0}^{|v_1 v_2|} \frac{1}{2^{|v_1|+|...
4
votes
1answer
140 views
A set-family game
Two players, Green and Red, play a zero-sum game. It is parametrized by two integers $n\geq 0, k\geq 0$, and a finite family $F$ of sets of size $n$ (each set may appear multiple times in $F$).
Each ...
3
votes
0answers
109 views
How to compute the asymptotic of a summation which involves binomial coefficients?
Let $v_1,v_2 \in \{0,1\}^n$. Denote $v_1v_2=((v_1)_1 (v_2)_1, \ldots, (v_1)_n (v_2)_n)$ and $|v|=\sum v_{i}$.
\begin{align}
{\scriptsize
f(v_1, v_2) = \sum_{x_1=0}^{|v_1|} \sum_{x_2=0}^{|v_2|} \sum_{d=...
2
votes
0answers
73 views
Largest number of sets $k$ among given $m$ sets that give union size lower than a given bound
Given $m$ sets $S_1, S_2, \dots, S_m$ and a bound $b$, find as many sets as possible among $m$ sets, says $S_{i_i}, S_{i_2}, \dots, S_{i_k}$ such that
$$\big| S_{i_i} \cup S_{i_2} \cup \cdots \cup S_{...
4
votes
1answer
181 views
$Pr(A>B)$, where $A$ and $B$ are sum of Bernoullies
Let $X= x_1 + x_2 + \ldots + x_m$, $Y=y_1 + y_2 + y_3 + \ldots + y_n$, and $Y' = y'_1 + y'_2 + \ldots + y'_n$, where
Each $x_i$ is a Bernoulli variable which takes value $1$ with probability $p_i>...
1
vote
0answers
48 views
Find a set of $N$ numbers s.t. all combination of $N$ on $X$ with repetition of $Y \leq X$ sum up to a different value
I'm new to this forum I normally post on stackOverflow.
My question is related to combinatorics and subsets.
Here is an example:
$N=6$, $X=5$, $Y=5$; the set $\{0,1,6,31,108,366 \}$ has the ...
1
vote
1answer
87 views
Perfect Difference Set of order 7^2-7+1=43
Problem: Let $a_1\dots a_k$ be integers in $Z_{n}$ such that $n=k(k-1)+1$ and that the list of differences $a_i-a_j \bmod n$ is unique to $i,j$ (for $i\neq j$). Such a set exists for $k=1\dots6,8$. No ...
1
vote
0answers
105 views
A partial ordering on $S_n$
Where $P$ and $Q$ are permutations in $S_n$, let's say $P<Q$ if $P$ is obtained from $Q$ by swapping two numbers which $Q$ places in the correct order. For example, if
$$Q=(1, 3, 6, 5, 4, 2)$$
$$P=...
7
votes
1answer
262 views
Higher dimensional scutoids?
The recent discovery of scutoids in biological structures is fascinating. Two scutoids are depicted below (from Scientists Have Discovered an Entirely New Shape, And It Was Hiding in Your Cells), each ...
3
votes
0answers
64 views
Hadwiger number of Erdös-Faber-Lovasz graphs
For any set $X$, let $[X]^2 = \big\{\{a,b\}:a,b \in X, a\neq b\big\}$.
We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdös-Faber-Lovasz (EFL-) graph if there are $n$ subsets $S_1,\...
0
votes
0answers
27 views
Partitioning ordered objects into sets so as to maximize isolated objects
I'll phrase this as how I thought of it:
Henri is a headmaster who is planning a school trip. He has ordered $n$ coaches to take his $m$ students to the trip destination, and the students have ...
32
votes
2answers
3k views
How to find Erdős' treasure trove?
The renowned mathematician, Paul Erdős, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...
2
votes
0answers
68 views
Width of symmetric groups
MSE crosspost
For any (finite) group $G$ its length $l(G)$ is the length of maximal chain of proper subgroups (it's known and pretty widely used invariant). But we can also define width function $w_G(...
3
votes
0answers
49 views
How rich is the class of vertex- and edge-transitive polytopes?
There are only a few regular polytopes (five in 3D, six in 4D, three in any dimension above). In contrast, the class of uniform polytopes becomes very rich with higher dimensions.
The class of vertex-...
3
votes
1answer
267 views
What is the consistency strength of non-existence of outer automorphisms of Calkin algebra?
The Calkin algebra $C(H)$ is the quotient of $B(H)$, the ring of bounded linear operators on a separable infinite-dimensional Hilbert space $H$, by the ideal $K(H)$ of compact operators.
In 1977, ...
2
votes
1answer
67 views
Generalization: (The “number” of) smaller sized clusters in large random binary matrices follow a descending order. Why?
This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix?
In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of ...
3
votes
2answers
72 views
Maximizing minimal distance between consecutive brushstrokes when painting a checkerboard torus
Suppose you have a 2-torus and you want to paint an $m\times n$ checkerboard pattern on it.
Every brushstroke could paint a single square.
How does one maximize the minimal distance between ...
