Skip to main content
3 votes

Confusion about lower bounds and upper bounds in learning theory

I invariably run into this issue when I teach learning theory. Indeed, the common notation causes a lot of confusion and is logically flawed. To elaborate on Usul's comment. Upper bounds are of the ...
Aryeh's user avatar
  • 10.5k
1 vote

Upper Bound for distance-two chromatic number in terms of maximum degree

Let $\Delta$ denote the maximum degree of $G$. The bound $\Delta^2+1$ cannot be improved significantly. For instance, even for a colouring variant called 2-ranking (which is a generalisation of ...
Cyriac Antony's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible