Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, nr 2, s. 175-199Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Cambridges Institutes Press, 2021. Vol. 30, nr 2, s. 175-199
HSV kategori
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
Swedish Research Council, 2014-4897, 2016-03488Tilgjengelig fra: 2021-09-15 Laget: 2021-09-15 Sist oppdatert: 2021-09-15bibliografisk kontrollert

Open Access i DiVA

fulltext(576 kB)435 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 576 kBChecksum SHA-512
85cba1746035065a7c954373e3181dcb71998257e48b249706bd8475f1e07db5749e1657f581629f305876c4f765d152945dd66ce166caee8354ddb03b02141a
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Person

Falgas-Ravry, VictorMarkström, Klas

Søk i DiVA

Av forfatter/redaktør
Falgas-Ravry, VictorMarkström, Klas
Av organisasjonen
I samme tidsskrift
Combinatorics, probability & computing

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 437 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 588 treff
RefereraExporteraLink to record
Permanent link

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