NumberDB$^\beta$ Advanced search Tags Tables Help Login
Minimisers in the core threshold formula of random $k$-uniform hypergraphs
edit · history · discussion · files · long url · statistical mechanics combinatorics probability theory
Numbers
$k$
$r$ 
$\lambda_{k,r}$
3
2:
1.256431208626169676982737616609216326916416831701323711125894727048300478541051903533664750947250849
comment: The associated core threshold is $c_{3,2}$.
3
3:
3.213563520216979243990721598628550332961016937266993935011570314990932508944562066900919080501639543
comment: The associated core threshold is $c_{3,3}$.
3
4:
4.921981846772290888776752883024317186056436573439824091508273468468509196715986475449901324256178986
comment: The associated core threshold is $c_{3,4}$.
3
5:
6.515591826097798170851877858293313883072308134824081056860046654688644744395191367617398426422648410
comment: The associated core threshold is $c_{3,5}$.
3
6:
8.039263820146856092138856254339199422167993794012407995996779695584362939354934009423133546902118161
comment: The associated core threshold is $c_{3,6}$.
3
7:
9.514469508880899030507393558450993274264377875660089436754383763320216720140867547689851121592635562
comment: The associated core threshold is $c_{3,7}$.
3
8:
10.95346075985564844256143919627797293749795469545187124088935549568731785512016948741082119567842981
comment: The associated core threshold is $c_{3,8}$.
4
2:
1.903813694440383484710140360828135127280364804561987445879389818281945875445251742935897221209070264
comment: The associated core threshold is $c_{4,2}$.
4
3:
3.943432991608201993709553168630446799608703563709097909739285068630870979892017973839711377125004985
comment: The associated core threshold is $c_{4,3}$.
4
4:
5.712655689793184261749113193644386168167982023993296659606920984267937821370298005601033912014038776
comment: The associated core threshold is $c_{4,4}$.
4
5:
7.356238662572010428146260839034522811851758906746380894035040209606244738087812519651127293227178069
comment: The associated core threshold is $c_{4,5}$.
4
6:
8.923133543937897404138547779823342524209920334968527807245157335182798107944509307833635497158032921
comment: The associated core threshold is $c_{4,6}$.
4
7:
10.43685728939695192283051786477345424635359010958106227104559457532044084712440111362795839930312800
comment: The associated core threshold is $c_{4,7}$.
4
8:
11.91085482297029987283273947363803164895241207451413619648971821871543101470988522101009737414578049
comment: The associated core threshold is $c_{4,8}$.
5
2:
2.336662982263053881182850266714011154679504739557109039685225120116767568104385781543593285556392922
comment: The associated core threshold is $c_{5,2}$.
5
3:
4.429961741174340595794299265887946343440849798841691898549878810448210800725524242240549510592604875
comment: The associated core threshold is $c_{5,3}$.
5
4:
6.239233099841364699091761779242710268467766957008527239152171992449855251908655717861069860689669939
comment: The associated core threshold is $c_{5,4}$.
5
5:
7.915932808932573244389888265459534420745939469008615284488694955445411352543868387413870342466396931
comment: The associated core threshold is $c_{5,5}$.
5
6:
9.511581543348483155284054757333259972267475267373966015269183105044286077661111762509825055266705227
comment: The associated core threshold is $c_{5,6}$.
5
7:
11.05099850311515789634766292263302508532769550742277390402251011897664690455990175411305835670362303
comment: The associated core threshold is $c_{5,7}$.
5
8:
12.54839414688261437023640741484170199310321861483385964228059641879490595267312347778684332551874187
comment: The associated core threshold is $c_{5,8}$.
6
2:
2.660399058463684990432673112693838761316192793557399779133621108141380344526679670369701126317582048
comment: The associated core threshold is $c_{6,2}$.
6
3:
4.792922350729458389393836269395977881768808104455610404765378350938009353293442180198297113646891715
comment: The associated core threshold is $c_{6,3}$.
6
4:
6.631692044980859859695457087456113562828943559209647679904601932328360504449403525078647056405154631
comment: The associated core threshold is $c_{6,4}$.
6
5:
8.332885060545474643453038367357276844362292641194579907242869038284539339311870952451145000236630570
comment: The associated core threshold is $c_{6,5}$.
6
6:
9.949856035279598965993281101298144352595406559863380482666470886487477439749560118793565830379607461
comment: The associated core threshold is $c_{6,6}$.
6
7:
11.50836092309161955292977618826790777947661320182321955172192652659584731470204336130700207829174634
comment: The associated core threshold is $c_{6,7}$.
6
8:
13.02316374017669072156336769629112584326498148263216486482457051849391131216069892990076318148638379
comment: The associated core threshold is $c_{6,8}$.
7
2:
2.918300475783052591304221719797499459970061873861584609944495208244877889764383735414949103879265396
comment: The associated core threshold is $c_{7,2}$.
7
3:
5.081459160901541280072984052767384364834705608549266804400302362457469786927329892961576241670256255
comment: The associated core threshold is $c_{7,3}$.
7
4:
6.943403149510170669582130838854226834674871175506322769216454740852507523491016500409957336861346672
comment: The associated core threshold is $c_{7,4}$.
7
5:
8.663897435137174519899583577567728252667605281255596605005591025135471805928532424709794084516994332
comment: The associated core threshold is $c_{7,5}$.
7
6:
10.29770370948003437532796512255737443462847796934890923922314195797931097072888681130447394638516963
comment: The associated core threshold is $c_{7,6}$.
7
7:
11.87130070214323957227718493587230991764172191009718801979638624429793118363290687748586153232250824
comment: The associated core threshold is $c_{7,7}$.
7
8:
13.39988120401632761753924670661057126272293378422422449028809204749315606537864394912727852237790303
comment: The associated core threshold is $c_{7,8}$.
8
2:
3.132265450540420106833422460869303332477500804253648991520139627783433414358227583586491785309904738
comment: The associated core threshold is $c_{8,2}$.
8
3:
5.320410398592856390274399571423194057429031818068357224721914044015662800282969722273689295179037782
comment: The associated core threshold is $c_{8,3}$.
8
4:
7.201342167086465465995230954511332137013680863221225905126416091272120474693659568328505902778556493
comment: The associated core threshold is $c_{8,4}$.
8
5:
8.937689058821257897847473075778498054363562033589717691202034236556493355565920677841425777848131716
comment: The associated core threshold is $c_{8,5}$.
8
6:
10.58534398664845734750878149290269445326079627643095634678228319037799585247784783513560945584997527
comment: The associated core threshold is $c_{8,6}$.
8
7:
12.17136936664993198917735237904287147986248521678215131664326659268714127192768870112217956585325223
comment: The associated core threshold is $c_{8,7}$.
8
8:
13.71130531896385558662755379683587375766125942222105380706720345280147382907814364034891657375807970
comment: The associated core threshold is $c_{8,8}$.
2
3:
1.793282132900761007557553363901042400798495011352844840187368692793640350312145307101816031284552000
comment: The corresponding graph $r$-core threshold is $c_3$, in average-degree normalisation.
2
4:
3.383634282853181326233720626325268824492707241179045519190265623070215823455522487634872897545945707
comment: The corresponding graph $r$-core threshold is $c_4$, in average-degree normalisation.
2
5:
4.881277491345664699476221132699578165991747552538638780470402006490011336193449645628928782932652016
comment: The corresponding graph $r$-core threshold is $c_5$, in average-degree normalisation.
2
6:
6.322505551033348213117536010712698139853551563542760107474509790804292377580695833711266516282831955
comment: The corresponding graph $r$-core threshold is $c_6$, in average-degree normalisation.
2
7:
7.724583600437083719742881506618773234074923503267538261336546494114206039730648969106716340789423916
comment: The corresponding graph $r$-core threshold is $c_7$, in average-degree normalisation.
2
8:
9.097344402575752511530172721804952369723320459976861539455985671621454422104751816436773258597298092
comment: The corresponding graph $r$-core threshold is $c_8$, in average-degree normalisation.
2
9:
10.44703068132582643466146774023156489999628189515940834443242756856517508061830202668735584626248927
comment: The corresponding graph $r$-core threshold is $c_9$, in average-degree normalisation.
2
10:
11.77790660645444814760342031501205362589525223509565135072961175420145126514944898686789068160617415
comment: The corresponding graph $r$-core threshold is $c_10$, in average-degree normalisation.
2
11:
13.09304249828627741818047196896153062418531383505357205182742728349180778379297745359746436233268261
comment: The corresponding graph $r$-core threshold is $c_11$, in average-degree normalisation.
2
12:
14.39473890191730692303041347143866646079914037894170847648844652786607945528956529938703860316494576
comment: The corresponding graph $r$-core threshold is $c_12$, in average-degree normalisation.
Definition
For integers $k\geq2$ and $r\geq2$, except $(2,2)$, $\lambda_{k,r}$ is the positive $\lambda$ that minimises $\lambda/(kQ(\lambda,r-1)^{k-1})$; here $Q(\lambda,s)=\mathbb{P}(\mathrm{Po}(\lambda)\geq s)$. The formula is for random $k$-uniform hypergraphs [3].
Parameters
$k$
—   edge size ($k\geq2$)
$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!$.
(2)
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 derivative is $g'(\lambda)=e^{-\lambda}\lambda^{r-2}((k-1)\lambda-(k-1)(r-1)+1)/(r-2)!$.
(3)
$c_{k,r}=\min_{\lambda>0}\lambda/(kQ(\lambda,r-1)^{k-1}) =\lambda_{k,r}/(kQ(\lambda_{k,r},r-1)^{k-1})$ [1] [2].
Comments
(4)
For $k\geq3$, the notation and indexing match the core threshold table, whose $c_{k,r}$ is obtained from $\lambda_{k,r}$ by (3). The $k=2$ rows use the same minimisation for the graph core threshold table, which writes thresholds in average-degree normalisation.
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)
lo = mp.mpf(r - 1) - mp.mpf(1) / (k - 1)
hi = mp.mpf(4 * (k + r) + 10)
while g(hi) <= 0:
    hi *= 2
