A tool for researchers in extremal graph theory.
flagmatic version 1.5.1 source

flagmatic version 1.5.1 Mac OS X binaries

Also available: User’s Guide, Mac OS X installation instructions
and the old version 1.0
source and
Mac OS X binaries.
Flagmatic version 1.5 has support for induced densities, 2graphs and oriented 2graphs. New results from it can be found in our new paper.
Flagmatic is a tool for computing exact and approximate upper bounds on 3graph Turán densities and Hdensities, developed by Emil R. Vaughan as part of joint work with Victor FalgasRavry (see our paper).
Flagmatic uses the flag algebra calculus of Razborov. For more details please see our paper, or Keevash (2011) (Section 7) or Baber and Talbot (2010) or Razborov (2010) or Razborov (2007).
Flagmatic is known to work on Linux and Mac OS X, and should work on other POSIX compliant systems. The semidefinite program solver CSDP is required. For the computation of exact results, Sage is required. Sage is not needed if only approximate floatingpoint bounds are required.
Below is a list of some of the results that Flagmatic can prove.
Each result is accompanied by a certificate, which contains sufficient information to be able to independently verify the result. The certificates are in JSON format and are humanreadable to some extent. To assist with the certificates we provide a Python script inspect_certificate.py, which can display information from the certificate.
The “transcript” links show how to use Flagmatic to reproduce the result. The “certificate” links are the certificates, some of which have been compressed to save disk space.
The notation 5:123124345 means the 3graph on the vertex set [5] with edges 123, 124 and 345. The notation 5.8 means the set of 3graphs on 5 vertices with 8 edges.
All results marked as new are due to FalgasRavry and Vaughan (2011).
Density result  Extremal graph  Discovered by  
π (K_{4}^{–}, 5:123124345) = 2/9  Blowup of a 3edge  Bollobás (1974)  transcript certificate 
π (5:123124345) = 2/9  Blowup of a 3edge  Frankl and Füredi (1983)  transcript certificate 
π (K_{4}^{–}, induced 4.1, induced C_{5}) = 2/9  Blowup of a 3edge  Attributed to Mubayi in Razborov (2010)  transcript certificate 
π (K_{4}^{–}, F_{3,2} , C_{5}) = 12/49  H_{7} blowup  new  transcript certificate 
π (K_{4}^{–} , induced 4.1) = 5/18  H_{6} blowup  Frankl and Füredi (1984)  transcript certificate 
π (K_{4}^{–} , induced 5.1) = 5/18  H_{6} blowup  Baber (2011), private communication  transcript certificate 
π (K_{4}^{–} , F_{3,2}) = 5/18  H_{6} blowup  new  transcript certificate 
π (F_{3,2}, induced K_{4}^{–}) = 3/8  K_{4} blowup  new  transcript certificate 
π (F_{3,2}, induced 5.6) = 3/8  K_{4} blowup  new  transcript certificate 
π (F_{3,2}, 5:123124125134135145) = 3/8  K_{4} blowup  new  transcript certificate 
π (F_{3,2}, 6:123124125126134135136145146156) = 3/8  K_{4} blowup  new  transcript certificate 
π (F_{3,2}) = 4/9  3:122123133 blowup  Füredi, Pikhurko and Simonovits (2003)  transcript certificate 
π (K_{4} , C_{5}, induced 4.1) = 4/9  3:122123133 blowup  Attributed to Mubayi in Razborov (2010)  transcript certificate 
π (K_{4} , induced 4.1) = 5/9  3:123112223331 blowup  Razborov (2010)  transcript certificate 
π (K_{5} , induced 5.8) = 3/4  Balanced bipartite graph  new  transcript certificate 
π (F_{3,3}) = 3/4  Balanced bipartite graph  Mubayi and Rödl (2002) and independently by J. Goldwasser  transcript certificate 
π (H_{6}) = π (6:234235145126136246346256356456) = π (6:234135145245126146346256356456) = π (6:234235145345136246346256356456) = 3/4 
Balanced bipartite graph  PhD thesis, R. Baber (2011)  transcripts 1 2 3 4 certificates 1 2 3 4 
Note: K_{n} denotes the complete 3graph on n vertices,
K_{4}^{–} is the 3graph on 4 vertices with 3 edges,
H_{6} = 6:123234345451512136246356256146,
H_{7} = 7:124137156235267346457653647621542517431327,
C_{5} = 5:123234345451512,
F_{3,2} = 5:123145245345,
F_{3,3} = 6:123145146156245246256345346356.
Result  Conjectured  Lower bound  
π (K_{4}^{–}, C_{5}) ≤ 0.251073  1/4  Iterated blowup of a 3edge  transcript certificate 
π (K_{4}^{–}, L_{5}, F_{3,2}) ≤ 0.255889  1/4  Geometric: see Frankl and Füredi (1984), FalgasRavry and Vaughan (2011)  transcript certificate 
π (K_{4}^{–}, L_{5}) ≤ 0.258295  1/4  Many: see Frankl and Füredi (1984), FalgasRavry and Vaughan (2011)  transcript certificate 
π (K_{4}^{–}) ≤ 0.286889  2/7  Iterated blowup of H_{6} (Frankl and Füredi, 1984)  transcript certificate 
π (C_{5}, 5.7) ≤ 0.464714  2√33  Unbalanced Blowup of 2:112, iterated inside part 2 (Mubayi and Rödl, 2002)  transcript certificate 
π (5.7) ≤ 0.465558  2√33  Unbalanced Blowup of 2:112, iterated inside part 2 (Mubayi and Rödl, 2002)  transcript certificate 
π (C_{5}) ≤ 0.468287  2√33  Unbalanced Blowup of 2:112, iterated inside part 2 (Mubayi and Rödl, 2002)  transcript certificate 
π (J_{4}, K_{4}) ≤ 0.479371  transcript certificate 

