0
$\begingroup$

The probabilistic method is a technique for proving the existence of an object with certain properties by showing that a random object chosen from an appropriate probability distribution has the desired properties with positive probability. For example: enter image description here https://cpb-us-east-1-juc1ugur1qwqqqo4.stackpathdns.com/sites.psu.edu/dist/f/7257/files/2013/10/The-Probabilistic-Method.pdf

If $\binom nk \cdot 2^{1-\binom k2}<1$, then $R(k,k)>n$. Thus $R(k,k)>\lfloor 2^{k/2}\rfloor$ for each $k\ge3$.

Is there any example for getting some properties on planar graphs using the probabilistic method? We know that discharging can get many useful local structures. I feel that the probability method is also a way of counting skill.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ the crossing number inequality has a short probabilistic proof, for example $\endgroup$
    – Fedor Petrov
    Commented Mar 3, 2021 at 14:32
  • $\begingroup$ @FedorPetrov: nice answer, but it's not quite a result about planar graphs. One problem with the question is that there's not an obvious simple random model of planar graphs... $\endgroup$
    – Sam Hopkins
    Commented Mar 3, 2021 at 14:34
  • $\begingroup$ @Sam Hopkins Thanks! For probability method, I am a beginner. My quetion is: For some specific graph classes(for example: minimum degree is greater than 5 , whether we can get some properties. just example may be Inappropriate. Theorem: If a planar graph has minimum degree 5, then it either has an edge with endpoints both of degree 5 or one with endpoints of degrees 5 and 6. $\endgroup$
    – Licheng Zhang
    Commented Mar 3, 2021 at 14:52
  • $\begingroup$ The structural results you're talking about appear to have a pretty different flavor than the things proved with the probabilistic method (which are usually inequalities...) but who knows $\endgroup$
    – Sam Hopkins
    Commented Mar 3, 2021 at 14:59

0

Reset to default

You must log in to answer this question.