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 2024Show all

6 papers · 1 filter

cs.CC2024

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra

Grigorii Dakhno, Dmitry Gribanov, Nikita Kasianov +4

In our work, we consider the problem of computing a vector $x \in Z^{n}$ of minimum $∥ \cdot ∥_{p}$ -norm such that $a^{⊤} x \neq = a_{0}$ , for any vector $(a, a_{0})$ from a given subset of…

math.CO2024

Linear dependencies, polynomial factors in the Duke--Erd\H os forbidden sunflower problem

Andrey Kupavskii, Fedor Noskov

We call a family of $s$ sets ${F_{1}, \dots, F_{s}}$ a \textit{sunflower with $s$ petals} if, for any distinct $i, j \in [s]$ , one has $F_{i} \cap F_{j} = \cap_{u = 1}^{s} F_{u}$ . The set $…

math.CO2024

Intersection problems and a correlation inequality for integer sequences

Peter Frankl, Andrey Kupavskii

Let us consider a collection $G$ of codewords of length $n$ over an alphabet of size $s$ . Let $t_{1}, \dots, t_{s}$ be nonnegative integers. What is the maximum of $|\mathcal…

math.CO2024

Two questions on Kneser colorings

Eduard Inozemtsev, Andrey Kupavskii

In this paper, we investigate two questions on Kneser graphs $K G_{n, k}$ . First, we prove that the union of $s$ intersecting families in $(k [ n ])$ has size at most ${n\choose…

cs.CG2024

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers

Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii +4

We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant $ε \in (0, 1)$ , one could constru…

math.CO2024

Non-trivial $r$ -wise agreeing families

Peter Frankl, Andrey Kupavskii

A family of subsets of $[n]$ is $r$ -wise agreeing if for any $r$ sets from the family there is an element $x$ that is either contained in all or contained in none of the $r$ sets.…

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra

Linear dependencies, polynomial factors in the Duke--Erd\H os forbidden sunflower problem

Intersection problems and a correlation inequality for integer sequences

Two questions on Kneser colorings

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers

Non-trivial r-wise agreeing families

Non-trivial $r$ -wise agreeing families