| Full text | |
| Author(s): |
Han, Jie
;
Kohayakawa, Yoshiharu
Total Authors: 2
|
| Document type: | Journal article |
| Source: | Proceedings of the American Mathematical Society; v. 145, n. 1, p. 73-87, JAN 2017. |
| Web of Science Citations: | 4 |
| Abstract | |
The celebrated Erdos-Ko-Rado theorem determines the maximum size of a k-uniform intersecting family. The Hilton-Milner theorem determines the maximum size of a k-uniform intersecting family that is not a subfamily of the so-called Erdos-Ko-Rado family. In turn, it is natural to ask what the maximum size of an intersecting k-uniform family that is neither a subfamily of the Erdos-Ko-Rado family nor of the Hilton-Milner family is. For k >= 4, this was solved (implicitly) in the same paper by Hilton-Milner in 1967. We give a different and simpler proof, based on the shifting method, which allows us to solve all cases k >= 3 and characterize all extremal families achieving the extremal value. (AU) | |
| FAPESP's process: | 15/07869-8 - Perfect matchings and Tilings in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships abroad - Research Internship - Post-doctor |
| FAPESP's process: | 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat |
| Grantee: | Oswaldo Baffa Filho |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |