On 3-Hypergraphs with Forbidden 4-Vertex Configurations | Zendy

Alexander Razborov | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On 3-Hypergraphs with Forbidden 4-Vertex Configurations

Author(s) -

Alexander Razborov

Publication year - 2010

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/090747476

Subject(s) - hypergraph , mathematics , combinatorics , vertex (graph theory) , graph , upper and lower bounds , discrete mathematics , cauchy distribution , mathematical analysis , statistics

Every 3-graph in which no four vertices are independent and no four vertices span precisely three edges must have edge density $\geq4/9(1-o(1))$. This bound is tight. The proof is a rather elaborate application of Cauchy-Schwarz-type arguments presented in the framework of flag algebras. We include further demonstrations of this method by re-proving a few known tight results about hypergraph Turán densities and significantly improving numerical bounds for several problems for which the exact value is not known yet.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research