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
Partite Turán-densities for complete r-uniform hypergraphs on r + 1 vertices
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark.
2021 (Engelska)Ingår i: Journal of Combinatorics, ISSN 2156-3527, E-ISSN 2150-959X, Vol. 12, nr 2, s. 235-245Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper we investigate density conditions for finding a complete r-uniform hypergraph K-(r+1((r)) on r + 1 vertices in an (r + 1)-partite r-uniform hypergraph G. First we prove an optimal condition in terms of the densities of the (r + 1) induced r-partite subgraphs of G. Second, we prove a version of this result where we assume that r-tuples of vertices in G have their neighbours evenly distributed in G. Third, we also prove a counting result for the minimum number of copies of K-r+1((r)) when G satisfies our density bound, and present some open problems.

A striking difference between the graph, r = 2, and the hypergraph, r >= 3, cases is that in the first case both the existence threshold and the counting function are non-linear in the involved densities, whereas for hypergraphs they are given by a linear function. Also, the smallest density of the r-partite parts needed to ensure the existence of a complete r-graph with (r + 1) vertices is equal to the golden ratio τ = 0.618 ... for r = 2, while it is r/r+1 for r >= 3.

Ort, förlag, år, upplaga, sidor
2021. Vol. 12, nr 2, s. 235-245
Nyckelord [en]
Turan problem, mulitpartite, hypergraph
Nationell ämneskategori
Datavetenskap (datalogi) Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-187144DOI: 10.4310/JOC.2021.v12.n2.a3ISI: 000675850800003Scopus ID: 2-s2.0-85149715846OAI: oai:DiVA.org:umu-187144DiVA, id: diva2:1595299
Forskningsfinansiär
Vetenskapsrådet, 2014-4897Tillgänglig från: 2021-09-17 Skapad: 2021-09-17 Senast uppdaterad: 2024-11-22Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Markström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Markström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Journal of Combinatorics
Datavetenskap (datalogi)Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

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