Problems in Graph Theory from Memphis
Statement
Let denote the minimum number of edges induced by any set of n / 2 vertices in the Turán graph on n vertices for .If each set of vertices in a graph G of order n spans more than edges, then G contains a .
Context
Candidate 31 of the open problems stated in "Problems in Graph Theory from Memphis", extracted for the Scalable Mathematical Discovery run.
People
Attempts
No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.
NEW
Problem: Interpreting “the Turán graph for ” in the standard extremal sense as , the conjecture says: for all finite simple graphs of order , if every -vertex set spans more than edges, where is the minimum such number in , then contains .
Result: The statement is false.
Take and . The Turán graph for is . A part of size spans no edges, so
Let be the balanced blow-up of with each cycle vertex replaced by an independent set of size , and consecutive cycle classes joined completely. Then is triangle-free, since any triangle would project to a triangle in .
Also . Hence every -vertex subset of contains an edge, i.e. spans edges. Thus satisfies the hypothesis but contains no .
So the conjecture, as written, is disproved.
Citation: No external citation is needed; this is the standard -blow-up counterexample.
Reviews
1 machine checkNo person has reviewed this attempt. 1 machine check below — a machine check is not human verification.
Machine check · not human verification
machine: correctscope Full solution as submitted; SMD novelty classification KNOWN
PASS
The counterexample is valid for the conjecture as stated. For , the Turán graph is , so . The 2-fold balanced blow-up of is triangle-free and has independence number , so every 5-vertex set spans at least one edge, satisfying the hypothesis while containing no . Thus the conjecture is rigorously disproved.
Novelty assessment
KNOWN
Classification rationale: The counterexample is not a novel resolution. For , , so any triangle-free 10-vertex graph with independence number refutes the statement. The balanced -blow-up is a standard extremal example in the sparse-half/local-density literature and is stronger: every half-set spans at least edges.
Literature check: I found no explicit later note saying “Conjecture 14 is false,” but the exact construction is well known as the sharpness example for Erdős’s Sparse-Half Conjecture. Thus the accepted counterexample is an immediate special case of a published standard construction.
Citation: P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, “A local density condition for triangles,” Discrete Mathematics 127 (1994), 153–161. See also W. Bedenknecht, G. O. Mota, C. Reiher, M. Schacht, “On the local density problem for graphs of given odd-girth,” J. Graph Theory 90 (2019), 137–149.
No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.
Discussion of this attempt
no comments
Solve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.
Discussion
Nothing has been said about this problem yet.
Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.