Linear Algebra Methods

Lecture Notes for CS477 combinatorics on 2025/05/26

组合中的线性代数方法

Maybe this link is useful: Linear Algebra Methods in Combinatorics

d维中每一对点距离为奇数，最大个数

n维点有2种距离，最大个数

d 维最大 joint 数

d维n条线，最大joint个数（要求joint必须是d个线性无关的线交点）

intuition：考虑 d 维中 $dk^{d-1}$ 条线，交点是一个点阵 $k^d$，因此 $\Omega(n^{\frac{d}{d-1}})$

先考虑三维空间，如果 $|J|=m\lt {d+3\choose3}$ 存在一个 d 次非平凡多项式 $P$ 使得 $J$ 在零点集中. ($\mathbb{R}^d[x_1,x_2,x_3]$ 有 ${d+3\choose3}$ 自由度)

Finite Kakeya conjecture

(to be completed)

• Combinatorics