This repository contains the slides and additional material of the talk "Bounds for the Number of Partitions of a Graph " by Fabian Ball and Andreas Geyer-Schulz that was held at the European Conference on Data Analysis on Match 19, 2019 in Bayreuth, Germany.
Just the slides of the talk.
We know from combinatorics that the number of partitions of a set of
Our contribution provides examples of the possible partitions of very small graphs (
This folder contains several Python scripts. Run them with Python3 (some of them are also compatible with Python2). You will need the following external libraries (not every script needs every one, if you want to differentiate, have a look at the beginning of each script):
future
networkx
sympy
pandas
requests
beautifulsoup4
matplotlib
The scripts can be executed in the following logical order:
download_smallgraphs.py
: This wil download the small graphs from http://www.graphclasses.org/smallgraphs.htmlsearchspace.py
: Enumerate the searchspaces of the small graphsplot_exp_vs_bell.py
: Create plots that relate the upper and lower bound of the total number of partitions of a graphplot_lb_vs_Snk.py
: Create plots that relate the upper and lower bound of the number of k-partitions of a graph
All scripts can be executed as python3 <scriptname> -h
to get some information on how to call them.
The files estimation.py
and datastructures.py
contain code that is used by searchspace.py
.
The code is not intended to be used in a production environment!
This folder contains data that are the result of some of the above scripts.
All files prefixed input_
can be used as input for searchspace.py
.input_smallgraphs.csv
is the result of downloading the small graphs with download_smallgraphs.py
.
searchspace_sizes_all_graphs.csv
contains the exact number of partitions of all small graphs, whereas the subfolder searchspace_sizes_graphs
does contain the exact numbers of k-partitions for each graph individually. The former file can be used as input for plot_exp_vs_bell.py
; the latter files can be used as input for plot_lb_vs_Snk.py
.
Ball, Fabian. 2019. “Bounds for the Number of Partitions of a Graph.” Talk presented at the European Conference on Data Analysis 2019, Bayreuth, March 18. http://www.gfkl.org/ecda2019/.