Talk:Ramsey's theorem: Difference between revisions

:: While I generally agree that the majority of “solutions” fail at the task as written, I'm not at all sure about how one could go about creating an ''algorithm'' to construct a graph from the requirements as listed. What would be possible would be to create the graph and check that the condition is true; a ''proof-checking'' operation, not a ''proof-generating'' operation. (I'm not quite sure what the lemma is that we'd be checking, probably that <math>R(?,?,?,?) > 17</math> as this looks like it's overlaying 4 connection patterns on the one graph, but that's of lesser concern.) Elevating to proof-generating would require graph generation, graph checking and sweeping up through the possible graph sizes, which would be potentially very expensive! Having a task that could require a significant amount of supercomputing time to execute without generating meaningful results earlier is a bit of a disqualification on the “good task” front, methinks. (There's multiple nested brute force steps in that outline; it would be nastily expensive to run.)

:: In any case, this task needs some significant revision work. It needs to be something which is practical, and yet not trivial. Merely generating the graph concerned is too trivial (we can have it as another task I suppose, but it's just too small a piece of working with Ramsey's theorem) yet doing proper proofs is too hard. I don't plan to attempt to solve this task (in Tcl, of course) until the task is worth solving. –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 08:22, 22 December 2013 (UTC)