8
votes
Accepted
Bound on the number of unit vectors with the same pairwise inner products
The upper bound is $n+1$, achieved by the vertices of a regular simplex with $0$ at the center. This is implicit in Iosef Pinelis answer, but let's state it explicitly. (It looks like the question may ...
- 153k
7
votes
Accepted
Large almost disjoint family on $\mathbb{N}$ with property $\mathbf{B}$
One of the standard examples of an almost disjoint family of cardinality $\mathfrak c$ is the set of paths through the complete binary tree $2^{<\omega}$ (identified with $\omega$ via your favorite ...
- 72.4k
7
votes
Closed form for binomial coefficient sum
A closed form is
\begin{equation*}
\sum_{i=j+1}^{n} \binom{\binom{i}{j}}{2}
=\sum_{k=1}^j \frac{1}{2}\binom{j}{k}\binom{j+k}{k}\binom{n+1}{j+k+1}.\tag{1}\label{474985_1}
\end{equation*}
For fixed $j$ ...
- 16.6k
5
votes
Bound on the number of unit vectors with the same pairwise inner products
Your post is unclear. In particular, what do you mean by "given a set of equiangular lines, how to extract the largest set of vectors with the same pairwise inner product?"? Extract from ...
- 121k
5
votes
Accepted
4-color theorem for hypergraphs
This follows from the case of graphs (i.e. hypergraphs where all sets have size $\leq 2$). As I explained in the comments above, Hadwiger's conjecture says that a graph with no $K_k$ minor is $(k-1)$-...
- 153k
5
votes
Accepted
Do there exist at least two sets whose union gives the universe in a certain intersection-closed family of sets?
No.
Let $U$ be the Fano plane, a set of $7$ elements. Let $\mathcal F$ consist of the complements of the lines in the Fano plane, each with multiplicity $1000000000000$, together with all their ...
- 141k
5
votes
Accepted
Number of planes generated by integer vectors
For $k=d-1$ this is a result of Bárány-Harcos-Pach-Tardos (2001). See Theorem 3 in the preprint version or the published version.
- 102k
5
votes
Counting a class of backtracking walks
Let's fix $n$ as suggested. As $t\in\{1,2,\ldots,n\}$ a fixed finite set, let's fix $t$ too. For a tree $T\ni n$, we denote $c_{\subseteq T}(\ell)$ the number of closed walks of length $2\ell$ in $T$, ...
- 1,459
4
votes
Accepted
An arrangement of hyperplanes
If you have an arbitrary system of linear equations and add
to it one equation, the dimension of the space of solutions
can decrease by at most 1. Do take any $d$ equations of your hyperplanes, order ...
- 90.1k
3
votes
Closed form for binomial coefficient sum
Equation \eqref{474985_1} from Ira Gessel's nice answer can be summed using Mathematica 14, and the result can be simplified to
\begin{align}
\sum_{i=j+1}^{n} \binom{\binom{i}{j}}{2}
&=\sum_{k=1}^...
- 3,013
3
votes
How do you traverse a rectangular grid of points while turning as little as possible?
Here is a very short elementary proof, but perhaps not completely trivial.
Assume there $n$ rows and $m$ columns. Represent the traversing path by a line, going from the center of one unit square to ...
- 5,103
1
vote
Square submatrix of a binary matrix with all columns having the same sum
Having $m$ large enough does not guarantee this.
Fix $n,k\in\mathbb N$: for your hypothesis to be possible, we need $k\leq n$. Obviously, the matrix has all ones if $k=n$, so focus on the nontrivial ...
- 527
1
vote
Accepted
Infinite complete minor in $\min,\max$-graph on $\mathbb{N}$
It seems to me that an infinite minor can be constructed as follows. For any $i\ge 1$, let $$V_i=\{(2i-1,2i)\}\cup\{(2i,j):j>2i\}.$$ The sets $V_i$ are all disjoint and each set $V_i$ is connected (...
- 935
1
vote
Accepted
Looking for another difficult case for the union-closed sets conjecture
Thanks to this answer to a related question, I was able to build an example where there is not even one couple of non-empty sets $A, B$ such that $A \in G$ or $B \in G$ for all $G \in \mathcal{G}$.
...
- 814
Only top scored, non community-wiki answers of a minimum length are eligible