Umeå University's logo

umu.sePublications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
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
Codegree thresholds for covering 3-uniform hypergraphs
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
2016 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 30, no 4, p. 1899-1917Article in journal (Refereed) Published
Abstract [en]

Given two 3-uniform hypergraphs F and G = (V, E), we say that G has an F-covering if we can cover V with copies of F. The minimum codegree of G is the largest integer d such that every pair of vertices from V is contained in at least d triples from E. Define c(2)(n, F) to be the largest minimum codegree among all n-vertex 3-graphs G that contain no F-covering. Determining c(2)(n, F) is a natural problem intermediate (but distinct) from the well-studied Turan problems and tiling problems. In this paper, we determine c(2)(n, K-4) (for n > 98) and the associated extremal configurations (for n > 998), where K-4 denotes the complete 3-graph on 4 vertices. We also obtain bounds on c(2)(n, F) which are apart by at most 2 in the cases where F is K-4(-) (K-4 with one edge removed), K-5(-), and the tight cycle C-5 on 5 vertices.

Place, publisher, year, edition, pages
2016. Vol. 30, no 4, p. 1899-1917
Keywords [en]
3-graphs, covering, codegree, extremal
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-130142DOI: 10.1137/15M1051452ISI: 000391960000001Scopus ID: 2-s2.0-85006998203OAI: oai:DiVA.org:umu-130142DiVA, id: diva2:1064523
Available from: 2017-01-12 Created: 2017-01-12 Last updated: 2023-03-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Falgas–Ravry, Victor

Search in DiVA

By author/editor
Falgas–Ravry, Victor
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
SIAM Journal on Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 592 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