Transitive edge coloring of graphs and dimension of lattices
The author proves a strenghtening of \textit{A. Sali}'s conjecture [Eur. J. Comb. 17, 421-425 (1996; Zbl 0849.06007)]. The original conjecture says that the dimension of an \(n\)-element lattices is \(o(n)\). In fact, even the original conjecture spelled out in different setting, that involves the notion of \(t\)-configurations. Furthermore, for a set system \({\mathcal F}= \{F_i\}_{i=1}^n\) let \(\mathcal {M(F)}_2=\{F_i \cap F_j:\;i \neq j \}\). With that the main theorem has the form: For every fixed \(c>0\) and fixed positive integer \(t\) there exists \(n_0(c,t)\) such that if \(n >n_0\) then every system \({\mathcal F}\) satisfying \(|\mathcal {M(F)}_2|\leq cn\) contains a \(t\)-configuration. The proof also uses the notion of transitive edge coloring of graphs. An edge coloring is transitive if one can associate a set \(F_i\) to vertex \(i\) for all vertices such that for any pair of edges \(ij\) and \(kl\) their color is the same if and only if \(F_i \cap F_j = F_k \cap F_l\). With this set-up the main theorem turns out to be a generalization of the celebrated theorem of \textit{I. Z. Ruzsa} and \textit{E. Szemerédi} [Combinatorics, Keszthely 1976, Coll. Math. Soc. János Bolyai 18, 939-945 (1978; Zbl 0393.05031)].
scientific article; zbMATH DE number 1992710