# flagmatic

A tool for researchers in extremal graph theory.

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.

### Some sharp bounds that Flagmatic can obtain (all are exact rational computations)

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.

### Some non-tight bounds that Flagmatic can obtain (all are exact rational computations)

 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.

### Some induced subgraph densities that Flagmatic can obtain (all are exact rational computations)

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

### Some oriented graph induced subgraph densities that Flagmatic can obtain (all are exact rational computations)

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

### Some graph results that Flagmatic can obtain (all are exact rational computations)

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