for _ in range(4 * mp.dps):
    mid = (lo + hi) / 2
    if g(mid) < 0:
        lo = mid
    else:
        hi = mid
print((lo + hi) / 2)
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.
Links
Similar tables
Core thresholds of random $k$-uniform hypergraphs —   thresholds obtained from these minimisers by the formula for $c_{k,r}$
$k$-core thresholds of the Erdős–Rényi random graph —   graph-case thresholds obtained from the same minimisers at edge size $2$ and written in average degree rather than edge density
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 $\lambda_{k,r}$ for every $3\leq k\leq8$ and $2\leq r\leq8$, and for edge size $k=2$ with $3\leq r\leq12$; $(2,2)$ is omitted because the minimum is approached as $\lambda\to0$ and has no positive minimiser)
How they were obtained:

Each entry is computed in ball arithmetic with 64 guard bits beyond the 100 digits written.

more

The function $\lambda/(kQ(\lambda,r-1)^{k-1})$ has only one minimiser because the sign of its derivative is the sign of $g$ in (2); the displayed derivative $g'$ is negative below $(r-1)-1/(k-1)$ and positive above it, so $g$ first decreases from $0$ and then increases to $1$, crossing zero once on $(0,\infty)$. 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 checked to give opposite signs; that bracket is the stored ball. The Poisson tail is the finite sum in (1). The generator compares every row with an mpmath computation at 120 digits that writes $Q$ as the regularised incomplete gamma function, compares every derived threshold for the $k\geq3$ rows with the core threshold table, and checks the edge-size-$2$ rows against the graph-core threshold table.



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