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, 2-graphs and oriented 2-graphs. New results from it can be found in our new paper.
Flagmatic is a tool for computing exact and approximate upper bounds on 3-graph Turán densities and H-densities, developed by Emil R. Vaughan as part of joint work with Victor Falgas-Ravry (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 semi-definite program solver CSDP is required. For the computation of exact results, Sage is required. Sage is not needed if only approximate floating-point 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 human-readable 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 3-graph on the vertex set [5] with edges 123, 124 and 345. The notation 5.8 means the set of 3-graphs on 5 vertices with 8 edges.
All results marked as new are due to Falgas-Ravry and Vaughan (2011).
| Density result | Extremal graph | Discovered by | |
| π (K4–, 5:123124345) = 2/9 | Blowup of a 3-edge | Bollobás (1974) | transcript certificate |
| π (5:123124345) = 2/9 | Blowup of a 3-edge | Frankl and Füredi (1983) | transcript certificate |
| π (K4–, induced 4.1, induced C5) = 2/9 | Blowup of a 3-edge | Attributed to Mubayi in Razborov (2010) | transcript certificate |
| π (K4–, F3,2 , C5) = 12/49 | H7 blowup | new | transcript certificate |
| π (K4– , induced 4.1) = 5/18 | H6 blowup | Frankl and Füredi (1984) | transcript certificate |
| π (K4– , induced 5.1) = 5/18 | H6 blowup | Baber (2011), private communication | transcript certificate |
| π (K4– , F3,2) = 5/18 | H6 blowup | new | transcript certificate |
| π (F3,2, induced K4–) = 3/8 | K4 blowup | new | transcript certificate |
| π (F3,2, induced 5.6) = 3/8 | K4 blowup | new | transcript certificate |
| π (F3,2, 5:123124125134135145) = 3/8 | K4 blowup | new | transcript certificate |
| π (F3,2, 6:123124125126134135136145146156) = 3/8 | K4 blowup | new | transcript certificate |
| π (F3,2) = 4/9 | 3:122123133 blowup | Füredi, Pikhurko and Simonovits (2003) | transcript certificate |
| π (K4 , C5, induced 4.1) = 4/9 | 3:122123133 blowup | Attributed to Mubayi in Razborov (2010) | transcript certificate |
| π (K4 , induced 4.1) = 5/9 | 3:123112223331 blowup | Razborov (2010) | transcript certificate |
| π (K5 , induced 5.8) = 3/4 | Balanced bipartite graph | new | transcript certificate |
| π (F3,3) = 3/4 | Balanced bipartite graph | Mubayi and Rödl (2002) and independently by J. Goldwasser | transcript certificate |
| π (H6) = π (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: Kn denotes the complete 3-graph on n vertices, K4– is the 3-graph on 4 vertices with 3 edges, H6 = 6:123234345451512136246356256146, H7 = 7:124137156235267346457653647621542517431327, C5 = 5:123234345451512, F3,2 = 5:123145245345, F3,3 = 6:123145146156245246256345346356.
| Result | Conjectured | Lower bound | |
| π (K4–, C5) ≤ 0.251073 | 1/4 | Iterated blowup of a 3-edge | transcript certificate |
| π (K4–, L5, F3,2) ≤ 0.255889 | 1/4 | Geometric: see Frankl and Füredi (1984), Falgas-Ravry and Vaughan (2011) | transcript certificate |
| π (K4–, L5) ≤ 0.258295 | 1/4 | Many: see Frankl and Füredi (1984), Falgas-Ravry and Vaughan (2011) | transcript certificate |
| π (K4–) ≤ 0.286889 | 2/7 | Iterated blowup of H6 (Frankl and Füredi, 1984) | transcript certificate |
| π (C5, 5.7) ≤ 0.464714 | 2√3-3 | Unbalanced Blowup of 2:112, iterated inside part 2 (Mubayi and Rödl, 2002) | transcript certificate |
| π (5.7) ≤ 0.465558 | 2√3-3 | Unbalanced Blowup of 2:112, iterated inside part 2 (Mubayi and Rödl, 2002) | transcript certificate |
| π (C5) ≤ 0.468287 | 2√3-3 | Unbalanced Blowup of 2:112, iterated inside part 2 (Mubayi and Rödl, 2002) | transcript certificate |
| π (J4, K4) ≤ 0.479371 | transcript certificate |
||
| π (J4) ≤ 0.504081 | 1/2 | Iterated blowup of the complement of the Fano plane (Bollobás, Leader and Malvenuto, 2011) | transcript certificate |
| π (K4) ≤ 0.561666 | 5/9 | Many: (Turán, 1941; Kostochka, 1982; Brown, 1983; Fon der Flass, 1988; Frohmader, 2008) | transcript certificate |
| π (K5) ≤ 0.769533 | 3/4 | Many: see Sidorenko (1995) | transcript certificate |
Note:
L5 = 6:123134145156162,
J4 = 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 Falgas-Ravry and Vaughan (2012).
| Density result | Extremal graph | Discovered by | |
| πK4 (F3,2) = 3/32 | Blowup of K4 | new | transcript certificate |
| π4.2 (K4–, F3,2, C5) = 4/9 | Blowup of 3:123 | new | transcript certificate |
| π4.2 (F3,2, C5) = 9/16 | Blowup of K4 | new | transcript certificate |
| π4.2 (K4–, F3,2) = 5/9 | Blowup of H6 | new | transcript certificate |
| πK4– (K4) = 16/27 | Blowup of 3:112223331123 | new | transcript certificate |
| πK4– (F3,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 Falgas-Ravry 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 (C5) ≤ 0.423592 | 4 - 6( (√2+1)1/3 - (√2-1)1/3 ) | Unbalanced iterated blowup of 2:112 | transcript certificate |
| π4.2 (K4–, C5) ≤ 0.461645 | 6/13 | Balanced iterated blowup of a 3-edge. | transcript certificate |
| π4.1 (F3,2) ≤ 0.514719 | 4/9 | Balanced blowup of 3:112223331 | transcript certificate |
| π4.2 (K4–) ≤ 0.558378 | 24/43 | Balanced iterated blowup of H6. | transcript certificate |
| π4.2 (C5) ≤ 0.583852 | 4/7 | Balanced iterated blowup of K4 | transcript certificate |
| π4.2 (F3,2) ≤ 0.627732 | 9/16 | Balanced blowup of K4 | 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 Falgas-Ravry and Vaughan (2011). A paper is in preparation.
| Density result | Extremal graph | Discovered by | |
| πS3 (∅) = 2√3-3 | Take two vertex sets, A and B, where |B|=√3|A|, add all edges from A to B. Iterate inside A. | new | transcript certificate |
| πS4 (∅) = 1-9x2 where x is the real root of 3X3 + 3X2 + 3X - 1. | Take two vertex sets, A and B, where |B|=x|A|, 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 C4. (Sperfeld, 2011) | transcript certificate |
| πP3 (∅) ≤ 0.400016 | 2/5 | Iterated blowup of C4. (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 (K3) = 24/625 | Blowup of C5. | Grzesik, 2011 and Hatami, Hladký, Král, Norine and Razborov, 2011 | transcript certificate |
| πK1,1,2 (∅) = 72/125 | Blowup of K5. | Hirst, 2011 | transcript certificate |
| Result | Conjectured | Lower bound | |
| πC5 (∅) ≤ 0.03846157 | 1/26 (≈0.03846154) | Iterated blowup of C5. | transcript certificate |
| πP4 (∅) ≤ 0.204513 | Best lower bound is a blow-up of QR(17) (Exoo). | transcript certificate |
|
| π-minK4 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 |
