The sharp threshold conjecture for rank deficiency in sparse random GF[2] matrices
Statement
Let be the row-weight random variables, assume that the sequence is uniformly bounded, and suppose
for every . Let denote the rank deficiency and let be the upper threshold defined in the paper. Sharp threshold conjecture. The normalized rank deficiency converges in probability to this threshold:
as . The preceding theorem proves matching lower and upper bounds up to the currently available threshold estimates, and the conjecture asserts that the upper bound is sharp; the asymptotics of remain open in this setting.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.