M. Stein

collaborators

7 papers

math.CO2026

Are trees really just butterflies in disguise?

Giovanne Santos, Maya Stein, Ella Williams

As a generalisation of the Erdős-Sós conjecture about graphs, Addario-Berry, Havet, Linhares Sales, Reed and Thomassé conjectured that every digraph on $n$ vertices with more than…

math.CO2026

The Erd\H os-Sós conjecture in dense graphs

Bruce Reed, Maya Stein

The Erd\H os--Sós conjecture states that every $n$ -vertex graph with more than $(k - 2) n /2$ edges contains every $k$ -vertex tree. We prove that for every $γ$ there is an $n_{0}$ such t…

math.CO2026

The extremal cases of the Erd\H os--Sós conjecture

Bruce Reed, Maya Stein

The Erd\H os--Sós conjecture states that every $n$ -vertex graph $G$ with more than $(k - 2) n /2$ edges contains every $k$ -vertex tree. We solve the extremal cases of this conjecture,…

math.CO2026

Semidegree threshold for spanning trees in oriented graphs

Pedro Araújo, Giovanne Santos, Maya Stein

We show that for all $γ > 0$ and $Δ \in N$ , there is some $n_{0}$ such that, if $n \geq n_{0}$ , then every oriented graph on $n$ vertices with minimum semidegree at least $(3/8…

math.CO2024

Packing large balanced trees into bipartite graphs

Cristina G. Fernandes, Tássio Naia, Giovanne Santos +1

We prove that for every $γ > 0$ there exists $n_{0} \in N$ such that for every $n \geq n_{0}$ any family of up to $⌊ n^{\frac{1}{2} + γ} ⌋$ trees having at most $(1-γ…

math.CO2024

A bounded diameter strengthening of Kőnig's Theorem

Louis DeBiasio, António Girão, Penny Haxell +1

K\H onig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at mos…