π (J_{4}) ≤ 0.504081  1/2  Iterated blowup of the complement of the Fano plane (Bollobás, Leader and Malvenuto, 2011)  transcript certificate 
π (K_{4}) ≤ 0.561666  5/9  Many: (Turán, 1941; Kostochka, 1982; Brown, 1983; Fon der Flass, 1988; Frohmader, 2008)  transcript certificate 
π (K_{5}) ≤ 0.769533  3/4  Many: see Sidorenko (1995)  transcript certificate 
Note:
L_{5} = 6:123134145156162,
J_{4} = 5:123124125134135145.
These results have been obtained using an unreleased beta version of Flagmatic that has support for induced densities. All the following are due to FalgasRavry and Vaughan (2012).
Density result  Extremal graph  Discovered by  
π_{K4} (F_{3,2}) = 3/32  Blowup of K_{4}  new  transcript certificate 
π_{4.2} (K_{4}^{–}, F_{3,2}, C_{5}) = 4/9  Blowup of 3:123  new  transcript certificate 
π_{4.2} (F_{3,2}, C_{5}) = 9/16  Blowup of K_{4}  new  transcript certificate 
π_{4.2} (K_{4}^{–}, F_{3,2}) = 5/9  Blowup of H_{6}  new  transcript certificate 
π_{K4–} (K_{4}) = 16/27  Blowup of 3:112223331123  new  transcript certificate 
π_{K4–} (F_{3,2}) = 27/64  Blowup of 4:114224334124134234  new  transcript certificate 
π_{5.9} (∅) = 5/8  Balanced bipartite graph  new  transcript certificate 
π_{5.6} (∅) = 20/27  Blowup of 3:112223331122233311  new  transcript certificate 
π_{5.7} (∅) = 20/27  Blowup of 3:123111222333112223331  new  transcript certificate 
π_{4.2} (∅) = 3/4  Random geometric construction.  new  transcript certificate 
The following bounds are due to FalgasRavry and Vaughan (2012).
Result  Conjectured  Lower bound  
π_{C5} (∅) ≤ 0.198845  3/16  Random geometric construction.  transcript certificate 
π_{F3,2} (∅) ≤ 0.349465  A cubic irrational.  Unbalanced iterated blowup of 2:112222  transcript certificate 
π_{4.3} (C_{5}) ≤ 0.423592  4  6( (√2+1)^{1/3}  (√21)^{1/3} )  Unbalanced iterated blowup of 2:112  transcript certificate 
π_{4.2} (K_{4}^{–}, C_{5}) ≤ 0.461645  6/13  Balanced iterated blowup of a 3edge.  transcript certificate 
π_{4.1} (F_{3,2}) ≤ 0.514719  4/9  Balanced blowup of 3:112223331  transcript certificate 
π_{4.2} (K_{4}^{–}) ≤ 0.558378  24/43  Balanced iterated blowup of H_{6}.  transcript certificate 
π_{4.2} (C_{5}) ≤ 0.583852  4/7  Balanced iterated blowup of K_{4}  transcript certificate 
π_{4.2} (F_{3,2}) ≤ 0.627732  9/16  Balanced blowup of K_{4}  transcript certificate 
π_{4.3} (induced 4.1) ≤ 0.650930  Balanced blowup of 3:123112223331 gives 16/27.  transcript certificate 

π_{4.3} (∅) ≤ 0.651912  Balanced blowup of 3:123112223331 gives 16/27.  transcript certificate 
These results have been obtained using an unreleased beta version of Flagmatic that has support for oriented graphs.
Results marked as new are due to FalgasRavry and Vaughan (2011). A paper is in preparation.
Density result  Extremal graph  Discovered by  
π_{S3} (∅) = 2√33  Take two vertex sets, A and B, where B=√3A, add all edges from A to B. Iterate inside A.  new  transcript certificate 
π_{S4} (∅) = 19x^{2} where x is the real root of 3X^{3} + 3X^{2} + 3X  1.  Take two vertex sets, A and B, where B=xA, add all edges from A to B. Iterate inside A.  new  transcript certificate 
Result  Conjectured  Lower bound  
π_{C4} (∅) ≤ 0.095239  2/21  Iterated blowup of C_{4}. (Sperfeld, 2011)  transcript certificate 
π_{P3} (∅) ≤ 0.400016  2/5  Iterated blowup of C_{4}. (Sperfeld, 2011)  transcript certificate 
These results have been obtained using an unreleased beta version of Flagmatic that has support for graphs.
Density result  Extremal graph  Discovered by  
π_{C5} (K_{3}) = 24/625  Blowup of C_{5}.  Grzesik, 2011 and Hatami, Hladký, Král, Norine and Razborov, 2011  transcript certificate 
π_{K1,1,2} (∅) = 72/125  Blowup of K_{5}.  Hirst, 2011  transcript certificate 
Result  Conjectured  Lower bound  
π_{C5} (∅) ≤ 0.03846157  1/26 (≈0.03846154)  Iterated blowup of C_{5}.  transcript certificate 
π_{P4} (∅) ≤ 0.204513  Best lower bound is a blowup of QR(17) (Exoo).  transcript certificate 

πmin_{K4 or K4} (∅) ≥ 0.029434  Best upper bound is 1/33 (=0.03030...) due to Thomason. Our bound improves 0.028747 due to Sperfeld, 2011.  transcript certificate 