DISJOINT COLOR-AVOIDING TRIANGLES

摘要

A set of pairwise edge-disjoint triangles of an edge-colored K_n is r-color avoiding if it does not contain r monochromatic triangles, each having a different color. Let f_r(n) be the maximum integer so that in every edge coloring of K_n with r colors, there is a set of f_r(n) pairwise edge-disjoint triangles that is r-color avoiding. We prove that 0.1177n~2(1 - o(1)) ＜ f_2(n) ＜ 0.1424n~2(1 + o(1)). The proof of the lower bound uses probabilistic arguments, fractional relaxation and some packing theorems. We also prove that f_r(n)~2 ＜ 1/6(1 - 0.145~(r-1)) + o(1). In particular, for every r, if n is sufficiently large, there are edge colorings of K_n with r colors so that the removal of any o(n~2) members from any Steiner triple system does not turn it r-color avoiding.