1
$\begingroup$

Sorry to bother again with my misunderstandings, but I encountered yet again an issue with the topic of coloring in graphs and again I require some help to deal with this exercise:

Let $\mathbb{F}$ be a field of characteristic not equal to 2. A 3-uniform hypergraph is a pair (V, E) with V a finite set and E a collection of subsets of V of size 3. We call a 3-uniform hypergraph H = (V, E), 2- colourable if there exists a map χ : V → {−1, 1} such that no e ∈ E is monochromatic (here a hyperedge e = {v1, v2, v3} ∈ E is called monochromatic if all vi receive the same colour.) We need to show that a 3-uniform hypergraph H = (V, E) is not 2-colourable if and only if the polynomial

$\prod_{e\in E} \bigg(\sum_{v \in e} (x_v)\bigg)^2 - 9$

lies in the ideal generated by the polynomials $\{x_v^2 -1| v ∈ V\}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.