학술
Settling the no-$(k+1)$-in-line problem when $k$ is not small
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.Abstract
What is the maximum number of points that can be selected from an $n\times n$ square lattice so that no $k+1$ of them are collinear?
This was asked more than $100$ years ago for $k=2$ and it remained wide open ever since.
In this paper, we prove the exact answer is $kn$, provided that $ n\ge k\ge C\log n$ for an absolute constant $C<20$.
The proof relies on carefully constructed block-uniform random bipartite graphs and concentration inequalities.
관련 뉴스
'research' 카테고리 뉴스
Correction: Pupillary dynamics during hands-off L2 driving and transitions of control under high cognitive load
PLOS ONE
Correction: Ornamental motifs and visual concerns: Exploring aesthetic pleasure and conservation intention in architectural heritage renovation
PLOS ONE
Correction: Who is disrupting whom? Examining the nighttime activity patterns of humans and their dogs
PLOS ONE