Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

Combinatorics on Path Connections of a Rectangular Graph

Booth Id:



Finalist Names:
Geisler, Emil (School: Bountiful High School)

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 Won:
National Security Agency Research Directorate : Honorable Mention Mathematics