Open Problem Garden

Conjecture   The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required?

Conjecture  

Skewes' number is not an integer.

Question   For every does there exists a such that every graph with average degree smaller than and girth at least has a matching-cut?