Objects, Invariants, and Properties for Graph Theory (OIP-GT)
OIP-GT is a set of files that contain:
The ostensible goal of this project is to encode all of graph theory in an accessible repository. Why?:
The final point above is the most exciting one! Combining our growing repository of graph theory knowledge with automated conjecturing software has shown promise as a tool to develop potential new theorems which might not otherwise be found (see below section for examples and references).
GitHub has proven a valuable tool for this project.
For one, it enables us to share this repository with a growing community of researchers. Ideally, researchers can use this repository to generate and test new conjectures. Then, researchers will contribute their findings either as counterexamples (graphs not previously in OIP-GT) or as theorems (with citations, when a conjecture is proven).
Second, it enables us to recruit students. Some of these students have interests in computer science, rather than math, and this project is a tool to bridge these fields. We have organized several summer workshops, each with a particular focus in graph theory, where students program, conjecture, and prove/disprove as a group. These efforts spur growth in OIP-GT much faster than we could produce alone.
📔 See https://arxiv.org/abs/1801.01814 for a more extensive introduction to the motivations for this project, past workshops, some of the results produced with OIP, and a history of efforts in automated conjecturing.
📔 See https://www.sciencedirect.com/science/article/pii/S0004370215001575 for a description of the CONJECTURING program’s algorithm.
We’ve written the below instructions so that anybody can use OIP-GT. This is a math project. We hope to recruit mathematicians, no matter how programming-phobic they are!
If you have trouble getting started, please contact us (see Maintained by at the end). If you find a specific problem that means OIP-GT doesn’t work on your system, please submit an Issue (see Reporting bugs below).
The primary language used to interact with OIP-GT is Sage. For those familiar with Python, Sage is Python 2 with many built-in libraries and some syntactic sugar.
Even if you don’t know Python, the below instructions should be detailed enough to get you started! There are links to Sage and Python tutorials below.
Users may also find it helpful to know about git, GitHub, and working in the shell/terminal. This isn’t required for most usage, but it helps when problem-solving and if you’d like to contribute to the repository.
You can run Sage and OIP-GT on any machine and in any environment you’d like! - with the following caveats and advice:
For users less experienced with setting up and managing programming environments, you might consider using the online computing environment CoCalc, which comes preinstalled with Sage and many other features. CoCalc is run by the developers of Sage.
However, CoCalc is far from perfect. Resources are limited for users on the free tier. In particular, CoCalc’s free tier does not allow remote internet resources, so you’ll have to add additional files by first downloading them to your machine and then uploading them to CoCalc. The paid tiers do offer more features, but even with those features, CoCalc will not be ideal for advanced users who want to run large-scale computations.
Windows users may find things difficult locally. Some software, including git, just works more easily on Unix systems. And, CONJECTURING currently requires users to build using make. This is possible to do on Windows, but you’ll have to do some googling (maybe you can use Linux on Windows). If you’d prefer not to deal with these challenges, then you might want to find a Unix environment to use (virtualize Linux with VirtualBox, or ssh into a remote server provided by your university), or using CoCalc might be a good option.
Note that if you use a remote server, such as a shared computing environment at your university, you may need to contact your sysadmin for help installing some software. Also, when running Sage remotely using only a terminal/CLI, you may lose the ability to use the awesome function
someGraph.show()
which draws a picture of given graph object. In this case, a combination of running Sage locally and remotely, or remotely and on CoCalc, may be a good option.
To set up Sage, either:
As mentioned above, the primary purpose for OIP-GT is automated conjecturing. Of course, you’re free to use the data in OIP-GT in other ways too.
We designed OIP-GT with the program CONJECTURING (available on GitHub) by Nico Van Cleemput in mind.
To install CONJECTURING, you can follow their instructions for installing CONJECTURING as a Sage package. This installs the program as a package for all users on the machine, accessible from any working directory, and will probably require admin privileges (you cannot get admin privileges on CoCalc).
For CoCalc users and for first-time users who would prefer a simpler process, you can set up CONJECTURING by following these steps:
sage. Copy conjecturing.py out of sage into whatever directory you plan to work in later.c. As described above, this may not be simple to do on Windows. For Unix (including CoCalc) users:
ls to list files in your current folder. Use the command cd someFolderName to change into someFolder. Repeat this until you’re in the c folder.make.build inside of c. Copy the file expressions from build into whatever directory you plan to work in later.To build the source files, open a terminal and cd to the root OIP directory. Then, run make. This should create a new directory named build. Copy all of the files from build into the directory you plan to work in. You can do this by running cp build/* someDirectory, where someDirectory is wherever you plan to work.
The above process takes the individual files containing graphs / Objects, Properties, Invariants, etc. and builds a single file gt.sage. To use OIP-GT, load gt.sage. To contribute to OIP-GT, edit the individual files.
See the links to additional examples and documentation after this section for more help.
The below examples assume that gt.sage and the other files you downloaded above are located in your current working directory. If not, then either copy the files, use cd, or use os.chdir("dirName").
To start, load the different components:
load("conjecturing.py")
load("gt.sage")
load("gt_precomputed_database.sage")
Note that the OIP-GT GitHub repository contains lists of graphs that are not by default included in the release download. You can download some additional lists (ex. a list of all maximal triangle-free graphs up to order 16) from the Objects directory on GitHub. These are either loaded with a command like
load("dimacsgraphs.sage")
or by following the instructions in the file, as in the case of mtf_graphs.sage.
The graphs in gt.sage are all in the list all_graphs.
You can find graphs which meet some criteria by running something like
myGraphs = [g for g in all_graphs if g.order() < 20 and g.is_hamiltonian()] # All Hamiltonian graphs of order less than 20.
myGraphs2 = [g for g in all_graphs if is_two_connected(g)] # All the 2-connected graphs
Note that when we say “All the 2-connected graphs”, we do not mean “all of the 2-connected graphs in the universe”; we only mean a subset of the graphs that we have programmed into gt.sage.
To check whether a graph isomorphic to a particular graph is in some list, use the function
does_graph_exist(someGraphObject, someList)
which will print the names of any graphs isomorphic to someGraphObject and return a Boolean.
You can find many graph generators built-in to the Sage graphs package. These work like
myGraph = graphs.BullGraph()
myGraph2 = graphs.CompleteGraph(5)
Graph properties are functions which take a graph as input and return True or False.
Some properties are built-in to Sage. These are part of the Graph class and are called like
myGraph.is_hamiltonian()
myGraph.is_planar()
We have many more properties built-in to gt.sage. These functions are called like
has_star_center(myGraph)
is_two_connected(myGraph)
Here are some lists of properties built-in to gt.sage:
properties
efficiently_computable_properties
intractable_properties
sage_properties
The list properties contains all the built-in properties, and these are the properties we have precomputed values for. The list efficiently_computable_properties are properties we have identified as “efficient”, usually meaning polynomial-time complexity; intractable_properties are all other properties. The list sage_properties is the subset of properties which are functions from the Graph class.
Graph invariants are functions which take a graph as input and return a number.
Some invariants are in to Sage. These are part of the Graph class and are called like
myGraph.order()
myGraph.size()
We have many more invariants built-in to gt.sage. These functions are called like
max_degree(myGraph)
independence_number(myGraph)
Here are some lists of invariants in to gt.sage:
all_invariants
efficient_invariants
intractable_invariants
sage_efficient_invariants
sage_intractable_invariants
The list all_invariants contains all the built-in invariants, and these are the invariants we have precomputed values for. The list efficient_invariants are the invariants we have identified as “efficient”, usually meaning polynomial-time complexity; intractable_invariants are all other invariants. The lists sage_efficient_invariants and sage_intractable_invariants are the subsets which are functions from the Sage Graph class.
Running the conjecturing program is simple. Just make sure that you have loaded conjecturing.py and then run
myGraphs = [g for g in all_graphs[0:20] if g.order() < 40] # Picks a list of small graphs from the beginning of all_graphs
conjs = propertyBasedConjecture(myGraphs, efficiently_computable_properties[0:10], 0, sufficient=True)
for c in conjs:
print c
Any conjecture printed out will be true for all input graphs and properties. But, whether it’s in general is left for you to prove or disprove.
If you were conjecturing on invariants, the command would be
conjs = conjecture(someGraphs, someInvariants, mainInvariant, upperBound=True)
In the first command, mainProperty is set to 0. In the second command, mainInvariant is not yet set. You should set these values to the index of the property/invariant you are want conditions or bounds on. For example, the first command finds sufficient conditions for the first property in the list efficiently_computable_properties[0:10] (which was is_regular when I ran it). If you’d like conditions related to the second property in the list, whatever it happens to be, you would pass 1.
Note that in the above two commands, you can set the sufficient and upperBound parameters to True or False. They both default to True. If set to False, then conjectures will be made for necessary conditions or for lower bounds, respectively.
Besides setting the list of functions to analyze and the function of interest, there is one other way to introduce a condition into your conjectures. For example, if I want a bound on the independence number of Hamiltonian graphs, it may not be immediately obvious how to make CONJECTURING consider both independence number (invariant) and Hamiltonicity (property). Here, if the list of someGraphs you pass contains only Hamiltonian graphs, then any conjecturing bounds will have the implicit qualifier “If the graph is Hamiltonian, then…”.
The process of conjecturing is relatively fast, with the bottleneck usually being the computation of each function on each graphs. See Add precompute values to conjecturing below for one way to speed things up. Another way to reduce the time to conjecture is to reduce the size of the inputs. One heuristic we have found useful is to conjecture on a relatively small list of graphs, select which conjectures we find interesting or viable, and then (usually, quickly) search for counterexamples in the full list of graphs.
One final note concerning pedantic cases: we encourage you not to include the empty graph, Graph(0), Graph(1), or any other possibly frustrating graph in your conjecture input. We have attempted to consider these cases when defining the functions in gt.sage. However, since there is often a lot of disagreement in these cases (is the empty graph complete? Hamiltonian? 2-regular?), passing them as input may prevent CONJECTURING from making some otherwise viable conjectures.
For more help with CONJECTURING, we encourage you to run the commands
conjecture?
propertyBasedConjecture?
so you can see the full list of parameters to each function.
Conjectures are most interesting when they improve on already known results.
The definition of “improve” is important here. First consider properties. If we are looking for sufficient conditions C that imply property P, the CONJECTURING program will only output a conjecture if the number of graphs implied to be P increases from what is already implied by other theory. Similarly, if we are looking for necessary conditions C that are implied by property P, a conjecture will be made only if the number of graphs with conditions necessary for P would decrease.
In the case of invariants, the definition of “improve” is more obvious, as any inequality which is tighter/closer to the observed/known results than current theory is.
So, as you add theorems to your conjecturing, be careful of what we call “bingos”. If your property theorems already characterize all of the graphs, or your invariant theorems reach equality, then the program will not make any new conjectures. In these cases, you could add more graphs. You might also remove functions which are already well-described by theory, and focus on other relationships; for example, if looking for invariant conjectures with complete graphs, I would not include both size and order in my list of invariants.
For properties, set the theory parameter to a list of properties which return a Boolean which imply the main property when True (are implied to be True when the main property is True) when when for sufficient (necessary):
propertyBasedConjecture(objects, properties, mainProperty, theory=listofThoerems)
For invariants, set the theory parameter to a list of functions which return known bounds on the main invariants:
conjecture(objects, invariants, mainInvariant, theory=listOfTheorems)
There are some theorems built-in to gt.sage. Again, these are just various functions, some sorted into various lists. Find a list of these theorems here.
Make sure that you have loaded gt_precomputed_database.sage and that gt_precomputed_database.db is in the current working directory.
For properties, run the conjecture as you normally would, but setting the precomputed parameter as:
precomputedDictionary = precomputed_properties_for_conjecture()
propertyBasedConjecture(objects, properties, mainProperty, precomputed=precomputedDictionary)
For invariants, run the conjecture as you normally would, but setting the precomputed parameter as:
precomputedDictionary = precomputed_invariants_for_conjecture()
conjecture(objects, invariants, mainInvariant, precomputed=precomputedDictionary)
If the values for the given graphs for the given functions exist, then this will help massively speed up the conjectures.
Not all values for all graphs and functions have been precomputed, especially for larger graphs and slower functions. To check or filter by what has been computed, use commands like
precomputed = properties_as_dict()
g_key = myGraph.canonical_label(algorithm='sage').graph6_string() # Values are stored according to graph's **canonical** graph6 string.
print g_key in precomputed # Check if the graph exists at all in the precomputed database
print someProperty.__name__ in precomputed[g_key] # Check if the value for some property has been computed for the graph.
The same commands will work for invariants, if properties_as_dict is replaced by invariants_as_dict.
If you would like to computed additional values, either for graphs and functions combinations we have neglected, or for graphs and functions you have added yourself, then use the following functions.
In the below functions, you specify the list of functions and graphs to compute, and the number of seconds to spend on each combination before timing out and moving on.
update_invariant_database(someinvariants, graphs, timeout=60)
update_property_database(someProperties, graphs, timeout=60)
Keep in mind that the graphs and functions passed to the update methods must be unique. In particular, the no graphs can be isomorphic to each other.
If you would to contribute your computations to the OIP-GT repository, you will need to use the below command to dump the entire gt_precomputed_database.db file into a collection of individual .sql files. For further instructions on contributing, see Contributing below.
dump_database("filePathWhereToDump")
Sage and OIP-GT, from the command prompt:
? or ?? after any command will display documentation and examples. For example,
has_star_center?
or
Graph.is_hamiltonian?
Python, from the command prompt (see links to tutorials above for other questions):
help(object) to get information on any Python object (the single ? above is just a shorthand version of help). For example,
help(print)
help([1,2,3])
Sage, online documentation:
graphs.SomeGraph(): http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html.Graph package, with a list of built-in properties and invariants called as someGraph.is_some_property(): http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.htmlOIP-GT, online:
Note: Please don’t file an issue to ask a question. See Maintained by below for contact information.
Have you found a bug / problem with OIP-GT 🐞🐛? Do you have a suggestion for an improvement ✨? We track both as GitHub issues.
Note that improvements / enhancements may include requests for new functions, requests to add graphs, suggestions for improving usability, documentation, or reliability, and more.
Keep in mind that we have a small team, so be sure to describe the impact of your bug (is it critical, or just bothersome?) / why your suggestion is important (how many Fields Medals will this result in?). If you’d like things done more quickly, see below to see how YOU can contribute the code.
Contributions can include resolving any open issue, such as programming a new property, adding precomputed values to the database, improving documentation, and more.
Everybody is welcome to contribute! If you’re not sure where to start, please contact us. We want to get more researchers / developers involved in contributing to OIP-GT. There are plenty of “beginner” issues available.
To contribute, you’ll need to be familiar with GitHub pull requests and with programming - although the amount and type of programming may be minimal, depending on the issue. You can use the tutorials linked to above in Getting Started.
The basic process is (more details in our Contributing Guidelines):
Contact ✉️:
Current maintainers 🔨🔧🔩:
Past significant contributions by 👻: