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…

math.CO2024

Embedding Nearly Spanning Trees

Bruce Reed, Maya Stein

The Erdős-Sós Conjecture states that every graph with average degree exceeding $k - 1$ contains every tree with $k$ edges as a subgraph. We prove that there are $δ > 0$ and $k_0\in\mat…