NumberDB$^\beta$ Advanced search Tags Tables Help Login
Core thresholds of random $k$-uniform hypergraphs
edit · history · discussion · files · long url · statistical mechanics combinatorics probability theory
Numbers
$k$
$r$ 
$c_{k,r}$
3
2:
0.8184691607613759831252558008733920329831175469613078626899018670427363129799913288253032902559241024
comment: The minimum is attained at $\lambda_{3,2}=1.25643120863$.
3
3:
1.552829939577520449289628025855559576466226931102107143431923294941745865086743479581879605638915296
comment: The minimum is attained at $\lambda_{3,3}=3.21356352022$.
3
4:
2.174492025941424869391681607777529981296692510852437938445923826603023521889889315816723323337233011
comment: The minimum is attained at $\lambda_{3,4}=4.92198184677$.
3
5:
2.746725876360039113130416440308124105078956249084493826526952096747076459967379033578663025474986972
comment: The minimum is attained at $\lambda_{3,5}=6.51559182610$.
3
6:
3.289353438262529065990607372942020043647007757434903533191272647567726361773864674923357626812904227
comment: The minimum is attained at $\lambda_{3,6}=8.03926382015$.
3
7:
3.811659455494417085555522830128696916112917803808867984101384829384625169196271993754301980604536139
comment: The minimum is attained at $\lambda_{3,7}=9.51446950888$.
3
8:
4.318881026235451476793863579986753320110057877177707070064109553971687356904083518911665008344646696
comment: The minimum is attained at $\lambda_{3,8}=10.9534607599$.
4
2:
0.7722798398025084362589115204423372898792246826090093125525747762969751339659248599750041805845882712
comment: The minimum is attained at $\lambda_{4,2}=1.90381369444$.
4
3:
1.333636524131221823346108686205322273982500971147818522739473250415324684238830997654475231493660276
comment: The minimum is attained at $\lambda_{4,3}=3.94343299161$.
4
4:
1.810866216223604532451731645558285634462684972524608841723989433689268749345701831877195667737549766
comment: The minimum is attained at $\lambda_{4,4}=5.71265568979$.
4
5:
2.249767571132481991709638861508802234314564776243344476987210437230900690326176824181016006625622472
comment: The minimum is attained at $\lambda_{4,5}=7.35623866257$.
4
6:
2.665443309491988286329405584588083271038586674935415032537130444469242191120402850927948734682144531
comment: The minimum is attained at $\lambda_{4,6}=8.92313354394$.
4
7:
3.065087688854232828458211511537655788872671761007110764367912775053342294964377581195879914938794698
comment: The minimum is attained at $\lambda_{4,7}=10.4368572894$.
4
8:
3.452794112705545007187502536436123720410625509582650523597094628904563951354985474250949879353686103
comment: The minimum is attained at $\lambda_{4,8}=11.9108548230$.
5
2:
0.7017802664845689682277622650333858599784179575686798819131925668319248298996566051224833271540303690
comment: The minimum is attained at $\lambda_{5,2}=2.33666298226$.
5
3:
1.157769111592034144785534421701714149624285699501978650307329571177868936379987496907591944662490478
comment: The minimum is attained at $\lambda_{5,3}=4.42996174117$.
5
4:
1.545698248311169033363806648229693853726840487272600228426957895950823957310733538471724861833145447
comment: The minimum is attained at $\lambda_{5,4}=6.23923309984$.
5
5:
1.902161098906697844463901493329974755347290910740029519133629954882903636663177533506188768271107303
comment: The minimum is attained at $\lambda_{5,5}=7.91593280893$.
5
6:
2.239456013729484270499941683141803895183583558676697356255912217478876041580987093913412290959850833
comment: The minimum is attained at $\lambda_{5,6}=9.51158154335$.
5
7:
2.563484703351145170531271291880132308341631280768257627623008954428977184818630169644474366505284613
comment: The minimum is attained at $\lambda_{5,7}=11.0509985031$.
5
8:
2.877618817118384091107445624224423733517247635212578007863145953140517934751815256907382611607918825
comment: The minimum is attained at $\lambda_{5,8}=12.5483941469$.
6
2:
0.6370811272741537470169571390872661686272612023764815932492554704257887151893038461006142694589183687
comment: The minimum is attained at $\lambda_{6,2}=2.66039905846$.
6
3:
1.021630465700997361252645019118980013540627214643065296611336888758312241738087128561996576729456742
comment: The minimum is attained at $\lambda_{6,3}=4.79292235073$.
6
4:
1.348789262865272000557080725532970752330039767756719755085559124914303147409895217157320026836102013
comment: The minimum is attained at $\lambda_{6,4}=6.63169204498$.
6
5:
1.649197026930156589511430268444214242708074598227568788124272721020979019065493394088646901794728082
comment: The minimum is attained at $\lambda_{6,5}=8.33288506055$.
6
6:
1.933257342959889197324835593611747065037058762239342404489153463600401378581927435996837885285738290
comment: The minimum is attained at $\lambda_{6,6}=9.94985603528$.
6
7:
2.205984437250255864783261016352820767982034629709665944478125460661021645004428007126829091496445881
comment: The minimum is attained at $\lambda_{6,7}=11.5083609231$.
6
8:
2.470250087459505507006904841784472958943600963491876447096720438134431752956709585244401215868062281
comment: The minimum is attained at $\lambda_{6,8}=13.0231637402$.
7
2:
0.5817751769996016417083894367734361074936598379037227464768781680603713297266039299226379201536631650
comment: The minimum is attained at $\lambda_{7,2}=2.91830047578$.
7
3:
0.9145757127183174997611762062016991315587289695404211627508102149187495671320284348144561994080992393
comment: The minimum is attained at $\lambda_{7,3}=5.08145916090$.
7
4:
1.197661190661175903943262796385937954453784871856627438264935553353692718107690440644729156659340269
comment: The minimum is attained at $\lambda_{7,4}=6.94340314951$.
7
5:
1.457448079251875166840493940526802318828436619832708614292572019684886849277501237082915058467796129
comment: The minimum is attained at $\lambda_{7,5}=8.66389743514$.
7
6:
1.702965796976139420316215760710583117342187550735278921583421222618056468674413907356514417681843298
comment: The minimum is attained at $\lambda_{7,6}=10.2977037095$.
7
7:
1.938579232167352466373087015440132523356416789370544201288129938864508213890710497740818366894480767
comment: The minimum is attained at $\lambda_{7,7}=11.8713007021$.
7
8:
2.166792640609733028489040133868649059047633580398487524801005319926075112840672412283211685707237665
comment: The minimum is attained at $\lambda_{7,8}=13.3998812040$.
8
2:
0.5349972862942120647093615028586932402334758358840069618775340834355588710370165929157239360269315149
comment: The minimum is attained at $\lambda_{8,2}=3.13226545054$.
8
3:
0.8285355339483092068340119880824122581040263478944722649242611763803801444061341548013800496114170331
comment: The minimum is attained at $\lambda_{8,3}=5.32041039859$.
8
4:
1.078169217319322920020916628729130248405354550080985903414308997880845963886445608308421470240935175
comment: The minimum is attained at $\lambda_{8,4}=7.20134216709$.
8
5:
1.307146422785888337627727232743189910811692878018743497978009008061914750458131358475026583304693283
comment: The minimum is attained at $\lambda_{8,5}=8.93768905882$.
8
6:
1.523451491774642143329123483282857870078019849233589935917179905686914277105115893829523569510649675
comment: The minimum is attained at $\lambda_{8,6}=10.5853439866$.
8
7:
1.730952680658104541188229743060792854014293701355939375857143643243204575411450657458904714550997219
comment: The minimum is attained at $\lambda_{8,7}=12.1713693666$.
8
8:
1.931872255411836733030529946902264359949878782104978758785345941331716366775242985330701814031074193
comment: The minimum is attained at $\lambda_{8,8}=13.7113053190$.
Definition
The $r$-core of a $k$-uniform hypergraph [6] is its largest subhypergraph with every vertex of degree at least $r$. In the random model with $n$ vertices and $m=\lfloor cn\rfloor$ edges, $c_{k,r}$ is the high-probability threshold between empty and nonempty $r$-cores [1] [2].
Parameters
$k$
—   edge size ($k\geq3$)
$r$
—   minimum degree of the core ($r\geq2$)
Formulas
(1)
$Q(\lambda,s)=\mathbb{P}(\mathrm{Po}(\lambda)\geq s) =1-e^{-\lambda}\sum_{j=0}^{s-1}\lambda^j/j!$, where $\mathrm{Po}(\lambda)$ is a Poisson random variable of mean $\lambda$.
(2)
$c_{k,r}=\min_{\lambda>0}\frac{\lambda}{kQ(\lambda,r-1)^{k-1}}$ for $k\geq3$ and $r\geq2$ [1] [2].
(3)
The minimiser $\lambda_{k,r}$ is the unique positive zero of $g(\lambda)=Q(\lambda,r-1) -(k-1)e^{-\lambda}\lambda^{r-1}/(r-2)!$. The sign of $g$ is the sign of the derivative of $\lambda/Q(\lambda,r-1)^{k-1}$, and $g'(\lambda)=e^{-\lambda}\lambda^{r-2}((k-1)\lambda-(k-1)(r-1)+1)/(r-2)!$, so $g$ decreases and then increases, with one positive zero.
Comments
(4)
This table measures density by edges per vertex, $c=m/n$; the average degree is $kc$. The table of $k$-core thresholds of the Erdős–Rényi random graph measures graph density by average degree, which is $2c$, so the same minimisation as (2), taken at $k=2$, gives half of each value stored there for $r\geq3$. This table has no rows with $k=2$. For $r=2$ the graph $2$-core grows continuously from edge density $1/2$, while for every $k\geq3$ the hypergraph $2$-core appears discontinuously. Dembo and Montanari use the reciprocal density $n/m$ for $2$-cores of uniform hypergraphs [3].
(5)
The $r=2$ rows are the obstruction thresholds for peeling processes on random uniform hypergraphs. $c_{3,2}$ is also the clustering threshold of random $3$-XORSAT [3] [4]. Molloy's Boolean-formula application gives the threshold for the pure literal rule on random $k$-SAT as clause density $2c_{k,2}$ [1]. For invertible Bloom lookup tables (IBLTs), the standard three-hash recovery threshold is the reciprocal density $1/c_{3,2}$ cells per key [5].
Programs
(P1)
Python
from mpmath import mp
mp.dps = 50
k, r = 3, 2
Q = lambda x, s: mp.gammainc(s, 0, x, regularized=True)
g = lambda x: Q(x, r - 1) - (k - 1) * mp.e**(-x) * x**(r - 1) / mp.factorial(r - 2)
lam = mp.findroot(g, r)
print(lam / (k * Q(lam, r - 1)**(k - 1)))
References
[1]
M. Molloy, Cores in random hypergraphs and Boolean formulas, Random Structures & Algorithms 27 (2005), 124-135. (doi)
[2]
J. Cain and N. Wormald, Encores on cores, Electronic Journal of Combinatorics 13 (2006), R81.
[3]
A. Dembo and A. Montanari, Finite size scaling for the core of large random hypergraphs, Annals of Applied Probability 18 (2008), 1993-2040. (arXiv) (doi)
[4]
M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh and M. Rink, Tight thresholds for cuckoo hashing via XORSAT, Proceedings of ICALP 2010, Lecture Notes in Computer Science 6198, 213-225. (arXiv) (doi)
[5]
V. Gaďurek and P. Veselý, Breaking 2-Cores for Invertible Bloom Lookup Tables by Structure Prediction, 24th International Symposium on Experimental Algorithms (SEA 2026), LIPIcs 371 (2026), 19:1-19:24. (doi)
Links
Similar tables
$k$-core thresholds of the Erdős–Rényi random graph —   the graph case, written in average degree rather than edge density, with the core degree as its only parameter
Data properties
Entries are of type: real number
How well the digits are known: proven
Sources of data: [1], [2]
Table is complete: no (it holds $c_{k,r}$ for every $3\leq k\leq8$ and $2\leq r\leq8$)
How they were obtained:

Each entry is the value at the minimiser $\lambda_{k,r}$ of $f(\lambda)=\lambda/(kQ(\lambda,r-1)^{k-1})$, computed in ball arithmetic with 64 guard bits beyond the 100 digits written.

more

That $\lambda_{k,r}$ is the unique minimiser and the minimum is global follows from the sign of $f'$, which is the sign of $g$ in (3): $g$ is negative before $\lambda_{k,r}$ and positive after it, so $f$ decreases and then increases. The computation encloses $\lambda_{k,r}$ by bisection on the sign of $g$ between $(r-1)-1/(k-1)$ and $4(k+r)+10$, each sign decided in ball arithmetic, down to a bracket of half-width $10^{-106}$ whose ends are then checked to give $g$ opposite signs, and evaluates $f$ on that bracket as a ball; the Poisson tail is the finite sum in (1). Before any entry was written, all values were compared with an mpmath computation at 120 digits that writes the tail as the regularised incomplete gamma function and finds the minimiser as a root of the numerical derivative; the extension of the generator to $k=2$ was also compared with the graph-core table, where it gives exactly half of each stored value for $3\leq r\leq8$.



API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.