multiplicative group . We say that two nonzero elements are equivalent if we have and for some . Consider a graph on the set of all equivalence classes , such that and are connected if and only if . One can verify that is well-defined and free of , and every vertex in has degree or . Hence we have the upper bound Norm graphs and projective norm graphs For sufficiently larger than , the above conjecture was verified by Kollár, Rónyai, and Szabó and Alon, Rónyai, and Szabó using the construction of norm graphs and projective norm graphs over finite fields. For , consider the norm graph NormGraphp,s with vertex set , such that every two vertices are connected if and only if , where is the norm map It is not hard to verify that the graph has vertices and at least edges. To see that this graph is -free, observe that any common neighbor of vertices must satisfy for all , which a system of equations that has at most solutions. The same result can be proved for all using the projective norm graph, a construction slightly stronger than the above. The projective norm graph ProjNormGraphp,s is the graph on vertex set , such that two vertices are adjacent if and only if , where is the norm map defined by . By a similar argument to the above, one can verify that it is a -free graph with edges. The above norm graph approach also gives tight lower bounds on for certain choices of . In particular, for , , and , we have In the case , consider the bipartite graph with bipartition , such that and . For and , let in if and only if , where is the norm map defined above. To see that is -free, consider tuples . Observe that if the tuples have a common neighbor, then the must be distinct. Using the same upper bound on he number of solutions to the system of equations, we know that these tuples have at most common neighbors. Clique partitions Using a related result on clique partition numbers, Alon, Mellinger, Mubayi and Verstraëte proved a tight lower bound on for arbitrary : if , then we have . For , we say that a collection of subsets is a clique partition of if form a partition of . Observe that for