Compression and Erdős-Ko-Rado graphs
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.
- A Group-Theoretic Setting for Some Intersecting Sperner Families
- A simple proof of the Erdős-Chao Ko-Rado theorem
- An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
- An Erdős-Ko-Rado theorem for integer sequences of given rank
- An Erdős-Ko-Rado theorem for signed sets
- An Erdős-Ko-Rado theorem for the subcubes of a cube
- An ordered version of the Erdős-Ko-Rado theorem
- Erdös–Ko–Rado Theorem—22 Years Later
- scientific article; zbMATH DE number 3461973 (Why is no real title available?)
- scientific article; zbMATH DE number 3472087 (Why is no real title available?)
- INTERSECTING FAMILIES OF SEPARATED SETS
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Intersection theorems for systems of finite vector spaces
- More on the Erdős-Ko-Rado theorem for integer sequences
- On the maximum number of permutations with given maximal or minimal distance
- The complete intersection theorem for systems of finite sets
- The Erdös-Ko-Rado Theorem for Integer Sequences
- A generalization of Talbot's theorem about King Arthur and his knights of the round table
- The Erdős-Ko-Rado properties of various graphs containing singletons
- The Erdős-Ko-Rado properties of set systems defined by double partitions
- Compressions, graphs, and hyperreflexivity
- Erdös-Ko-Rado theorems for a family of trees
- Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
- Graphs with the Erdős-Ko-Rado property
- An Erdős-Ko-Rado theorem for unions of length 2 paths
- Erdős-Ko-Rado theorems on the weak Bruhat lattice
- On stars in caterpillars and lobsters
- The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
- The maximum sum of sizes of cross-intersecting families of subsets of a set
- On intersecting families of independent sets in trees
- Cross-intersecting subfamilies of levels of hereditary families
- The EKR property for flag pure simplicial complexes without boundary
- A Deza-Frankl type theorem for set partitions
- The maximum product of sizes of cross-intersecting families
- Cross-intersecting non-empty uniform subfamilies of hereditary families
- Erdős-Ko-Rado theorems for chordal graphs and trees
- Erdős-Ko-Rado theorems for simplicial complexes
- Compressing Bounded Degree Graphs
- The maximum product of weights of cross-intersecting families
- Non-trivial intersecting uniform sub-families of hereditary families
- An analogue of the Erdős-Ko-Rado theorem for weak compositions
- A short proof of an Erdős-Ko-Rado theorem for compositions
- An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
- Erdös-Ko-Rado theorem for ladder graphs
- The number of s-separated k-sets in various circles
- A sharp bound for the product of weights of cross-intersecting families
- Erdős-Ko-Rado theorems of labeled sets
- Stars on trees
- A cross‐intersection theorem for subsets of a set
- On the Holroyd-Talbot conjecture for sparse graphs
- Very well-covered graphs with the Erdős-Ko-Rado property
- On the star of the family of independent sets in a graph
- Disk compression of k-mer sets
- Strict Erdős-Ko-Rado for simplicial complexes (extended abstract)
- Non-trivial intersecting and non-empty cross-intersecting families of independent sets in graphs
- Strongly intersecting integer partitions
- Graph compression and the zeros of polynomials
- A non-trivial intersection theorem for permutations with fixed number of cycles
This page was built for publication: Compression and Erdős-Ko-Rado graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1779494)
