NumberDB$^\beta$ Advanced search Tags Tables Help Login
Cuckoo hashing thresholds of random $k$-uniform hypergraphs
edit · history · discussion · files · short url · combinatorics probability theory
Numbers
$k$
$\ell$ 
$c^*_{k,\ell}$
2
1:
1/2
comment: The threshold is exact: with two choices and capacity one, success is equivalent to the cuckoo graph being a pseudoforest.
2
2:
1.794023736482697185702072260922220651446847857242629314741409159722842192323768658125858982706009313
comment: The root is $\xi_{2,2}=2.68799934550$.
2
3:
2.877462805773104601383446482855977688201566330213884344147609954701014361992024001432142349800224667
comment: The root is $\xi_{2,3}=5.07146970816$.
2
4:
3.921479097144247218622967455754882381969492446973709771717838244012920761856240928180429377430730329
comment: The root is $\xi_{2,4}=7.32170335898$.
2
5:
4.947756809299554345341872647115200280183738143165187479042937229462595359361250598170477473285153512
comment: The root is $\xi_{2,5}=9.49611633963$.
2
6:
5.964436239513138659619929120753446763597136707162676068555810567304407986993679162958098898424796905
comment: The root is $\xi_{2,6}=11.6220108348$.
3
1:
0.9179352766580860135154412282330241295566462813786741119388567679432894341028061252100137350717952174
comment: The root is $\xi_{3,1}=2.14912579991$.
3
2:
1.976402827945018131920271559975262298624969301245582124244029051282683200685764557735583055769410083
comment: The root is $\xi_{3,2}=5.65657634943$.
3
3:
2.991857217756977366680597685191668449623460870257231553720467580809494674831252223618984007293033939
comment: The root is $\xi_{3,3}=8.84985165247$.
3
4:
3.997012625648743302273762929913638565700653571578426870112509258493357375813089713288050426564473161
comment: The root is $\xi_{3,4}=11.9332406302$.
3
5:
4.998873294118150969333519117221896576217294921858737152365000264583014045776775919936019685113750641
comment: The root is $\xi_{3,5}=14.9703579883$.
3
6:
5.999568880504426099670108020028966633364065673199424477936168744197318069564183158242503476062116963
comment: The root is $\xi_{3,6}=17.9869322967$.
4
1:
0.9767701648780461315596453315801681767089324117092366344477820171954417168938976107089484319269740715
comment: The root is $\xi_{4,1}=3.59351196945$.
4
2:
1.996482967874904255590456922181224320635491112691848421532907427366799975400167532130410238462241788
comment: The root is $\xi_{4,2}=7.90767401912$.
4
3:
2.999385430194753174648485489376002505168401766875443841946011174195225771390338409594536448433558012
comment: The root is $\xi_{4,3}=11.9784075455$.
4
4:
3.999888264401298625623716085385569302254757474770833785533500959000231837332101924715416151887876541
comment: The root is $\xi_{4,4}=15.9950645692$.
4
5:
4.999979340653780324015040271985280966678004171623991495353210876623953329564676405924425455414668172
comment: The root is $\xi_{4,5}=19.9988997920$.
4
6:
5.999996141669181155871597337336411049803539145537996667408937848891236217991012208136281982868419701
comment: The root is $\xi_{4,6}=23.9997594760$.
5
1:
0.9924383912621006266589799793323504474696379410861973127564646960469684573473547755463108213196347197
comment: The root is $\xi_{5,1}=4.80100754972$.
5
2:
1.999448720069167727035462452430890911219734312410759174202843038368849831099715743153895577726858020
comment: The root is $\xi_{5,2}=9.97686430376$.
5
3:
2.999955435986581283444882025861140029212235129352555607766174797971254268977323520381948678026994564
comment: The root is $\xi_{5,3}=14.9974135011$.
5
4:
3.999996294949884624578061459731097323358511021420873096209477276474375757812738642334538931186731699
comment: The root is $\xi_{5,4}=19.9997251182$.
5
5:
4.999999687144044935393004612122874995112819585886125524372482323757480469448639156438469831161723458
comment: The root is $\xi_{5,5}=24.9999717443$.
5
6:
5.999999973288070189344630169624282144471417524844188007104938074752013814242184279230818936470510109
comment: The root is $\xi_{5,6}=29.9999971576$.
6
1:
0.9973795527786723480335298422727171806947578778455543989561183255629649006299375198226788332339351435
comment: The root is $\xi_{6,1}=5.90300005895$.
6
2:
1.999913747274470569389203571194216178672545088774116087666894883932989594152160007511452788301799383
comment: The root is $\xi_{6,2}=11.9946673302$.
6
3:
2.999996938381392376166114080230759591446494821958184942602793484833624392217738417863842320763123313
comment: The root is $\xi_{6,3}=17.9997334764$.
6
4:
3.999999888406371084509335436360640386934357548882021175485654372098562018995608685170457404864787032
comment: The root is $\xi_{6,4}=23.9999874749$.
6
5:
4.999999995861590166870067525133864208054376575359364102679230293551259772110190725782355071738634683
comment: The root is $\xi_{6,5}=29.9999994315$.
6
6:
5.999999999844601525039783111270085128864107889601055476101178401557652034751144040313008304160799203
comment: The root is $\xi_{6,6}=35.9999999748$.
7
1:
0.9990637587536802554886204642246230679289335411670661479087836641414840208770255075157509128677423698
comment: The root is $\xi_{7,1}=6.95345571335$.
7
2:
1.999986687836687466950470587085335927493710868623333718272369205851493375468424258861673415106998570
comment: The root is $\xi_{7,2}=13.9988580111$.
7
3:
2.999999798680631383681506245979015437628672628527238313672554169466675616181099647014632561347735652
comment: The root is $\xi_{7,3}=20.9999754217$.
7
4:
3.999999996867315061289050889484635088186412202341732709029986353874089772248409984224769542211257305
comment: The root is $\xi_{7,4}=27.9999995042$.
7
5:
4.999999999950315548351608834679948584474362081028250371712909868496022726268460193912208464051416812
comment: The root is $\xi_{7,5}=34.9999999903$.
7
6:
5.999999999999201282346480310860476468816909975235103544967261611856032007090916908596965754574630631
comment: The root is $\xi_{7,6}=41.9999999998$.
Definition
An $\ell$-orientation assigns each edge to one of its vertices, with at most $\ell$ edges at any vertex. In the random $k$-uniform hypergraph [5] with $n$ vertices and $\lfloor cn\rfloor$ edges, $c^*_{k,\ell}$ is the high-probability threshold for $\ell$-orientability [1].
Parameters
$k$
—   number of choices ($k\geq2$)
$\ell$
—   bucket capacity ($\ell\geq1$)
Formulas
(1)
$Q(x,s)=\mathbb{P}(\mathrm{Po}(x)\geq s) =1-e^{-x}\sum_{j=0}^{s-1}x^j/j!$.
(2)
For each listed pair $(k,\ell)\neq(2,1)$, $\xi_{k,\ell}$ is the unique positive solution of $k\ell=\xi_{k,\ell}Q(\xi_{k,\ell},\ell)/Q(\xi_{k,\ell},\ell+1)$.
(3)
$c^*_{k,\ell}=\xi_{k,\ell}/(kQ(\xi_{k,\ell},\ell)^{k-1})$ for $(k,\ell)\neq(2,1)$, and $c^*_{2,1}=1/2$ [1] [2].
Comments
(4)
The high-probability threshold means that, as $n\to\infty$, $\ell$-orientability has probability tending to $1$ for $c<c^*_{k,\ell}$ and to $0$ for $c>c^*_{k,\ell}$. In hashing language, edges are keys and vertices are buckets, so $c^*_{k,\ell}$ is the threshold for the number of keys per bucket in offline cuckoo hashing [4] with $k$ choices and bucket capacity $\ell$ [2]. The load factor, keys per slot, is $c^*_{k,\ell}/\ell$.
(5)
The density is $c=m/n$, so the average hypergraph degree is $kc$. Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh and Rink tabulate the same per-bucket thresholds with an index larger by one: their row labelled $\ell+1$ is this table's bucket capacity $\ell$ [2].
(6)
For $\ell=1$ and $k\geq3$, the thresholds are equal to satisfiability thresholds of random $k$-XORSAT [2]. The row $k=2$, $\ell=1$ is the ordinary two-choice cuckoo hashing threshold $1/2$ [4].
(7)
The obstruction is the $(\ell+1)$-core, whose appearance thresholds are in core thresholds of random $k$-uniform hypergraphs. At $c^*_{k,\ell}$, the core's asymptotic edge density is $\ell$ [1].
Programs
(P1)
Python
from mpmath import mp
mp.dps = 50
k, ell = 3, 1
Q = lambda x, s: mp.gammainc(s, 0, x, regularized=True)
if (k, ell) == (2, 1):
    print(mp.mpf(1) / 2)
