A. Kupavskii

activity

20132026

most citedDistance graphs with large chromatic number and arbitrary girth

15 citations · 149 across the 60 of their papers we have counts for

collaborators

Showing 2022Show all

8 papers · 1 filter

math.CO2022★ 1 cited

Cutting corners

Andrey Kupavskii, Arsenii Sagdeev, Dmitrii Zakharov

We say that a subset $M$ of $R^{n}$ is exponentially Ramsey if there are $ε > 0$ and $n_{0}$ such that $χ (R^{n}, M) \geq (1 + ε)^{n}$ for any $n > n_{0}$ , where $χ (R^{n}, M)$ stan…

math.CO2022

Octopuses in the Boolean cube: families with pairwise small intersections, part I

Andrey Kupavskii, Fedor Noskov

Let $F_{1}, \dots, F_{ℓ}$ be families of subsets of ${1, \dots, n}$ . Suppose that for distinct $k, k^{'}$ and arbitrary $F_1 \in \mathcal F_{k}, F_2 \in \mathcal…

math.CO2022

Erdős Matching Conjecture for almost perfect matchings

Dmitriy Kolupaev, Andrey Kupavskii

In 1965 Erdős asked, what is the largest size of a family of $k$ -element subsets of an $n$ -element set that does not have a matching of size $s + 1$ ? In this note, we improve upon a…

math.CO2022★ 1 cited

Spread approximations for forbidden intersections problems

Andrey Kupavskii, Dmitriy Zakharov

We develop a new approach to approximate families of sets, complementing the existing ` $Δ$ -system method' and `junta approximations method'. The approach, which we refer to as `spr…

math.CO2022★ 5 cited

Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings

Nóra Frankl, Andrey Kupavskii, Arsenii Sagdeev

In 2008, Schmidt and Tuller stated a conjecture concerning optimal packing and covering of integers by translates of a given three-point set. In this note, we confirm their conject…

cs.DS2022

Sketching Distances in Monotone Graph Classes

Louis Esperet, Nathaniel Harms, Andrey Kupavskii

We study the two-player communication problem of determining whether two vertices $x, y$ are nearby in a graph $G$ , with the goal of determining the graph structures that allow the…