Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Theorem 1.2 of the paper: if t<n/(3k2)t<n/(3k^2), every kk-uniform hypergraph on nn vertices with no tt pairwise disjoint edges has at most (nk)−(n−t+1k)\binom nk-\binom{n-t+1}{k} edges. In the notation of Problem 1020, with rr for the uniformity and kk for the forbidden number of disjoint edges,

f(n;r,k)=(nr)−(n−k+1r)(n>3r2k),f(n;r,k)=\binom nr-\binom{n-k+1}{r}\qquad(n>3r^2k),

the conjectured value in that range, the covering family attaining it. The proof uses the shifting method and passes through an asymptotic form of a rainbow-matching strengthening of the conjecture (the paper's Conjecture 1.3), which it also proves in full for t<n/(3k2)t<n/(3k^2). The paper is H. Huang, P.-S. Loh and B. Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21 (2012), 442–450, carded at The size of a hypergraph and its matching number.

Covers. The range n>3r2kn>3r^2k, which the site records as n≥3kr2n\ge3kr^2. It improves the order r3kr^3k of Bollobás, Daykin and Erdős 1976 and was improved in turn, to n>2r2(k−1)/log⁡rn>2r^2(k-1)/\log r on Frankl, Łuczak and Mieczkowska 2012 and to order rkrk on Frankl 2013.

Depends on. No page of this wiki.

Acceptance. Refereed: the paper appeared in Combinatorics, Probability and Computing 21 (2012), no. 3, 442–450, after its first posting as arXiv:1107.5544 on 2011-07-27. The site labels the problem FALSIFIABLE, an open label, so its commentary, which credits the range to the paper as [HLS12], is not acceptance and no reviewed is listed. Nothing here rests on this project's own review.