Some intersection theorems for structures (Q5903908): Difference between revisions

Let \({\mathcal S}\) be a structure and let \({\mathfrak G}\) be a family of substructures \({\mathcal S}_ i\) of \({\mathcal S}\), i.e. \({\mathfrak G}=\{{\mathcal S}_ 1,...,{\mathcal S}_ N\}\). Given a property \({\mathcal P}\) of structures, the family \({\mathfrak G}\) is called a P-intersection family if \({\mathcal S}_ i\cap {\mathcal S}_ j\) has the property \({\mathcal P}\) for all \(1\leq i<j\leq N\). In this paper three special structures \({\mathcal S}\) are considered and corresponding theorems about the maximum cardinality \({\mathcal N}\) of these intersection families are proved. Case 1: Let \({\mathcal S}\) be an arbitrary graph \(G=(V,E)\) with the girth r, which fulfils certain conditions, \({\mathcal S}_ i=G_ i\) are subgraphs of G and P is the property that \(G_ i\cap G_ j\) is a non-empty cycle. Then holds \(N\leq | E| -r+1.\) Also the special case of the equality is considered and already known results are obtained for \(G=K_ n.\) Case 2: Let \({\mathcal S}\) be a simple graph \(G=(V,E)\), \({\mathcal S}_ i=G_ i\) are different subgraphs of G and P is the property that \(G_ i\cap G_ j\) is an interval of G. Authors get a term for the maximum cardinality only depending on \(| E|.\) Case 3: Let \({\mathcal S}\) be the set of all permutations on the set \(\{\) 1,2,...,n\(\}\), \({\mathcal S}_ i=a_ i\) are elements of \({\mathcal S}\) and P is the property that any two of them have just one (empty or non-empty) maximal common interval. It is shown that in this case the maximum cardinality only depends on n and it holds \(f(n)=n^ 2-n,\) for \(n\geq 2\).