Stack Exchange Network

Stack Exchange network consists of 174 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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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