Source author record

Mykhaylo Tyomkyn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math-ph math.MP math.PR

Catalog footprint

Research overview

11works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

A new approach for the Brown-Erdos-Sos problem

The celebrated Brown-Erdős-Sós conjecture states that for every fixed $e$ , every $3$ -uniform hypergraph with $Ω(n^2)$ edges contains $e$ edges spanned by $e+3$ vertices. Up to this date all the approaches towards resolving this problem relied on highly involved applications of the hypergraph regularity method, and yet they supplied only approximate versions of the conjecture, producing $e$ edges spanned by $e+O(\log e/\log \log e)$ vertices. In this short paper we describe a completely different approach, which reduces the problem to a variant of another well-known conjecture in extremal graph theory. A resolution of the latter would resolve the Brown-Erdős-Sós conjecture up to an absolute additive constant.

preprint2022arXiv

Monochromatic components with many edges

Given an $r$ -edge-coloring of the complete graph $K_n$ , what is the largest number of edges in a monochromatic connected component? This natural question has only recently received the attention it deserves, with work by two disjoint subsets of the authors resolving it for the first two special cases, when $r = 2$ or $3$ . Here we introduce a general framework for studying this problem and apply it to fully resolve the $r = 4$ case, showing that any $4$ -edge-coloring of $K_n$ contains a monochromatic component with at least $\frac{1}{12}\binom{n}{2}$ edges, where the constant $\frac{1}{12}$ is optimal only when the coloring matches a certain construction of Gyárfás.

preprint2022arXiv

Ramsey numbers of trails and circuits

We show that every two-colouring of the edges of the complete graph $K_n$ contains a monochromatic trail or circuit of length at least $2n^2/9 +o(n^2)$ , which is asymptotically best possible.

preprint2020arXiv

Many disjoint triangles in co-triangle-free graphs

We prove that any $n$ -vertex graph whose complement is triangle-free contains $n^2/12-o(n^2)$ edge-disjoint triangles. This is tight for the disjoint union of two cliques of order $n/2$ . We also prove a corresponding stability theorem, that all large graphs attaining the above bound are close to being bipartite. Our results answer a question of Alon and Linial, and make progress on a conjecture of Erdős.

preprint2014arXiv

Strong Turán stability

We study the behaviour of $K_{r+1}$ -free graphs $G$ of almost extremal size, that is, typically, $e(G)=ex(n,K_{r+1})-O(n)$ . We show that such graphs must have a large amount of 'symmetry', in particular that all but very few vertices of $G$ must have twins. As a corollary, we obtain a new, short proof of a theorem of Simonovits on the structure of extremal graphs with $ω(G)\leq r$ and $χ(G)\geq k$ for fixed $k \geq r \geq 2$ .

preprint2012arXiv

A Turan-type problem on distances in graphs

We suggest a new type of problem about distances in graphs and make several conjectures. As a first step towards proving them, we show that for sufficiently large values of n and k, a graph on n vertices that has no three vertices at pairwise distance k has at most (n-k+1)^2/4 pairs of vertices at distance k.

preprint2011arXiv

A note on the abelian sandpile in Z^d

We analyse the abelian sandpile model on $\mathbbm{Z}^d$ for the starting configuration of $n$ particles in the origin and $2d-2$ particles otherwise. We give a new short proof of the theorem of Fey, Levine and Peres \cite{FLP} that the radius of the toppled cluster of this configuration is $O(n^{1/d})$ .

preprint2010arXiv

An improved bound for the Manickam-Miklós-Singhi conjecture

We show that for $n>k(4e\log k)^k$ every set $\{x_1,..., x_n\}$ of $n$ real numbers with $\sum_{i=0}^{n}x_i \geq 0$ has at least $\binom{n-1}{k-1}$ $k$ -element subsets of a non-negative sum. This is a substantial improvement on the best previously known bound of $n>(k-1)(k^k+k^2)+k$ , proved by Manickam and Miklós \cite{MM} in 1987.

preprint2010arXiv

Completing Partial Packings of Bipartite Graphs

Given a bipartite graph $H$ and an integer $n$ , let $f(n;H)$ be the smallest integer such that, any set of edge disjoint copies of $H$ on $n$ vertices, can be extended to an $H$ -design on at most $n+f(n;H)$ vertices. We establish tight bounds for the growth of $f(n;H)$ as $n \rightarrow \infty$ . In particular, we prove the conjecture of Füredi and Lehel \cite{FuLe} that $f(n;H) = o(n)$ . This settles a long-standing open problem.

preprint2010arXiv

Walks and Paths in Trees

Recently Csikvári \cite{csik} proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend his theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negative. Finally we consider an analogous question for paths rather than walks.

preprint2008arXiv

A proof of the rooted tree alternative conjecture

Bonato and Tardif conjectured that the number of isomorphism classes of trees mutually embeddable with a given tree T is either 1 or infinite. We prove the analogue of their conjecture for rooted trees. We also discuss the original conjecture for locally finite trees and state some new conjectures.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Mykhaylo Tyomkyn

Research overview

Is this your work?

11 publications

A new approach for the Brown-Erdos-Sos problem

Monochromatic components with many edges

Ramsey numbers of trails and circuits

Many disjoint triangles in co-triangle-free graphs

Strong Turán stability

A Turan-type problem on distances in graphs

A note on the abelian sandpile in Z^d

An improved bound for the Manickam-Miklós-Singhi conjecture

Completing Partial Packings of Bipartite Graphs

Walks and Paths in Trees

A proof of the rooted tree alternative conjecture

See the researcher in context

Building this map preview