Well, that's more of a regex question and not really graph / query realted. But here you go:
gremlin> g.inject(["john smith", "John Smith", "JOHN SMITH", "John", "Smith", "no match"]).unfold().is(Search.regex(".*ohn.*smi.*"))
==>john smith
gremlin> g.inject(["john smith", "John Smith", "JOHN SMITH", "John", "Smith", "no match"]).unfold().is(Search.regex("(?i).*ohn.*smi.*"))
==>john smith
==>John Smith
==>JOHN SMITH
gremlin> g.inject(["john smith", "John Smith", "JOHN SMITH", "John", "Smith", "no match"]).unfold().is(Search.regex("(?i).*(ohn|smi).*"))
==>john smith
==>John Smith
==>JOHN SMITH
==>John
==>Smith
gremlin>
Cheers,