Combinatorics on Path Connections of a Rectangular Graph

Overview

Graph connectivity is a critical concept for a variety of applications in both pure and applied math. Identifying the connectivity of the graphs underlying neural networks, for example, would allow for improved analysis of multi-variable data. To increase our understanding in this area, this project seeks to explore the combinatorics on path connectivity of rectangular graphs. The problem is to define a function f(a,b) which returns the number of connected graphs in the given shape. In particular, this function acts on an ‘a’ by ‘b’ rectangular grid where every grid tile can be colored “on” or “off”. The function f(a,b) returns the number of grid colorings with a connection along adjacent “on” tiles beginning from an “on” tile in the leftmost column to an “on" tile in the rightmost column. A closed form solution was found directly for f(a,1), f(1,b), and f(2,b). Casework and recursion of these base cases allowed for the construction of f(a,2), f(3,b), and f(a,3). Further analysis yielded a methodology for finding the complexity of f(a,b): O(f(k,b)) = r^b, where ‘r’ is a real number defined by constant ‘k’.

Awards (1)

• National Security Agency Research Directorate : Honorable Mention Mathematics

Competition history

• ISEF 2018 Mathematics · Entry MATH026

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.