Sage Mathematical Software System

Mentors: Student: Meghana M Reddy

<p>The aim of the project is to code the linear time algorithm for partitioning a graph into 3-connected components and constructing the corresponding SPQR-tree of the graph. Further, this algorithm can be used as a subroutine for several other graph problems such as recognition of chordless graphs, hamiltonian cycle etc.</p>

Mentors: Student: Raghukul Raman

<p>This project aims at implementing basic algorithms for finding rational points on varieties. Classically algebraic variety is defined as the set of solutions of polynomial equations over a number field. A rational point of an algebraic variety is a solution of set of equations in the given field (rational field if not mentioned). Much of the number theory can be viewed as the study of rational point of algebraic varieties. Some of the great achievements of number theory amount to determining the rational points on particular curves. For example, Fermat’s last theorem is equivalent to the statement that for an integer n ≥ 3, the only rational point of the curve xn+yn=zn in P2 over Qare the obvious ones. Common variants of these question include determining the set of all points of V(K) of height up to some bound. The aim of this project is to implement some basic rational point finding algorithms (sieving modulo prime and Doyle Krumm Algorithm) and extend these to product_projective_space scheme.</p>

Mentors: Student: Filip Ion

<p>The following proposal detail some possible improvements of the coding theory component of SageMath. We aim to build databases of precomputed bounds and optimal examples of linear codes for each choice of parameters below a maximum range.</p>

Mentors: Student: Dario Asprone

<p>Currently SageMath checks for graph isomorphism through an internal package with a corresponding method, called <em>isomorphic</em> and contained in <strong>sage.groups.perm_gps.partn_ref.refinement_graphs</strong>. This method, in addition to being quite convoluted and without much documentation about its inner workings, was last updated in a significant manner in 2011.<br> The project aims at creating a new package which implements an efficient in practice heuristic method to check if two graphs are isomorphic, using one of the members of the Weisfeiler-Lehman (WL) algorithm hierarchy. An attempt was made in the past at the same task (but with a narrower scope, limited to only implementing the second order version of the WL algorithm), but the code was found to contain a bug and was never implemented/removed from the codebase (see Trac #10482).<br> To the best of my knowledge, this would be the first working open-source implementation of k-WL, for k &gt; 1.</p>

Mentors: Student: Sai Harsh Tondomker

<p>In this project, our goal is to extend the graph theory library in Sage by implementing functionality to find triconnected subgraphs, which will partition an undirected graph into 3-connected components and the construction of the corresponding SPQR-tree. These modules can later be used as pre-processing for several graph problems such as Hamiltonian Cycle, traveling salesman problem.</p>