Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Turan H-densities for 3-graphs
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.ORCID-id: 0000-0001-8631-4745
2012 (Engelska)Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, nr 3, s. P40-Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Newark: The Electronic Journal of Combinatorics , 2012. Vol. 19, nr 3, s. P40-
Nyckelord [en]
Turan problems, extremal hypergraph theory, flag algebras
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-61562DOI: 10.37236/2733ISI: 000309522100001Scopus ID: 2-s2.0-84867445875OAI: oai:DiVA.org:umu-61562DiVA, id: diva2:572611
Tillgänglig från: 2012-11-28 Skapad: 2012-11-20 Senast uppdaterad: 2023-03-24Bibliografiskt granskad

Open Access i DiVA

fulltext(412 kB)406 nedladdningar
Filinformation
Filnamn FULLTEXT02.pdfFilstorlek 412 kBChecksumma SHA-512
f18597d2fe6acb4b8fc6c8275a0b8ffb34e6588fa3ac02bfab1b4fa8fa858156b0fd4c7ca529bfa7b8e4bf15f45e026038c084fc1eb45ad9588d2e19cd79488a
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Ravry, Victor Falgas

Sök vidare i DiVA

Av författaren/redaktören
Ravry, Victor Falgas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
The Electronic Journal of Combinatorics
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 413 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 892 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf