TY - JOUR

T1 - Norm-Graphs

T2 - Variations and Applications

AU - Alon, Noga

AU - Rónyai, Lajos

AU - Szabó, Tibor

N1 - Funding Information:
We describe several variants of the norm-graphs introduced by Kollar, Ronyai, and Szabo and study some of their extremal properties. Using these variants we construct, for infinitely many values of n, a graph on n vertices with more than 21n5 3 edges, containing no copy of K3,3, thus slightly improving an old construction of Brown. We also prove that the maximum number of vertices in a complete graph whose edges can be colored by k colors with no monochromatic copy of K3,3is (1+o(1)) k3. This answers a question of Chung and Graham. In addition we prove that for every fixed t, there is a family of subsets of an n element set whose so-called dual shatter function is O(mt) and whose discrepancy is 0(n1 2&1 2t - log n). This settles a problem of Matousek. ν 1999 Academic Press * Research supported in part by a State of New Jersey grant, by a U.S.A. Israeli BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. -Research supported in part by OTKA Grants 016503, 016524, NWO-OTKA Grant 048.011.002, MKM Grant FKFP 0612 1997, and EC Grant ALTEC KIT. Research supported in part by the Alfred P. Sloan Foundation Grant 96-6-2 and the state of New Jersey.

PY - 1999/7

Y1 - 1999/7

N2 - We describe several variants of the norm-graphs introduced by Kollár, Rónyai, and Szabó and study some of their extremal properties. Using these variants we construct, for infinitely many values of n, a graph on n vertices with more than 12n5/3 edges, containing no copy of K3, 3, thus slightly improving an old construction of Brown. We also prove that the maximum number of vertices in a complete graph whose edges can be colored by k colors with no monochromatic copy of K3, 3 is (1+o(1))k3. This answers a question of Chung and Graham. In addition we prove that for every fixed t, there is a family of subsets of an n element set whose so-called dual shatter function is O(mt) and whose discrepancy is Ω(n1/2-1/2tlogn). This settles a problem of Matoušek.

AB - We describe several variants of the norm-graphs introduced by Kollár, Rónyai, and Szabó and study some of their extremal properties. Using these variants we construct, for infinitely many values of n, a graph on n vertices with more than 12n5/3 edges, containing no copy of K3, 3, thus slightly improving an old construction of Brown. We also prove that the maximum number of vertices in a complete graph whose edges can be colored by k colors with no monochromatic copy of K3, 3 is (1+o(1))k3. This answers a question of Chung and Graham. In addition we prove that for every fixed t, there is a family of subsets of an n element set whose so-called dual shatter function is O(mt) and whose discrepancy is Ω(n1/2-1/2tlogn). This settles a problem of Matoušek.

UR - http://www.scopus.com/inward/record.url?scp=0001100795&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001100795&partnerID=8YFLogxK

U2 - 10.1006/jctb.1999.1906

DO - 10.1006/jctb.1999.1906

M3 - Article

AN - SCOPUS:0001100795

VL - 76

SP - 280

EP - 290

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 2

ER -