Some intersection theorems for structures

Let S be a structure and let \({\mathfrak S}\) be a family of substructures \(S_ i\) of S, i.e. \({\mathfrak S}=\{S_ 1,...,S_ N\}.\) Given a property P of structures, the family \({\mathfrak S}\) is called a P-intersection family if \(S_ i\cap S_ j\) has the property P for all \(1\leq i<j\leq N\). In this paper three special structures S are considered and corresponding theorems about the maximum cardinality N of these intersection families are proved. Case 1: Let S be an arbitrary graph \(G=(V,E)\) with the girth r, which fulfills certain conditions, \(S_ i=G_ i\) are subgraphs of G and P is the property that \(G_ i\cap G_ j\) is a nonempty 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 S be a simple graph \(G=(V,E)\), \(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 S be the set of all permutations on the set \(\{\) 1,2,...,n\(\}\), \(S_ i=a_ i\) are elements of 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\).

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Some intersection theorems for structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5904022)