Zobrazeno 1 - 10
of 177
pro vyhledávání: '"Bukh, Boris"'
We consider two questions of Ruzsa on how the minimum size of an additive basis $B$ of a given set $A$ depends on the domain of $B$. To state these questions, for an abelian group $G$ and $A \subseteq D \subseteq G$ we write $\ell_D(A) \colon =\min \
Externí odkaz:
http://arxiv.org/abs/2409.07442
We study several basic problems about colouring the $p$-random subgraph $G_p$ of an arbitrary graph $G$, focusing primarily on the chromatic number and colouring number of $G_p$. In particular, we show that there exist infinitely many $k$-regular gra
Externí odkaz:
http://arxiv.org/abs/2312.08340
Autor:
Bukh, Boris, Vasileuski, Alexey
Given finite sets $X_1,\dotsc,X_m$ in $\mathbb{R}^d$ (with $d$ fixed), we prove that there are respective subsets $Y_1,\dotsc,Y_m$ with $|Y_i|\ge \frac{1}{\operatorname{poly}(m)}|X_i|$ such that, for $y_1\in Y_1,\dotsc,y_m\in Y_m$, the orientations o
Externí odkaz:
http://arxiv.org/abs/2309.10731
Autor:
Bukh, Boris, Jeffs, R. Amzi
Any $n$-tuple of points in the plane can be moved to any other $n$-tuple by a continuous motion with at most $\binom{n}{3}$ intermediate changes of the order type. Even for tuples with the same order type, the cubic bound is sharp: there exist pairs
Externí odkaz:
http://arxiv.org/abs/2309.02588
Autor:
Bukh, Boris, Jeffs, R. Amzi
We show that every convex code realizable by compact sets in the plane admits a realization consisting of polygons, and analogously every open convex code in the plane can be realized by interiors of polygons. We give factorial-type bounds on the num
Externí odkaz:
http://arxiv.org/abs/2207.06290
Autor:
Bukh, Boris, Dong, Zichao
For a finite point set $P \subset \mathbb{R}^d$, denote by $\text{diam}(P)$ the ratio of the largest to the smallest distances between pairs of points in $P$. Let $c_{d, \alpha}(n)$ be the largest integer $c$ such that any $n$-point set $P \subset \m
Externí odkaz:
http://arxiv.org/abs/2204.02487
Autor:
Bukh, Boris, Jeffs, R. Amzi
For each fixed $d\ge 1$, we obtain asymptotic estimates for the number of $d$-representable simplicial complexes on $n$ vertices as a function of $n$. The case $d=1$ corresponds to counting interval graphs, and we obtain new results in this well-stud
Externí odkaz:
http://arxiv.org/abs/2203.12063
In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. (*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced b
Externí odkaz:
http://arxiv.org/abs/2111.05518
Autor:
Bukh, Boris, Chao, Ting-Wei
Publikováno v:
Discrete Analysis, 2021:26
A Kakeya set in $\mathbb{F}_q^n$ is a set containing a line in every direction. We show that every Kakeya set in $\mathbb{F}_q^n$ has density at least $1/2^{n-1}$, matching the construction by Dvir, Kopparty, Saraf and Sudan.
Comment: 9 pages, 1
Comment: 9 pages, 1
Externí odkaz:
http://arxiv.org/abs/2108.00074
Autor:
Bukh, Boris
The Tur\'an problem asks for the largest number of edges in an $n$-vertex graph not containing a fixed forbidden subgraph $F$. We construct a new family of graphs not containing $K_{s,t}$, for $t= C^s$, with $\Omega(n^{2-1/s})$ edges matching the upp
Externí odkaz:
http://arxiv.org/abs/2107.04167