Some intersection theorems for structures (Q5903908): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5790167 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the maximum number of permutations with given maximal or minimal distance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on the intersection properties of subsets of integers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3890733 / rank | |||
Normal rank |
Revision as of 14:41, 19 June 2024
scientific article; zbMATH DE number 4093507
Language | Label | Description | Also known as |
---|---|---|---|
English | Some intersection theorems for structures |
scientific article; zbMATH DE number 4093507 |
Statements
Some intersection theorems for structures (English)
0 references
1988
0 references
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\).
0 references
intersection properties for special structures
0 references