What is a "non-constructive proof?"

[Dutle, Aaron M. (LARC-D320)]

"There are at least three kinds of ?non-constructive proofs? that I have seen:
(1) A theorem that certain equations have finitely many solutions, with no bound given that would allow one to exhaustively search for them
(2) A theorem that a certain equation has a solution, with no bound given, but a guarantee that searching will eventually find one
(3) A counting argument that an object with certain properties of a certain size must exist, which comes with an implicit exponential bound on the search but no efficient construction.
" 


Classics of type (3) abound in combinatorics. Particularly in proofs where the best bounds are found using probabilistic methods. A (fairly) simple classic is "high girth and high chromatic number." This says that for all m,n, there is a graph G with girth(G)>m and \chi(G)>n. This is somewhat counterintuitive, because high chromatic number is generally form having a large clique, while girth is the length of the shortest cycle. The result is shown by choosing an appropriate random graph, and showing that as n->\infty, the probability of choosing a graph with both properties simultaneously is positive. Math majors with some background in probability and a little graph theory should be able to follow a well-presented proof. The classic reference for this type of problem is "The Probabilistic Method" by Noga Alon and Joel Spencer. 

  

Aaron M. Dutle
Research Computer Scientist 
Safety-Critical Avionics Systems Branch
NASA Langley Research Center
757-864-9326


On 2/18/20, 12:13 PM, "fom-bounces at cs.nyu.edu on behalf of fom-request at cs.nyu.edu" <fom-bounces at cs.nyu.edu on behalf of fom-request at cs.nyu.edu> wrote:

    Send FOM mailing list submissions to
    	fom at cs.nyu.edu
    
    To subscribe or unsubscribe via the World Wide Web, visit
    	https://urldefense.proofpoint.com/v2/url?u=https-3A__cs.nyu.edu_mailman_listinfo_fom&d=DwICAg&c=ApwzowJNAKKw3xye91w7BE1XMRKi2LN9kiMk5Csz9Zk&r=X7uq6g1m5_8dzQ5adu7hIXZuYVF6JTn1BUGGUY4Ndfs&m=9ODhWwmOqD3B26Td0_nvb6RPw5w9g4FfLi5N1ryFIoo&s=1sHNHJjbOjSoeRbTtGuQhVeAVET5H8RPFAP_HMPp1jk&e= 
    or, via email, send a message with subject or body 'help' to
    	fom-request at cs.nyu.edu
    
    You can reach the person managing the list at
    	fom-owner at cs.nyu.edu
    
    When replying, please edit your Subject line so it is more specific
    than "Re: Contents of FOM digest..."
    
    
    Today's Topics:
    
       1. What is a ?non-constructive proof?? (Joe Shipman)
    
    
    ----------------------------------------------------------------------
    
    Message: 1
    Date: Sun, 16 Feb 2020 21:46:01 -0500
    From: Joe Shipman <joeshipman at aol.com>
    To: Foundations of Mathematics <fom at cs.nyu.edu>
    Subject: What is a ?non-constructive proof??
    Message-ID: <CEB385D3-FBA7-4017-BBCF-5F115B5B0234 at aol.com>
    Content-Type: text/plain; charset=utf-8
    
    There are at least three kinds of ?non-constructive proofs? that I have seen:
    (1) A theorem that certain equations have finitely many solutions, with no bound given that would allow one to exhaustively search for them
    (2) A theorem that a certain equation has a solution, with no bound given, but a guarantee that searching will eventually find one
    (3) A counting argument that an object with certain properties of a certain size must exist, which comes with an implicit exponential bound on the search but no efficient construction.
    
    Can people provide examples of each of these three types where the proof can be presented to undergraduate math majors, and where no improvement is known? (In other words, a nonconstructive proof of each type where no proof is known of an easier type.)
    
    ? JS
    
    Sent from my iPhone
    
    
    ------------------------------
    
    _______________________________________________
    FOM mailing list
    FOM at cs.nyu.edu
    https://urldefense.proofpoint.com/v2/url?u=https-3A__cs.nyu.edu_mailman_listinfo_fom&d=DwICAg&c=ApwzowJNAKKw3xye91w7BE1XMRKi2LN9kiMk5Csz9Zk&r=X7uq6g1m5_8dzQ5adu7hIXZuYVF6JTn1BUGGUY4Ndfs&m=9ODhWwmOqD3B26Td0_nvb6RPw5w9g4FfLi5N1ryFIoo&s=1sHNHJjbOjSoeRbTtGuQhVeAVET5H8RPFAP_HMPp1jk&e= 
    
    
    End of FOM Digest, Vol 206, Issue 20
    ************************************