The Hardness of 3Uniform Hypergraph Coloring We prove that coloring a 3uniform 2colorable hypergraph with c colors is NPhard for any constant c. The best known algorithm 20 colors such a graph using O(n15) colors. Our result immediately implies that for any constants k xe2x89xa5 3 and c2 u003e c1 u003e 1, coloring a kuniform c1colorable hypergraph with c2 colors is NPhard; the case k  2, however, remains wide open.This is the first hardness result for approximatelycoloring a 3uniform hypergraph that is colorable with a constant number of colors. For k xe2x89xa5 4 such a result has been shown by 14, who also discussed the inherent difference between the k  3 case and k xe2x89xa5 4.Our proof presents a new connection between the LongCode and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph 19,22 and the Schrijver graph 26. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has xe2x80x98manyxe2x80x99 nonmonochromatic edges.

Extremal Problems for tPartite and tColorable Hypergraphs Fix integers t ge r ge 2 and an runiform hypergraph F. We prove that the maximum number of edges in a tpartite runiform hypergraph on n vertices that contains no copy of F is c_t, Fn choose r o(nr), where c_t, F can be determined by a finite computation.   We explicitly define a sequence F_1, F_2, ldots of runiform hypergraphs, and prove that the maximum number of edges in a tchromatic runiform hypergraph on n vertices containing no copy of F_i is alpha_t,r,in choose r o(nr), where alpha_t,r,i can be determined by a finite computation for each ige 1. In several cases, alpha_t,r,i is irrational. The main tool used in the proofs is the Lagrangian of a hypergraph.