Author ORCID Identifier

https://orcid.org/0009-0006-1551-5834

Defense Date

2024

Document Type

Dissertation

Degree Name

Doctor of Philosophy

Department

Systems Modeling and Analysis

First Advisor

Craig Larson

Second Advisor

Neal Bushaw

Third Advisor

Ghidewon Abay-Asmerom

Fourth Advisor

Paul Brooks

Abstract

In this paper, we will talk about many different mathematical concepts. We will prove theorems about Paley graphs, prime graphs, and crossword puzzles. It will be very fun.

The results in the section about Paley graphs include structure theorems about the subgraph induced by the quadratic residues, the subgraph induced by the non-residues and a few related subgraphs. The main is to better understand the “independence structure” of the Paley graph itself. No good upper bound on the independence number of Paley graphs is known. Theorems about these subgraphs, and various counts aim at future improvement of upper bounds for the independence number of these graphs. It also happens that, since these graphs are defined for 4k+1 primes, and the theorem of Fermat and Euler guarantees that these can be written uniquely as a sum of squares x^2+y^2, that these numbers interestingly appear in various counts and conjectures.

The results in the section about prime graphs include a graph-theoretic formula for the number of primes π(n) up to n in terms of the efficiently computable Lovasz theta function. We also provide a new proof of Staton’s theorem that every graph is an induced subgraph of some prime graph.

The section on crossword puzzles includes a new proof of Ferland's theorem that a "standard" 15*15 crossword puzzle can have no more than 96 words. The techniques developed in this section are then used to deduce a variety of results on crossword puzzle counts for puzzles of different sizes, symmetries, and minimum word lengths.

Comments

The most words in a 15*15 crossword puzzle is 96.

Rights

© Robert Jacobs

Is Part Of

VCU University Archives

Is Part Of

VCU Theses and Dissertations

Date of Submission

5-31-2024

Download

Share

COinS