Timeline for Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2015 at 5:54 | vote | accept | TCS-user-23 | ||
| Jun 10, 2015 at 12:45 | comment | added | Thomas Bloom | Corrected, thanks! (I also realised that technically the $k$ needs shifting up by 1, if we're considering a graph that is not $k$-colourable. | |
| Jun 10, 2015 at 12:45 | history | edited | Thomas Bloom | CC BY-SA 3.0 |
added 105 characters in body
|
| Jun 10, 2015 at 12:22 | comment | added | domotorp | Not like it would change the order of magnitude from $\Theta(k^3)$, but your upper bound is not optimal, it should be ${2k-1\choose 3}$. | |
| Jun 10, 2015 at 12:21 | history | edited | Thomas Bloom | CC BY-SA 3.0 |
More explicit bounds
|
| Jun 9, 2015 at 22:23 | history | answered | Thomas Bloom | CC BY-SA 3.0 |