math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
15 stars 6 forks source link

Add NB counterexample graphs #366

Closed math1um closed 7 years ago

math1um commented 7 years ago

counterexamples Neal Bushaw found to a round of conjectured lemmas for proving the girth-theta conjecture:

`independence_number(x)` >= -average_distance(x) + ceil(lovasz_theta(x))
CE: Corrected 1st graph: Graph('epCpih@K}gSGIZfc?Rkf{EWtVKJTmJtWYl_IoDOKOikwDSKtbH\\fi_g`affO\\|Agq`WcLoakSLNPaWZ@PQhCh?ylTR\\tIR?WfoJNYJ@B{GiOWMUZX_puFP?')

independence_number(x) >= ceil(1/2*cvetkovic(x))
independence_number(x) >= 1/2*cvetkovic(x)
CE: Graph('Gvz~r{')

independence_number(x) >= -max_common_neighbors(x) + min_degree(x)
CE: Graph('eLvnv~yv{yJ~rlB^Mn|v^nz~V]mwVji}^vZf{\\\\nqZLfVBze}y[ym|jevvt~NNucret|~ejj~rz}Q\\~^an}XzTV~t]a]v}nx\\u]n{}~ffqjn`~e}lZvV]t_')

independence_number(x) >= max_degree(x) - order_automorphism_group(x)
CE: Graph('ETzw')

independence_number(x) >= -card_periphery(x) + matching_number(x)
CE: Graph('I~~~}~~~w')

independence_number(x) >= lovasz_theta(x)/radius(x)
CE: Graph('~?@A~~~~~~z~~~~~~~~^~~~~~z~~~~~~~~~~~~~~~v~~~v~~~~~~~~~~z~~~~~~~~^~~~~~~~~~}\~~}v~^~~}~~^~~~~~~~~~~~~^~~~~~~~~V~~~n~~n~~~~~~}~~|~}~~~~~~~~~~~~~~~~~~~~~vv~|~~~~~~~~~~~~~~~~~z~~w~~~~~~~~~~~~~~~~n~~~|~~~~~~~v~|~~~~~~~~~~}~|~r~V~~~n~~~~~~~~z~~}}~}~~~~vz~~z~~~z}~~~n~~~~~~~~~~~~n~~~~~~~z~~~~~~~~~~~~~~^~~~~~~~~~n~~]~~~~~n~~~}~~~~~~~~~~^~^~~~~}~~~~~~~~~~~z~~~~^~~~~~~w')

independence_number(x) >= matching_number(x) - order_automorphism_group(x) - 1
CE: Graph('I~~Lt~\Nw')

independence_number(x) >= card_positive_eigenvalues(x) - lovasz_theta(x)
CE: Graph('N^nN~~}Z~|}~~\~]zzw')

independence_number(x) >= card_negative_eigenvalues(x) - sigma_2(x)
CE: Graph('IOilnemjG')
math1um commented 7 years ago

And more:

independence_number(x) >= minimum(card_positive_eigenvalues(x),2*card_zero_eigenvalues(x))
CE: Graph('Hx~\\rnV')

independence_number(x) >= minimum(min_degree(x), floor(lovasz_theta(x))) has counterexample Graph('z@M@E?OYOSCPBTp?mOWaP_?W[OG[abE_?P[@?@REt?ggAAOH?N@?CATE\oE?WO@GOKu?LJ_??SDP@CIA?AFHCC?kZQMo@CkOGoiJSs`?g?oDJqC?S?qJSqA?GN]?OPd?cGHE?AOpE_c_O@kC_?DF@HGgJ?ygAACdcCMPA[d`SHE@?PqRE?CO_?CWO?H_b_EBoOKI@CWAadQ?eOO?oT_@STAWCCCMOK?A@?TsBoJa@?PGQ_CiKPC_@_iE_hL@ACAIJQDgOSG?G[cG_D[A_CbDKO[goBH_?S?')