#18948: Strongly Regular Graphs database
---------------------------------+----------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Nathann Cohen | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+----------------------------
Changes (by ncohen):
* status: new => needs_review
Old description:
> This ticket implements a new module names `strongly_regular_db` that lets
> us build one example of strongly regular graph, given four integer
> parametes (v,k,lambda,mu).
>
> It uses Andries Brouwer's database to return more meaningful non-
> existence results, and help us find which constructions are missing from
> the database.
>
> With a bit of luck (and time, and work) it would be great if we could
> reproduce all SRG that are known to exist!
>
> The module has a simple structure:
>
> has a simple structure:
>
> - A `seems_feasible(v,k,l,mu)` function that performs the basic
> artihmetic
> checks to figure out if `(v,k,l,mu)` is realizable. The
> 'apparently_feasible_parameters(n)` returns the lists of all parameters
> that
> pass these tests for v<n. When n=1301, the set of parameters it returns
> is
> precisely those that appear on your database (this is checked in the
> code).
>
> - Several functions (is_paley, is_johnson, ...) test if a given set of
> parameters (v,k,l,mu) can be realized with a graph of the corresponding
> family
> (a Paley graph, a Johnson graph, ...). If they can, they return the
> parameters
> of that graph so that it can be built easily.
>
> - The main function `strongly_regular_graph` can be called in two ways:
>
> - `strongly_regular_graph(v,k,l,mu,existence=True)` answers True if
> such a
> graph is known to exists, False if it is known to be infeasible, and
> Unknown
> otherwise.
>
> - `strongly_regular_graph(v,k,l,mu)` attempts to build and return the
> requested graph, and returns a meaningful exception if it cannot.
>
> This branch also updates the package 'graphs', which now ships the
> database in json format.
>
> Nathann
New description:
This ticket implements a new module names `strongly_regular_db` that lets
us build one example of strongly regular graph, given four integer
parametes (v,k,lambda,mu).
It uses Andries Brouwer's database to return more meaningful non-existence
results, and help us find which constructions are missing from the
database.
With a bit of luck (and time, and work) it would be great if we could
reproduce all SRG that are known to exist!
The module has a simple structure:
has a simple structure:
- A `seems_feasible(v,k,l,mu)` function that performs the basic artihmetic
checks to figure out if `(v,k,l,mu)` is realizable. The
'apparently_feasible_parameters(n)` returns the lists of all parameters
that
pass these tests for v<n. When n=1301, the set of parameters it returns
is
precisely those that appear on your database (this is checked in the
code).
- Several functions (is_paley, is_johnson, ...) test if a given set of
parameters (v,k,l,mu) can be realized with a graph of the corresponding
family
(a Paley graph, a Johnson graph, ...). If they can, they return the
parameters
of that graph so that it can be built easily.
- The main function `strongly_regular_graph` can be called in two ways:
- `strongly_regular_graph(v,k,l,mu,existence=True)` answers True if such
a
graph is known to exists, False if it is known to be infeasible, and
Unknown
otherwise.
- `strongly_regular_graph(v,k,l,mu)` attempts to build and return the
requested graph, and returns a meaningful exception if it cannot.
This branch also updates the package 'graphs', which now ships the
database in json format.
http://www.steinertriples.fr/ncohen/tmp/graphs-20150724.tar.bz2
Nathann
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18948#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
