Norm-graphs: Variations and applications (Q1306316)

In this paper, several variants of the norm-graphs introduced by \textit{J. Kollár}, \textit{L. Rónyai} and \textit{T. Szabó} [Combinatorica 16, No. 3, 399-406 (1996; Zbl 0858.05061)] have been described, and some of their extremal properties have been studied. Using these variants, the authors have constructed, for infinitely many values of \(n\), a graph on \(n\) vertices with more than \({1\over 2}n^{5/3}\) edges, containing no copy of \(K_{3,3}\). This slightly improves an old construction of \textit{W. G. Brown} [Can. Math. Bull. 9, 281-285 (1966; Zbl 0178.27302)]. Further, the authors also answer a question of \textit{F. Chung} and \textit{R. Graham} (1998) by proving that the maximum number of vertices in a complete graph whose edges can be colored by \(k\) colors with no monochromatic copy of \(K_{3,3}\) is \((1+o(1))k^3\). The authors also settle a problem of \textit{J. Matoušek} (1997) by proving that for every fixed \(t\), there is a family of subsets of an \(n\)-element set whose so-called dual shatter function is \(O(m^t)\) and whose discrepancy is \(\Omega(n^{1/2- 1/2t}\sqrt{\log n})\).