Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2021 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, no 2, p. 175-199Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
Cambridges Institutes Press, 2021. Vol. 30, no 2, p. 175-199
National Category
Discrete Mathematics Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-187528DOI: 10.1017/S0963548320000061ISI: 000625213500002Scopus ID: 2-s2.0-85092279191OAI: oai:DiVA.org:umu-187528DiVA, id: diva2:1594366
Funder
Swedish Research Council, 2014-4897, 2016-03488Available from: 2021-09-15 Created: 2021-09-15 Last updated: 2021-09-15Bibliographically approved

Open Access in DiVA

fulltext(576 kB)434 downloads
File information
File name FULLTEXT01.pdfFile size 576 kBChecksum SHA-512
85cba1746035065a7c954373e3181dcb71998257e48b249706bd8475f1e07db5749e1657f581629f305876c4f765d152945dd66ce166caee8354ddb03b02141a
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Falgas-Ravry, VictorMarkström, Klas

Search in DiVA

By author/editor
Falgas-Ravry, VictorMarkström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Combinatorics, probability & computing
Discrete MathematicsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 436 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 574 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf