umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • 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.
2016 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 30, no 4, 1899-1917 p.Article 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, 1899-1917 p.
Keyword [en]
3-graphs, covering, codegree, extremal
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-130142DOI: 10.1137/15M1051452ISI: 000391960000001OAI: oai:DiVA.org:umu-130142DiVA: diva2:1064523
Available from: 2017-01-12 Created: 2017-01-12 Last updated: 2017-02-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

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

Altmetric score

Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • 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