# Tag Info

1 vote
Accepted

• 11.3k

### Quasi-random vs pseudo-random graphs

Someone else will probably have a better answer, but I can't leave a comment. In my experience "quasi-random graph" (almost?) always refers to the Chung Graham Wilson type graphs you ...
• 76
1 vote
Accepted

### Algorithm for finding a minimum weight circuit in a weighted binary matroid

The problem is NP-hard (even in the unweighted case) via a well-known connection to coding theory. Namely, if $A$ is the parity check matrix of a binary linear code $C$, then the distance of $C$ is ...
• 29.2k
Let me assume $p > (1 + \varepsilon)(2 \ln n/ n)^{1/2}$, this in particular includes the case of constant $p \in (0,1)$. If $p > (1 + \varepsilon)(2 \ln n/ n)^{1/2}$ then w.h.p. the binomial ...