D. Zakharov

activity

20162021

collaborators

10 papers

cs.IT2021

On the trifference problem for linear codes

Cosmin Pohoata, Dmitriy Zakharov

We prove that perfect $3$ -hash linear codes in $F_{3}^{n}$ must have dimension at most $(\frac{1}{4} - ε) n$ for some absolute constant $ε > 0$ .

math.CO2021

Norm hypergraphs

Cosmin Pohoata, Dmitriy Zakharov

We introduce a high uniformity generalization of the so-called (projective) norm graphs of Alon, Kollár, Rónyai, and Szabó, and use it to show that $$\operatorname{ex}_{d}(n,K_{s_{…

math.CO2020

Random multilinear maps and the Erdős box problem

David Conlon, Cosmin Pohoata, Dmitriy Zakharov

By using random multilinear maps, we provide new lower bounds for the Erdős box problem, the problem of estimating the extremal number of the complete $d$ -partite $d$ -uniform hyper…

math.CO2020

The extremal number of surfaces

Andrey Kupavskii, Alexandr Polyanskii, István Tomon +1

In 1973, Brown, Erdős and Sós proved that if $H$ is a 3-uniform hypergraph on $n$ vertices which contains no triangulation of the sphere, then $H$ has at most $…

math.CO2020

Turán-type results for intersection graphs of boxes

István Tomon, Dmitriy Zakharov

In this short note, we prove the following analog of the Kővári-Sós-Turán theorem for intersection graphs of boxes. If $G$ is the intersection graph of $n$ axis-parallel boxes in $…

math.CO2020

Zero subsums in vector spaces over finite fields

Cosmin Pohoata, Dmitriy Zakharov

The Olson constant $O L (F_{p}^{d})$ represents the minimum positive integer $t$ with the property that every subset $A \subset F_{p}^{d}$ of cardinality $…

math.MG2019

The right acute angles problem?

Andrey Kupavskii, Dmitriy Zakharov

The Danzer--Grünbaum acute angles problem asks for the largest size of a set of points in $R^{d}$ that determines only acute angles. Recently, the problem was essentially s…

math.CO2018

Chromatic numbers of Kneser-type graphs

Dmitriy Zakharov

Let $G (n, r, s)$ be a graph whose vertices are all $r$ -element subsets of an $n$ -element set, in which two vertices are adjacent if they intersect in exactly $s$ elements. In this…

math.MG2017

Acute sets

D. Zakharov

A set of points in $R^{d}$ is acute, if any three points from this set form an acute angle. In this note we construct an acute set in $R^{d}$ of size at least $2^{d/2…

math.CO2016

Regular bipartite graphs and intersecting families

Andrey Kupavskii, Dmitriy Zakharov

In this paper we present a simple unifying approach to prove several statements about intersecting and cross-intersecting families, including the Erd\H os--Ko--Rado theorem, the Hi…