umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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 1097-1440, E-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
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-61562ISI: 000309522100001OAI: oai:DiVA.org:umu-61562DiVA: diva2:572611
Available from: 2012-11-28 Created: 2012-11-20 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

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

Authority records BETA

Ravry, Victor Falgas

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
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 176 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

urn-nbn

Altmetric score

urn-nbn
Total: 250 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf