Zobrazeno 1 - 10
of 335
pro vyhledávání: '"Kupavskii, Andrey"'
Autor:
Kupavskii, Andrey, Noskov, Fedor
We call a family of $s$ sets $\{F_1, \ldots, 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 $C = \cap_{u = 1}^s F_u$ is called the {\it core} of the sunflower. It
Externí odkaz:
http://arxiv.org/abs/2410.06156
Autor:
Frankl, Peter, Kupavskii, Andrey
Let us consider a collection $\mathcal G$ of codewords of length $n$ over an alphabet of size $s$. Let $t_1,\ldots, t_s$ be nonnegative integers. What is the maximum of $|\mathcal G|$ subject to the condition that any two codewords should have at lea
Externí odkaz:
http://arxiv.org/abs/2408.08221
Autor:
Inozemtsev, Eduard, Kupavskii, Andrey
In this paper, we investigate two questions on Kneser graphs $KG_{n,k}$. First, we prove that the union of $s$ non-trivial intersecting families in ${[n]\choose k}$ has size at most ${n\choose k}-{n-s\choose k}$ for all sufficiently large $n$ that sa
Externí odkaz:
http://arxiv.org/abs/2405.08797
Autor:
Kupavskii, Andrey
For any $\epsilon>0$ and $n>(1+\epsilon)t$, $n>n_0(\epsilon)$ we determine the size of the largest $t$-intersecting family of permutations, as well as give a sharp stability result. This resolves a conjecture of Ellis, Friedgut and Pilpel (2011) and
Externí odkaz:
http://arxiv.org/abs/2405.07843
Autor:
Kupavskii, Andrey
A covering number of a family is the size of the smallest set that intersects all sets from the family. In 1978 Frankl determined for $n\ge n_0(k)$ the largest intersecting family of $k$-element subsets of $[n]$ with covering number $3$. In this pape
Externí odkaz:
http://arxiv.org/abs/2405.02621
Autor:
Kupavskii, Andrey, Tsarev, Dmitry
Bohn, Faenza, Fiorini, Fisikopoulos, Macchia, and Pashkovich (2015) conjectured that 2-level polytopes cannot simultaneously have many vertices and many facets, namely, that the maximum of the product of the number of vertices and facets is attained
Externí odkaz:
http://arxiv.org/abs/2404.17933
Autor:
Frankl, Peter, Kupavskii, Andrey
A family of sets 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. The study of such families is motivated by questions in discrete optimization. In
Externí odkaz:
http://arxiv.org/abs/2404.14178
Autor:
Bhore, Sujoy, Keszegh, Balázs, Kupavskii, Andrey, Le, Hung, Louvet, Alexandre, Pálvölgyi, Dömötör, Tóth, Csaba D.
We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant $\epsilon\in (0,1)$, one could construct a $(2+\epsilon)$-spanner with $O(n\log(n))$ edges (SICOMP 20
Externí odkaz:
http://arxiv.org/abs/2404.05045
Autor:
Kupavskii, Andrey
A family $\mathcal C$ of sets is hereditary if whenever $A\in \mathcal C$ and $B\subset A$, we have $B\in \mathcal C$. Chv\'atal conjectured that the largest intersecting subfamily of a hereditary family is the family of all sets containing a fixed e
Externí odkaz:
http://arxiv.org/abs/2311.02246
We consider several basic questions on distributed routing in directed graphs with multiple additive costs, or metrics, and multiple constraints. Distributed routing in this sense is used in several protocols, such as IS-IS and OSPF. A practical appr
Externí odkaz:
http://arxiv.org/abs/2310.07350