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
Applications of the semi-definite method to the Turan density problem for 3-graphs
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.ORCID-id: 0000-0001-8631-4745
Univ London, Sch Elect Engn & Comp Sci, London E1 4NS, England.
2013 (Engelska)Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, nr 1, s. 21-54Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper, we prove several new Turan density results for 3-graphs with independent neighbourhoods. We show: pi(K-4, C-5, F-3,F-2) = 12/49, pi(K-4, F-3,F-2) = 5/18 and pi(J(4), F-3,F-2) = pi(J(5), F-3,F-2) = 3/8, where J(t) is the 3-graph consisting of a single vertex x together with a disjoint set A of size t and all (vertical bar A vertical bar 2) 3-edges containing x. We also prove two Turan density results where we forbid certain induced subgraphs: pi(F-3,F-2, induced K-4(-)) = 3/8 and pi(K-5, 5-set spanning exactly 8 edges) = 3/4. The latter result is an analogue for K-5 of Razborov's result that pi(K-4, 4-set spanning exactly 1 edge) = 5/9. We give several new constructions, conjectures and bounds for Turan densities of 3-graphs which should be of interest to researchers in the area. Our main tool is 'Flagmatic', an implementation of Razborov's semi-definite method, which we are making publicly available. In a bid to make the power of Razborov's method more widely accessible, we have tried to make Flagmatic as user-friendly as possible, hoping to remove thereby the major hurdle that needs to be cleared before using the semi-definite method. Finally, we spend some time reflecting on the limitations of our approach, and in particular on which problems we may be unable to solve. Our discussion of the 'complexity barrier' for the semi-definite method may be of general interest.

Ort, förlag, år, upplaga, sidor
NEW YORK, NY, USA: Cambridge University Press, 2013. Vol. 22, nr 1, s. 21-54
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-63752DOI: 10.1017/S0963548312000508ISI: 000312036300003Scopus ID: 2-s2.0-84870896020OAI: oai:DiVA.org:umu-63752DiVA, id: diva2:585610
Tillgänglig från: 2013-01-10 Skapad: 2013-01-07 Senast uppdaterad: 2023-03-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Falgas-Ravry, Victor

Sök vidare i DiVA

Av författaren/redaktören
Falgas-Ravry, Victor
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Combinatorics, probability & computing
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 646 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