Den (två) kärnan i en hypergraf är den maximala samlingen av hyperkanter inom vilken ingen vertex visas endast en gång. Det är av betydelse i uppgifter som att effektivt lösa ett stort linjärt system över GF [2], eller iterativ avkodning av lågdensitet paritet-kontrollkoder som används över binära raderingskanalen. Liknande strukturer uppstår i en mängd olika NP-hård combinatorial optimering och beslutsproblem, från vertex cover till satisfiability. För en jämnt vald slumpmässig hypergraf av m = nρ hörn och n hyperkanter, var och en bestående av samma fasta tal l ≥ 3 hörn, storleken på kärnan uppvisar för stora n en första ordningen fas övergång, förändras från o(n) för ρ > ρ c till en positiv bråkdel av n för ρ < ρ c, med en övergångsfönsterstorlek (n −1/2 ) runt ρ c > 0. Analysera motsvarande "bladborttagning" algoritm, vi bestämmer den associerade finita storlek skalning beteende. I synnerhet om ρ är inne i skalningsfönstret (mer exakt, ρ = ρ c + rn −1/2 ), sannolikheten för att ha en kärna av storlek (n) har en gräns strikt mellan 0 och 1, och en ledande korrigering av ordningen (n −1/6 ). Korrigeringen medger en skarp karakterisering i termer av fördelningen av en Brownsk rörelse med kvadratisk förändring, från vilken den ärver skalningen med n. Detta beteende förväntas vara universellt för en bred samling av kombinatoriska problem.
I samma dokument påpekade de (se Ref Anmärkning 2.6) att deras tekniker var tillämpliga på en mängd olika egenskaper hos kärnan "i skalsystemet" ρ = ρ c + rn −1/2 där ρ c är tröskeln för uppkomsten av kärnan.
Finite size scaling for the core of large random hypergraphs
{'venue': None, 'journal': 'Annals of Applied Probability', 'mag_field_of_study': ['Mathematics']}