18 citations · 40 across the 27 of their papers we have counts for
33 papers
Optimally large cuts in both directions
Frederic Folz, Mykhaylo Tyomkyn
We prove that for every integer and all sufficiently large , every digraph with edges and minimum outdegree at least has a vertex bipartition for which each dire…
Linear matroid products: a synthetic approach
Mykhaylo Tyomkyn
The recently established duality between tensor, symmetric and exterior products of uniform matroids on the one hand, and abstract (bi-)rigidity matroids on the other hand, connect…
On plane rigidity matroids
Mykhaylo Tyomkyn
We establish new properties of matroids and matroidal families associated with rigidity in dimension , including the generic rigidity matroid family and Kalai's hy…
The Brown-Erdős-Sós conjecture in dense triple systems
Giovanne Santos, Mykhaylo Tyomkyn
The famous Brown-Erdős-Sós conjecture from 1973 states, in an equivalent form, that for any fixed and integer every sufficiently large linear -uniform hypergraph…
When does a tree activate the random graph?
Asaf Cohen Antonir, Yuval Peled, Asaf Shapira +2
Let and be two graphs. A spanning subgraph of is called weakly -saturated if one can add to the edges of in some order, so that whenever a ne…
Unavoidable subgraphs in digraphs with large out-degrees
Tomáš Hons, Tereza Klimošová, Gaurav Kucheriya +3
We ask the question, which oriented trees must be contained as subgraphs in every finite directed graph of sufficiently large minimum out-degree. We formulate the following sim…
Two-block paths in oriented graphs of large semidegree
Irena Penev, S Taruni, Stéphan Thomassé +2
We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive i…
A note on the computational complexity of weak saturation
Martin Tancer, Mykhaylo Tyomkyn
We prove that determining the weak saturation number of a host graph with respect to a pattern graph is already a computationally hard problem when is the triangle. As…
On the Small Quasi-kernel conjecture
Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei +2
An independent vertex subset of the directed graph is a kernel if the set of out-neighbors of is . An independent vertex subset of is a quasi-k…
A new approach for the Brown-Erdos-Sos problem
Asaf Shapira, Mykhaylo Tyomkyn
The celebrated Brown-Erdős-Sós conjecture states that for every fixed , every -uniform hypergraph with edges contains edges spanned by vertices. Up to this…
Monochromatic components with many edges
David Conlon, Sammy Luo, Mykhaylo Tyomkyn
Given an -edge-coloring of the complete graph , what is the largest number of edges in a monochromatic connected component? This natural question has only recently received…
Weakly saturated hypergraphs and a conjecture of Tuza
Asaf Shapira, Mykhaylo Tyomkyn
Given a fixed hypergraph , let $\mbox{wsat}(n,H)$ denote the smallest number of edges in an -vertex hypergraph , with the property that one can sequentially add the edges…
Weak saturation of multipartite hypergraphs
Denys Bulavka, Martin Tancer, Mykhaylo Tyomkyn
Given -uniform hypergraphs (-graphs) and , where is a spanning subgraph of , is called weakly -saturated in if the edges in ad…
Ramsey numbers of trails and circuits
David Conlon, Mykhaylo Tyomkyn
We show that every two-colouring of the edges of the complete graph contains a monochromatic trail or circuit of length at least , which is asymptotically bes…
Quasirandom Graphs and the Pantograph Equation
Asaf Shapira, Mykhaylo Tyomkyn
The pantograph differential equation and its solution, the deformed exponential function, are remarkable objects that appear in areas as diverse as combinatorics, number theory, st…
Repeated patterns in proper colourings
David Conlon, Mykhaylo Tyomkyn
For a fixed graph , what is the smallest number of colours such that there is a proper edge-colouring of the complete graph with colours containing no two vertex-d…
Many disjoint triangles in co-triangle-free graphs
Mykhaylo Tyomkyn
We prove that any -vertex graph whose complement is triangle-free contains edge-disjoint triangles. This is tight for the disjoint union of two cliques of order…
A Ramsey variant of the Brown-Erdős-Sós conjecture
Asaf Shapira, Mykhaylo Tyomkyn
An -uniform hypergraph (-graph for short) is called linear if every pair of vertices belong to at most one edge. A linear -graph is complete if every pair of vertices are…
Proof of the Brown-Erdős-Sós conjecture in groups
Rajko Nenadov, Benny Sudakov, Mykhaylo Tyomkyn
The conjecture of Brown, Erdős and Sós from 1973 states that, for any , if a -uniform hypergraph with vertices does not contain a set of vertices spanning…
Two Erdős--Hajnal-type Theorems in Hypergraphs
Michal Amir, Asaf Shapira, Mykhaylo Tyomkyn
The Erdős--Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph , have homogeneous sets of size significantl…
Edge-statistics on large graphs
Noga Alon, Dan Hefetz, Michael Krivelevich +1
The inducibility of a graph measures the maximum number of induced copies of a large graph can have. Generalizing this notion, we study how many induced subgraphs of fi…
Lagrangians of hypergraphs: The Frankl-Füredi conjecture holds almost everywhere
Mykhaylo Tyomkyn
Frankl and Füredi conjectured in 1989 that the maximum Lagrangian of all -uniform hypergraphs of fixed size is realised by the initial segment of the colexicographic order.…
On the inducibility of cycles
Dan Hefetz, Mykhaylo Tyomkyn
In 1975 Pippenger and Golumbic proved that any graph on vertices admits at most induced -cycles. This bound is larger by a multiplicative factor of than the…
A blow-up lemma for approximate decompositions
Jaehoon Kim, Daniela Kühn, Deryk Osthus +1
We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to longstanding decomposition problems. For instance, our result…