files / problems / caccetta-haggkvist-k3 / compute / CONSTANTS.md

1.4 KB · on GitHub

Constants

quantity value source
conjectured out-degree threshold 1/31/3 Caccetta–Häggkvist 1978
published unrestricted threshold (refereed) 0.34650.3465 Hladký–Král'–Norin, Combinatorica 37 (2017)
claimed F₆ threshold 0.33880.3388 de Joannis de Verclos–Sereni–Volec, Mar 2014, personal communication
two-sided threshold 0.3435450.343545 Lichiardopol 2010 (both δ+\delta^+ and δ−\delta^-)
Shen elementary 3−7≈0.3542493-\sqrt{7}\approx 0.354249 Shen, JCTB 74 (1998)
HHK 0.35320.3532 Hamburger–Haxell–Kostochka, Electron. J. Combin. 2007
tonight, same F₄ system 0.346450.34645 certs/f4_certificate.json, worst F=−0.12343F=-0.12343
tonight, F₄ plus CKLS 2015 fork 0.346400.34640 q4/certs/keep/f4_or_new_certificate.json, worst F=−0.41903F=-0.41903
F₄ SDP saturation (this system) ≈0.346439\approx 0.346439 certs/sdp_bound.json

Cyclic construction: out-set {1,…,⌊(n−1)/3⌋}\{1,\ldots,\lfloor(n-1)/3\rfloor\} on Z/n\mathbb{Z}/n, C₃-free.

Exact finite statement: every nn-vertex oriented graph with δ+≥⌈n/3⌉\delta^+\ge\lceil n/3\rceil has a directed triangle.

First nn not implied by Hoàng–Reed (r≤5r\le 5) plus HKN 0.34650.3465 was n=18n=18. That order, and the later holes n=21,24,26,27,29,30,32,33,35,36n=21,24,26,27,29,30,32,33,35,36, now have stored in-degree-cube DRATs.

Exact orders with stored in-degree-cube DRATs now include every leftover hole through n=152n=152.

First remaining hole: n=153n=153, δ+=51\delta^+=51.