Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Every tournament on 1414 vertices contains a transitive subtournament on 55 vertices (Theorem 4, printed p. 235), so f(14)≥5f(14)\ge5, while the conjectured formula of Problem 1216 gives ⌊log⁡214⌋+1=4\lfloor\log_214\rfloor+1=4; one such nn refutes the formula, so the answer to the question is no. The paper also gives a 1313-vertex tournament with no transitive 55-subtournament (pp. 235--236), so f(14)=5f(14)=5 exactly and the directed Ramsey number R(5)R(5) is 1414, and its Corollary 2 (p. 235) gives f(n)≥⌊log⁡2(16n/7)⌋f(n)\ge\lfloor\log_2(16n/7)\rfloor for every n≥14n\ge14, which exceeds ⌊log⁡2n⌋+1\lfloor\log_2n\rfloor+1 for nn in [7⋅2j,2j+3)[7\cdot2^j,2^{j+3}) for each j≥1j\ge1. The paper states the conjecture in the equivalent form that for each kk some tournament on 2k−1−12^{k-1}-1 vertices has no transitive kk-subtournament and shows it false for every k≥5k\ge5. The source is the library's source card, for the publisher's open-archive version. What the disproof leaves open, the exact value of f(n)f(n) for 34≤n≤4634\le n\le46 and from n=57n=57 on and the asymptotic constant between 11 and 22, is recorded on the problem page and is not part of this claim.

Depends on. Nothing in this wiki; the result is the paper's own theorem.

Dating. The page is dated by the issue month of the journal record (J. Combinatorial Theory 9 (1970), no. 3, October 1970, per the Crossref record); the day in the page name is a placeholder. The paper was received in August 1968 (p. 225).

Acceptance. Reviewed: the site's curator, T. F. Bloom, labels the problem DISPROVED and credits Reid and Parker in the problem's commentary with the negative answer for every n≥14n\ge14 (page last edited 12 April 2026); the curator neither submitted nor co-wrote the result and is independent of the authors, and the community database records the problem disproved (last updated 21 April 2026). The site's "for every n≥14n\ge14" overstates the result: the formula ⌊log⁡2n⌋+1\lfloor\log_2n\rfloor+1 holds again for 16≤n≤2716\le n\le27 (the paper's own values, p. 236) and for n=32,33n=32,33, and fails for infinitely many nn, as the problem page records. Refereed: J. Combinatorial Theory 9 (1970), no. 3, 225--238, communicated by Leo Moser. The theorem is attested by two later refereed sources: the survey paragraph of Ihringer, Rajendraprasad and Weinert (Discrete Math. 2021, p. 2) and Table 1 of McCarthy and Monico (Electron. J. Combin. 2025, p. 7) both cite R(5)=14R(5)=14 to the paper. Nagy's introduction (in the author-hosted copy; no journal record found in Crossref) names the paper as the disproof of the conjecture, and Neumann-Lara's shorter proof of Corollary 1 (Graphs Combin. 10 (1994), 363--366) has its own claim page; these attestations are beside the evidence listed above.

Read depth. Claims checked: Theorem 4 and Corollaries 1--2 on p. 235, and the 1313-vertex witness on pp. 235--236, whose automorphisms reduce the check to one cyclic triple, OS(0,1)={2,3,6}OS(0,1)=\{2,3,6\}, for the arcs with difference in {1,3,9}\{1,3,9\}; the arcs with difference in {2,5,6}\{2,5,6\} form a second orbit, mapped to (0,2)(0,2), and OS(0,2)={3,5}OS(0,2)=\{3,5\} has only two elements, so no TT3TT_3 lies above them either (the paper states only the first triple). The proof of Theorem 4 was followed as a reduction to the paper's Theorems 2 and 3; the case analysis proving Theorem 3 (pp. 227--235) was read for structure only and not checked, and nothing is independently reviewed in this corpus.