D. Cherkashin

activity

20112026

most citedAbout maximal number of edges in hypergraph-clique with chromatic number 3

3 citations · 7 across the 34 of their papers we have counts for

collaborators

Showing math.COShow all

30 papers · 1 filter

math.CO2026

A short proof of Oblakov's theorem

Danila Cherkashin

We give a short proof that for a given planar set of terminals $P$ there is at most one locally minimal tree with prescribed directions at $P$ (i.e. two locally minimal trees canno…

math.CO2026

On uniform eventowns

Danila Cherkashin, Pavel Prozorov

Suppose that $n = 2 m$ , $k = 2 t$ and $n > 10 k^{7}$ . We show that if a family $F$ of $k$ -subsets of an $n$ -set has only even pairwise intersections then $|\mathcal F| \leq \binom…

math.CO2026

Short proofs of three combinatorial results in the Johnson scheme

Danila Cherkashin, Yakov Shubin

In this note, we give short proofs of three theorems concerning extremal problems in the Johnson scheme, or, in other terminology, on $(n, k, L)$ -systems. The main result is a proof…

math.CO2025

On the chromatic numbers of Johnson type graphs

Danila Cherkashin

A Johnson type graph $J_{\pm} (n, k, t)$ is a graph whose vertex set consists of vectors from ${- 1, 0, 1}^{n}$ of the length $k$ and edges connect vertices with scalar product $t…

math.CO2024

The number of trees in distance-hereditary graphs and their friends

Danila Cherkashin, Pavel Prozorov

Counting the number of spanning trees in specific classes of graphs has attracted increasing attention in recent years. In this note, we present unified proofs and generalizations…

math.CO2024★ 1 cited

On set systems without singleton intersections

Danila Cherkashin

Consider a family $F$ of $k$ -subsets of an ambient $(k^{2} - k + 1)$ -set such that no pair of $k$ -subsets in $F$ intersects in exactly one element. In this short note…

math.CO2023

The kissing number in 48 dimensions for codes with certain forbidden distances is 52 416 000

Peter Boyvalenkov, Danila Cherkashin

We prove that the kissing number in 48 dimensions among antipodal spherical codes with certain forbidden inner products is 52\,416\,000. Constructions of attaining codes as kissing…

math.CO2023

On stability of weighted spanning tree degree enumerators

Danila Cherkashin, Pavel Prozorov

Our previous paper shows that the (vertex) spanning tree degree enumerator polynomial of a connected graph $G$ is a real stable polynomial (id est is non-zero if all variables have…

math.CO2023

On small non-uniform hypergraphs without property B

Danila Cherkashin

For a given hypergraph $H = (V, E)$ consider the sum $q (H)$ of $2^{- ∣ e ∣}$ over $e \in E$ . Consider the class of hypergraphs with the smallest edge of size $n$ and without a 2-colour…

math.CO2022

On stability of spanning tree degree enumerators

Danila Cherkashin, Fedor Petrov, Pavel Prozorov

We show that the spanning tree degree enumerator polynomial of a connected graph $G$ is a real stable polynomial if and only if $G$ is distance-hereditary.

math.CO2022

On the chromatic numbers of 3-dimensional slices

D. D. Cherkashin, A. J. Kanel-Belov, G. A. Strukov +1

We prove that for an arbitrary $ε > 0$ holds \[ χ(\mathbb{R}^3 \times [0,\varepsilon]^6) \geq 10, \] where $χ (M)$ stands for the chromatic number of an (infinite) graph w…

math.CO2022

Erd\H os--Hajnal problem for $H$ -free hypergraphs

Danila Cherkashin, Alexei Gordeev, Georgii Strukov

This paper deals with the minimum number $m_{H} (r)$ of edges in an $H$ -free graph with the chromatic number more than $r$ . We show how bounds on Ramsey and Turán numbers imply bounds…

math.CO2022

On the chromatic number of 2-dimensional spheres

Danila Cherkashin, Vsevolod Voronov

In 1976 Simmons conjectured that every coloring of a 2-dimensional sphere of radius strictly greater than $1/2$ in three colors has a couple of monochromatic points at the distance…

math.CO2022

Lov{á}sz theta approach to eventown problem

Mikhaylo Antipov, Danila Cherkashin

We apply the bound on independence number via Lov{á}sz theta function to eventown problem and its generalizations over $Z_{n}$ .

math.CO2021

On list chromatic numbers of 2-colorable hypergraphs

Danila Cherkashin, Alexey Gordeev

We give an upper bound on the list chromatic number of a 2-colorable hypergraph which generalizes the bound of Schauz on $k$ -partite $k$ -uniform hypergraphs. It makes sense for spa…

math.CO2020

On the minimal sum of edges in a signed edge-dominated graph

Danila Cherkashin, Pavel Prozorov

Let $G$ be a simple graph with $n$ vertices and $\pm 1$ -weights on edges. Suppose that for every edge $e$ the sum of edges adjacent to $e$ (including $e$ itself) is positive. Then…

math.CO2020

On minimizers of the maximal distance functional for a planar convex closed smooth curve

D. D. Cherkashin, A. S. Gordeev, G. A. Strukov +1

Fix a compact $M \subset R^{2}$ and $r > 0$ . A minimizer of the maximal distance functional is a connected set $Σ$ of the minimal length, such that \[ max_{y \in M} dist(y,Σ)…

math.CO2019★ 1 cited

Independence numbers of Johnson-type graphs

Danila Cherkashin, Sergei Kiselev

We consider a family of distance graphs in $R^{n}$ and find its independent numbers in some cases. Define graph $J_{\pm} (n, k, t)$ in the following way: the vertex set consist…

math.CO2019

On the Erd{\H o}s--Hajnal problem in the case of 3-graphs

Danila Cherkashin

Let $m (n, r)$ denote the minimal number of edges in an $n$ -uniform hypergraph which is not $r$ -colorable. For the broad history of the problem see [RaiSh]. It is known that for a fi…

math.CO2018

On a question of Sidorenko

D. Cherkashin, F. Petrov, V. Sokolov

For a positive integer $n > 1$ denote by $ω (n)$ the maximal possible number $k$ of different functions $f_{1}, \dots, f_{k} : Z / n Z \mapsto Z / n Z$ such that…

math.CO2018★ 2 cited

Regular behaviour of the maximal hypergraph chromatic number

Danila Cherkashin, Fedor Petrov

Let $m (n, r)$ denote the minimal number of edges in an $n$ -uniform hypergraph which is not $r$ -colorable. It is known that for a fixed $n$ one has \[ c_n r^n < m(n,r) < C_n r^n. \]…

math.CO2018

Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs

Jozsef Balogh, Danila Cherkashin, Sergei Kiselev

We suggest a new method on coloring generalized Kneser graphs based on hypergraphs with high discrepancy and small number of edges. The main result is providing a proper coloring o…

math.CO2017

Coloring cross-intersecting families

Danila Cherkashin

Intersecting and cross-intersecting families usually appear in extremal combinatorics in the vein of the Erd{\H o}s--Ko--Rado theorem. On the other hand, P.~Erd{\H o}s and L.~Lov{á…

math.CO2017

On small $n$ -uniform hypergraphs with positive discrepancy

Danila Cherkashin, Fedor Petrov

A two-coloring of the vertices $V$ of the hypergraph $H = (V, E)$ by red and blue has discrepancy $d$ if $d$ is the largest difference between the number of red and blue points in an…

A short proof of Oblakov's theorem

On uniform eventowns

Short proofs of three combinatorial results in the Johnson scheme

On the chromatic numbers of Johnson type graphs

The number of trees in distance-hereditary graphs and their friends

On set systems without singleton intersections

The kissing number in 48 dimensions for codes with certain forbidden distances is 52 416 000

On stability of weighted spanning tree degree enumerators

On small non-uniform hypergraphs without property B

On stability of spanning tree degree enumerators

On the chromatic numbers of 3-dimensional slices

Erd\H os--Hajnal problem for H-free hypergraphs

On the chromatic number of 2-dimensional spheres

Lov{á}sz theta approach to eventown problem

On list chromatic numbers of 2-colorable hypergraphs

On the minimal sum of edges in a signed edge-dominated graph

On minimizers of the maximal distance functional for a planar convex closed smooth curve

Independence numbers of Johnson-type graphs

On the Erd{\H o}s--Hajnal problem in the case of 3-graphs

On a question of Sidorenko

Regular behaviour of the maximal hypergraph chromatic number

Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs

Coloring cross-intersecting families

On small n-uniform hypergraphs with positive discrepancy

Erd\H os--Hajnal problem for $H$ -free hypergraphs

On small $n$ -uniform hypergraphs with positive discrepancy