Premium
Complete matchings in random subgraphs of the cube
Author(s) -
Bollobás Béla
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240010107
Subject(s) - social connectedness , combinatorics , cube (algebra) , matching (statistics) , hitting time , mathematics , degree (music) , constant (computer programming) , discrete mathematics , computer science , physics , statistics , psychology , psychotherapist , programming language , acoustics
In this article it is shown that for almost every random cube process the hitting time of a complete matching equals the hitting time of having minimal degree (at least) one and also the hitting time of connectedness. It follows from this that if t = ( n + c + o (1))2 n −2 for some constant c , then the probability that a random subgraph of the n ‐cube having precisely t edges has a complete matching tends to e − e −e −c.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom