Umeå University's logo

umu.sePublications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • 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.ORCID iD: 0000-0001-8631-4745
2012 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, no 3, p. P40-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, p. P40-
Keywords [en]
Turan problems, extremal hypergraph theory, flag algebras
National Category
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-61562DOI: 10.37236/2733ISI: 000309522100001Scopus ID: 2-s2.0-84867445875OAI: oai:DiVA.org:umu-61562DiVA, id: diva2:572611
Available from: 2012-11-28 Created: 2012-11-20 Last updated: 2023-03-24Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full textScopus

Authority records

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: 583 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 1303 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • 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