|
 학 술 대 회 명 |
l Colloquium at Yonsei University |
|
| 강 연 주 제 |
l An Erdos--Ko--Rado Theorem for cross $t$-intersecting families |
|
| 발 표 년 도 |
l 2013 |
|
| 발 표 월 |
l 05 |
|
| 저 자 |
l Lee, Sang June |
|
| 개 최 국 가 |
l 대한민국 |
|
| 다운로드 |
l
 1363158445_0.53486.pdf
|
|
Abstract:
(Also, see the attached file.)
A central result in extremal set theory is the extit{ErdH os--Ko--Rado Theorem} (1961) which investigates the maximum size of families $mathcal{A} subset biom{[n]}{k}:={Ssubset [n] : |S|=k}$ such that for every choice of $A_1, A_2in mathcal{A}$ we have $|A_1cap A_2| geq t$.
Two families $mathcal{A}, mathcal{B}subset biom{[n]}{k}:={Ssubset [n] : |S|=k}$ are {em cross $t$-intersecting} if for every choice of subsets $A in mathcal{A}$ and $B in mathcal{B}$ we have $|A cap B| geq t$.
The following was conjectured as the cross $t$-intersecting version of
the ErdH os--Ko--Rado Theorem: For all $tgeq 1$, $kgeq t$ and $n geq (t+1)(k-t+1)$, the maximum value of $|mathcal{A}||mathcal{B}|$ for two cross $t$-intersecting families $mathcal{A}, mathcal{B} subset binom{[n]}{k}$ is $binom{n-t}{k-t}^2$.
In this talk we verify this for $t geq 14$, large enough $k$
(depending on $t$ and any $delta>0$), and $n geq (t+1+delta)k$. Note that this range of $n$ is arbitrarily close to $ngeq (t+1)(k-t+1)$ in the conjecture if $delta$ is small and $k$ is large. Our proofs make use of a {em weight} version of the problem and {em randomness}.
This is joint work with Peter Frankl, Norihide Tokushige, and Mark Siggers. |
|
|
|
|
|
|
Invited Talks
Home > Activities > Outputs > Invited Talks