Let me add that I wrote an answer on a different but related question in which you might find some other interesting references. In particular, a lot of what I wrote above I learned from some of the introduction to Gortler, Healy and Thurston's paper on generic global rigidity in higher dimensions, which gives a nice overview of a lot of the work on these problems.

Let me add that I wrote an answer on a different but related question in which you might find some other interesting references. In particular, a lot of what I wrote above I learned from some of the introduction to Gortler, Healy and Thurston's paper on generic global rigidity in higher dimensions, which gives a nice overview of a lot of the work on these problems.

In (5), the reason that you almost surely will have a generic framework is because the set of non-generic vertices is not dense in the set of all possible choices of vertices that you're choosing from. It's a bit like choosing uniformly at random a number from the unit interval and asking if it's an algebraic number.

What if I said I was going to randomly and densely place vertices in cells of a finite matrix?

In this situation, which I think is effectively the same as choosing your vertices to have bounded integer coordinates (i.e. choosing from an integer grid), instead of zero probability that you will have some relation between the coordinates of the vertices, you will always have algebraic (rational, even) relations between the coordinates of the vertices.

However, not all is lost. I think that all that the "no algebraic relations at all between vertices" definition of genericity is doing here is actually just making sure that the vertices lie away from those algebraic relations which are defined by the minors of the rigidity matrix (see e.g. the discussion on pages 21 and 22 in Graver, Servatius and Servatius's book ) or see sections 3 and 4 in Connelly's paper Generic Global Rigidity to see how genericity is actually used in these theorems. So, in some sense that definition is a bit of overkill -- instead of avoiding every algebraic relation, you just have to avoid those coming from the rigidity matrix. I won't give a definition of the rigidity matrix (sometimes "stress matrix") here -- you can find it in most of the papers on rigidity that I've cited.

So, if you choose the vertices randomly with bounded integer coordinates, you will have a finite probability of getting an embedding which is non-generic in the sense that one or more of the minors of the rigidity matrix defined by the graph happen to vanish - note that these are the cases where the rigidity behavior of the embedding will differ from the generic embedding predictions for your graph. Roughly speaking, the locus of positions of vertices which satisfy some relation coming from the rigidity matrix (which is all that matters for rigidity properties) is going to be an intersection of lower dimensional algebraic curves in the full space.

If you're choosing the coordinates from a large enough set of integers (or equivalently, if your "matrix" is dense enough in the region of space you're approximating with it), the probability of such non-generic behavior should be small enough that you don't have to worry about it. When your matrix is really big, most of the vertex positions will avoid the "bad" subset and the generic rigidity predictions will coincide with the actual behavior. Don't ask me to give explicit estimates though...

All of the above is kind of artificial though. Remember that if you just perturb the positions of each of the coordinates of your vertices each by some tiny incommensurate transcendental numbers, your embedding will be generic in the original sense no matter what you started with. You might even say that any "physical" graph will always be embedded generically because there's no way to place perfectly commensurate vertices or edges. I guess what could go bad when you are very close to a non-generic embedding is that you have some different "approximate" embeddings with edge lengths very close to those of your original graph.

I'm just learning most of this stuff myself, so I think I would recommend you to spend some time understanding the papers and making sure that what I said is right too.