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
Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.ORCID-id: 0000-0001-8631-4745
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2021 (Engelska)Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, nr 2, s. 175-199Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F, what is c(1)(n, F), the least integer d such that if G is an n-vertex 3-graph with minimum vertex-degree delta(1)(G) > d then every vertex of G is contained in a copy of F in G?

We asymptotically determine c(1)(n, F) when F is the generalized triangle K-4((3)), and we give close to optimal bounds in the case where F is the tetrahedron K-4((3)) (the complete 3-graph on 4 vertices).

This latter problem turns out to be a special instance of the following problem for graphs: Given an nvertex graph G with m> n(2)/4 edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case.

Ort, förlag, år, upplaga, sidor
Cambridges Institutes Press, 2021. Vol. 30, nr 2, s. 175-199
Nationell ämneskategori
Diskret matematik Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-187528DOI: 10.1017/S0963548320000061ISI: 000625213500002Scopus ID: 2-s2.0-85092279191OAI: oai:DiVA.org:umu-187528DiVA, id: diva2:1594366
Forskningsfinansiär
Vetenskapsrådet, 2014-4897, 2016-03488Tillgänglig från: 2021-09-15 Skapad: 2021-09-15 Senast uppdaterad: 2021-09-15Bibliografiskt granskad

Open Access i DiVA

fulltext(576 kB)314 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 576 kBChecksumma SHA-512
85cba1746035065a7c954373e3181dcb71998257e48b249706bd8475f1e07db5749e1657f581629f305876c4f765d152945dd66ce166caee8354ddb03b02141a
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Falgas-Ravry, VictorMarkström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Falgas-Ravry, VictorMarkström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Combinatorics, probability & computing
Diskret matematikDatavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 314 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: 341 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