Compression and Erdős-Ko-Rado graphs (Q1779494): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q189742 |
||
Property / author | |||
Property / author: F. C. Holroyd / rank | |||
Revision as of 12:03, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Compression and Erdős-Ko-Rado graphs |
scientific article |
Statements
Compression and Erdős-Ko-Rado graphs (English)
0 references
1 June 2005
0 references
This paper deals with the following, rather general problem. Let \(G\) be a graph, \({\mathcal I}^{(r)}(G)\) denote its \(r\)-element independent sets, while \({\mathcal I}^{(r)}_v(G)\) denote those \(r\)-element independent sets which contain vertex \(v.\) A graph is called \(r\)-EKR if there is no bigger intersecting subfamily in \({\mathcal I}^{(r)}(G)\) than the maximum size \(| {\mathcal I}^{(r)}_v(G)| .\) The main question is to describe the \(r\)-EKR graphs. If \(G\) is an empty graph with \(n\) vertices, then to determine the biggest \(r\) such that \(G\) is \(r\)-EKR is the well-known Erdős-Ko-Rado problem. This paper, using a compression technique, shows that the disjoint union of at least \(r\) complete graphs (with order of at least 2 each) is \(r\)-EKR. It is also shown that the paths are \(r\)-EKR.
0 references
Erdős-Ko-Rado theorem
0 references