This came up once before already. I don’t know if @Datseris figured out the solution.
But yes, the problem is that the Python version on Travis is like ~2.7.3 or something, whereas MkDocs 1.0 needs at least 2.7.9, so it installs an older MkDocs. However, the latest mkdocs-material needs MkDocs 1.0., so it fails to install All in all, it looks like pip just spectacularly fails to resolve versions here.
Specifying the versions of MkDocs and mkdocs-material by hand might work. You could try passing
deps = Deps.pip("mkdocs==0.17.5", "mkdocs-material==2.9.4" ,"python-markdown-math", "pygments", "pymdown-extensions")