6 papers
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…
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…
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 hypergr…
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…
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…