On a Degree Property of Cross-Intersecting Families |
| |
| Authors: | Gohar M. M. Kyureghyan |
| |
| Affiliation: | Universit?t Bielefeld, Fakult?t für Mathematik; Postfach 100131, 33501 Bielefeld, Germany; and Armenian National Academy of Sciences, Institute for Problems of Informatics and Automation; 375044 Yerevan, Armenia; E-mail: Gohar.Kyureghyan@Mathematik.Uni-Magdeburg.De, AM
|
| |
| Abstract: | Motivated by some applications in computational complexity, Razborov and Vereshchagin proved a degree bound for cross-intersecting families in [1]. We sharpen this result and show that our bound is best possible by constructing appropriate families. We also consider the case of cross-t-intersecting families. Received October 28, 1999 |
| |
| Keywords: | AMS Subject Classification (1991) Classes: 05D05, 68R05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
