A problem of Erdős and Sós on 3-graphs

DOI10.1007/978-88-7642-475-5_1zbMATH Open1334.05092arXiv1303.7372OpenAlexW1488705378WikidataQ57601313 ScholiaQ57601313MaRDI QIDQ273102FDOQ273102

Authors: Roman Glebov, Daniel Král', Jan Volec 

Publication date: 21 April 2016

Published in: Israel Journal of Mathematics, The Seventh European Conference on Combinatorics, Graph Theory and Applications (Search for Journal in Brave)

Abstract: We show that for every positive epsilon there exist positive delta and n_0 such that every 3-uniform hypergraph on n>=n_0 vertices with the property that every k-vertex subset, where k>=delta*n, induces at least (1/4 + epsilon)*{k choose 3} edges, contains K4- as a subgraph, where K4- is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erdos and Sos. The constant 1/4 is the best possible.

Full work available at URL: https://arxiv.org/abs/1303.7372

Recommendations

• Two questions of Erdős on hypergraphs above the Turán threshold
• Constructing dense grid-free linear 3-graphs
• On a Turán problem in weakly quasirandom 3-uniform hypergraphs
• On the Erdős-Hajnal problem for 3-graphs

zbMATH Keywords

\(\delta\)-linear density\(r\)-uniform hypergraphedge densityspanned subgraphuniform hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Hypergraphs (05C65)

Cites Work

• CSDP, A C library for semidefinite programming
• Limits of dense graph sequences
• On 3-hypergraphs with forbidden 4-vertex configurations
• Hypergraphs do jump
• New Turán densities for 3-graphs
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• Flag algebras
• Title not available (Why is that?)
• On the structure of linear graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• On universality of graphs with uniformly distributed edges
• Some Ramsey-Turán type results for hypergraphs
• Mathematics of Ramsey theory. Collected papers of the Prague symposium on graph theory held in Prague, Czechoslovakia
• On Ramsey - Turan type theorems for hypergraphs
• On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
• Note on upper density of quasi-random hypergraphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Turán \(H\)-densities for 3-graphs
• A measure-theoretic approach to the theory of dense hypergraphs
• An extremal graph problem
• Title not available (Why is that?)
• Ramsey-Turán theory
• The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
• An exact result for 3-graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing

Uses Software

• CSDP
• SageMath
• Flagmatic

This page was built for publication: A problem of Erdős and Sós on 3-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q273102)