## Abstract

A classical result in extremal graph theory is Mantel's Theorem, which states that every maximum triangle-free subgraph of K_{n} is bipartite. A sparse version of Mantel's Theorem is that, for sufficiently large p, every maximum triangle-free subgraph of G(n, p) is w.h.p. bipartite. Recently, DeMarco and Kahn proved this for p>K√logn/n for some constant K, and apart from the value of the constant this bound is best possible. We study an extremal problem of this type in random hypergraphs. Denote by F_{5}, which is sometimes called the generalized triangle, the 3-uniform hypergraph with vertex set (a,b,c,d,e) and edge set (abc,ade,bde). One of the first results in extremal hypergraph theory is by Frankl and Füredi, who proved that the maximum 3-uniform hypergraph on n vertices containing no copy of F_{5} is tripartite for n>3000. A natural question is for what p is every maximum F_{5}-free subhypergraph of G^{3}(n,p) w.h.p. tripartite. We show this holds for p>Klogn/n for some constant K and does not hold for p=0.1√logn/n.

Original language | English (US) |
---|---|

Pages (from-to) | 641-654 |

Number of pages | 14 |

Journal | Random Structures and Algorithms |

Volume | 48 |

Issue number | 4 |

DOIs | |

State | Published - Jul 1 2016 |

## Keywords

- Extremal problems
- Random hypergraphs
- Turán number

## ASJC Scopus subject areas

- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics