Change search
ReferencesLink to record
Permanent link

Direct link
Turan H-densities for 3-graphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2012 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 19, no 3, P40- p.Article in journal (Refereed) Published
Abstract [en]

Given an r-graph H on h vertices, and a family F of forbidden subgraphs, we define ex H (n, F) to be the maximum number of induced copies of H in an F-free r-graph on n vertices. Then the Turan H-density of F is the limit pi(H)(F) = (lim)(n ->infinity) ex(H)(n, F)/((n)(h)) This generalises the notions of Turan-density (when H is an r-edge), and inducibility (when F is empty). Although problems of this kind have received some attention, very few results are known. We use Razborov's semi-definite method to investigate Turan H-densities for 3-graphs. In particular, we show that pi(-)(K4)(K-4) = 16/27, with Turans construction being optimal. We prove a result in a similar flavour for K-5 and make a general conjecture on the value of pi(Kt)-(K-t). We also establish that pi(4.2)(empty set) = 3/4, where 4: 2 denotes the 3-graph on 4 vertices with exactly 2 edges. The lower bound in this case comes from a random geometric construction strikingly different from previous known extremal examples in 3-graph theory. We give a number of other results and conjectures for 3-graphs, and in addition consider the inducibility of certain directed graphs. Let (S) over right arrow (k) be the out-star on k vertices; i.e. the star on k vertices with all k 1 edges oriented away from the centre. We show that pi((S) over right arrow3)(empty set) = 2 root 3 - 3, with an iterated blow-up construction being extremal. This is related to a conjecture of Mubayi and Rodl on the Turan density of the 3-graph C-5. We also determine pi((S) over right arrowk) (empty set) when k = 4, 5, and conjecture its value for general k.

Place, publisher, year, edition, pages
Newark: The Electronic Journal of Combinatorics , 2012. Vol. 19, no 3, P40- p.
Keyword [en]
Turan problems, extremal hypergraph theory, flag algebras
National Category
URN: urn:nbn:se:umu:diva-61562ISI: 000309522100001OAI: diva2:572611
Available from: 2012-11-28 Created: 2012-11-20 Last updated: 2012-11-28Bibliographically approved

Open Access in DiVA

fulltext(412 kB)138 downloads
File information
File name FULLTEXT02.pdfFile size 412 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Ravry, Victor Falgas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
The Electronic Journal of Combinatorics

Search outside of DiVA

GoogleGoogle Scholar
Total: 138 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 146 hits
ReferencesLink to record
Permanent link

Direct link