Transitive edge coloring of graphs and dimension of lattices
type: Item
instance of: scholarly article
title: Transitive edge coloring of graphs and dimension of lattices
zbMATH Open document ID: 1026.05038
author: András Gyárfás
published in: Combinatorica
publication date: 2003-10-14T00:00:00Z
review text: 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)].
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1992710
zbMATH Keywords: transitive edge coloring
zbMATH Keywords: lattices
zbMATH Keywords: regularity lemma
MaRDI profile type: Publication
full work available at URL: s00493-002-0002-z
OpenAlex ID: W185188870
DOI: 10.1007/S00493-002-0002-Z
description: scientific article; zbMATH DE number 1992710