else:
    g = lambda x: x * Q(x, ell) / Q(x, ell + 1) - k * ell
    xi = mp.findroot(g, k * ell)
    print(xi / (k * Q(xi, ell)**(k - 1)))
References
[1]
N. Fountoulakis, M. Khosla and K. Panagiotou, The multiple-orientability thresholds for random hypergraphs, Combinatorics, Probability and Computing 25 (2016), 870-908. (arXiv) (doi)
[2]
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)
[3]
J. A. Cain, P. Sanders and N. Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 469-476.
Links
Similar tables
satisfiability thresholds of random $k$-XORSAT —   the same threshold for bucket capacity one and $k\geq3$
core thresholds of random $k$-uniform hypergraphs —   the densities at which the $(\ell+1)$-cores appear; orientability fails later, when the core's edge density reaches $\ell$
Data properties
Entries are of type: real number
How well the digits are known: proven
Sources of data: [1], [2], [3]
Table is complete: no (it holds $c^*_{k,\ell}$ for every $2\leq k\leq7$ and $1\leq\ell\leq6$)
How they were obtained:

Each inexact entry is computed in ball arithmetic with 64 guard bits beyond the 100 digits written. The root $\xi_{k,\ell}$ is enclosed by bisection on the sign of $\xi Q(\xi,\ell)/Q(\xi,\ell+1)-k\ell$, down to a bracket of half-width $10^{-106}$ whose ends are checked to give opposite signs; the value of $\xi/(kQ(\xi,\ell)^{k-1})$ on that bracket is the stored ball.

more

The entry $c^*_{2,1}=1/2$ is exact. The generator also compares every inexact row with an mpmath computation at 120 digits that writes $Q$ as the regularised incomplete gamma function, and compares all rows in the printed range with the ten-decimal table in [2], using the source's index shift described in the comments.



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