3 ms·

By proving that his two properties hold with probability >1/2 over the distribution of random graphs on n vertices (for sufficiently large n), you _have_ proven

By proving that his two properties hold with probability >1/2 over the distribution of random graphs on n vertices (for sufficiently large n), you _have_ proven that there exists at least one graph of order n with those properties. This is because the intersection of any two properties of measure > 1/2 has positive measure itself (simple inclusion exclusion argument) followed by applying the "tautological" statement I gave earlier. This is the whole point of the probabilistic method! There are a finite number of graphs of order n - I don't know why you keep claiming that his proof relies on there being infinitely many graphs, when it's clear that the entire proof takes place in that (finite) set. > We're talking about random subgraphs of size n OR LARGER. We're actually picking from an infinite set here. entirely possible that NO graphs with n vertices have the two properties; all we've shown is that every graph in a finite set has some positive probability to have our properties. This is incorrect. We really are picking from the (finite) set of graphs of order n. Erdos picks n carefully so that his properties have the desired probability, but it is fixed! > entirely possible that NO graphs with n vertices have the two properties; all we've shown is that every graph in a finite set has some positive probability to have our properties. This is not possible - as I have said, if a property holds with positive probability there is an element of the underlying space (i.e. a particular choice of graph of order n in this case) that satisfies it. If no element of your probability space satisfies P, then the probability that P holds is 0, basically by definition! This is extremely basic stuff - the measure of the empty set is always zero. I think you really need to learn some mathematical probability theory to get this straight - you seem to be confused about basic definitions here. My question to you - can you define a random graph on n vertices rigorously? Can you define the probability of a property of a random graph of n vertices rigorously? Until you can do that we are just talking in circles - everything I'm saying follows easily (not tautologically) from those definitions. I feel you are applying some intuitive conception of probability, which is leading you to misinterpret key parts of the proof. Everything here can be formalised precisely using measures and probability spaces, as Erdos himself absolutely knew.

bubblyworld 2y ago
https://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf https://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob... Here is a good technical introduction to the probabilistic method, which verifies everything I've written (in the same language as I've used too, namely that of measures and probability spaces, which is the standard in modern mathematics for formalising this stuff). In particular, I quote: > We would like to prove the existence of a combinatorial object with specified properties. Unfortunately, an explicit construction of such a “good” object does not seem feasible, and maybe we do not even need a specific example; we just want to prove that something “good” exists. Then we can consider a random object from a suitable probability space and calculate the probability that it satisfies our conditions. If we prove that this probability is strictly positive, then we conclude that a “good” object must exist; if all objects were “bad”, the probability would be zero. I also quote (emphasis mine): > 1.1.2 Definition (Random graphs). 6 The probability space of random graphs G(n, p) is a finite probability space whose elementary events are all graphs on a fixed set of n vertices.

bubblyworld 2y ago

https://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf https://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob... Here is a good technical introduction to the probabilistic method, which verifies everything I've written (in the same language as I've used too, namely that of measures and probability spaces, which is the standard in modern mathematics for formalising this stuff). In particular, I quote: > We would like to prove the existence of a combinatorial object with specified properties. Unfortunately, an explicit construction of such a “good” object does not seem feasible, and maybe we do not even need a specific example; we just want to prove that something “good” exists. Then we can consider a random object from a suitable probability space and calculate the probability that it satisfies our conditions. If we prove that this probability is strictly positive, then we conclude that a “good” object must exist; if all objects were “bad”, the probability would be zero. I also quote (emphasis mine): > 1.1.2 Definition (Random graphs). 6 The probability space of random graphs G(n, p) is a finite probability space whose elementary events are all graphs on a fixed set of n vertices.