Compression and Erdős-Ko-Rado graphs (Q1779494): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q189742
Property / author
 
Property / author: F. C. Holroyd / rank
Normal 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
    0 references
    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

    Identifiers