betaFeedback

WorksMathematics

Ore-degree conditions for matchings in uniform hypergraphs

Abstract

Let σr(H)σ_r(\mathcal{H}) be the minimum sum of vertex degrees over all nonedges of an rr-uniform hypergraph H\mathcal{H} on nn vertices. Balogh, Palmer and Raeisi conjectured that n>2rsn>2rs and σr(H)>r[(n−1r−1)−(n−sr−1)]σ_r(\mathcal{H})>r[\binom{n-1}{r-1}-\binom{n-s}{r-1}] imply the existence of a matching of size ss in H\mathcal{H}. We prove that, for every fixed r≥3r\ge3 and all sufficiently large ss, σr(H)>r[(n−1r−1)−(n−sr−1)]σ_r(\mathcal{H})>r[\binom{n-1}{r-1}-\binom{n-s}{r-1}] forces an ss-matching whenever n≥rs+⌊(r−1)r−1/rr−2⌋n\ge rs+\lfloor(r-1)^{r-1}/r^{r-2}\rfloor. A complete rr-graph on rs−1rs-1 vertices together with ⌊(r−1)r−1/rr−2⌋\lfloor(r-1)^{r-1}/r^{r-2}\rfloor isolated vertices shows that the vertex bound is sharp for all sufficiently large ss. By adding new vertices to H\mathcal{H}, retaining all its edges, and adding every rr-set containing at least one new vertex as an edge, we also deduce that n≥rs+Cn\ge rs+C suffices under the same degree condition for every s≥1s\ge1, where CC is a finite constant depending only on rr. For r=3r=3, we provide the explicit sufficient order n≥⌈(7s+11)/2⌉n\ge\lceil(7s+11)/2\rceil for s≥6s\ge6, together with bounds for 2≤s≤52\le s\le5, establishing the conjecture in this uniformity. For s=2s=2, we improve the known sufficient order 2r+22r+2 to 2r+12r+1 for every r≥3r\ge3 and show that this order is best possible.

Paper details

vlnc:W_nzx5fyvh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…