KIAS Workshop on Combinatorics
On Combinatorial problems of Erd?s
SPEAKER | Younjin Kim
INSTITUTE | KAIST
DATE | June 1(Sat), 2013
TIME | 11:00
PLACE | Conference room 1503, KIAS
ABSTRACT | For a property ッ and a family of sets F, let f(F,ッ) be the size of the largest subfamily of F having property ッ. For a positive integer m, let f(m,ッ) be the minimum of f(F,ッ) over all families of size m. In 1972, Erd?s and Shelah also considered ッ to be the property that no four distinct sets satisfy F1○F2=F3 and F1○F2=F4. Such families are called B2-free. Erd?s and Shelah gave an example showing f(m,B2-free)?(3/2)m2/3 and they also conjectured f(m,B2-free)>c2m2/3. We verify a conjecture of Erd?s and Shelah from 1972. In1964, Erd?s, Hajnal, and Moon introduced the following problem: get the minimum size of a graph G such that G does not contain F as a subgraph but the addition of any new edge creates at least one copy of F in G. This minimum is called the saturation number of F. We obtain the saturation number of Ck, where Ck is a cycle with length k.