Back to search

Virginia Commonwealth University

Paley Graphs, Prime Graphs, and Crossword Puzzles

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Systems Modeling and Analysis

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Jacobs, Robert D, Jr.
  • https://orcid.org/0009-0006-1551-5834
Contributors dc:contributor
  • Craig Larson
  • Neal Bushaw
  • Ghidewon Abay-Asmerom
  • Paul Brooks

Subjects

dc:subject × 8

Rights

dc:rights
Statement dc:rights
  • © Robert Jacobs

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Virginia Commonwealth University
Base URL
scholarscompass.vcu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Jacobs, Robert D, Jr.; https://orcid.org/0009-0006-1551-5834. Paley Graphs, Prime Graphs, and Crossword Puzzles. Dissertation thesis, https://doi.org/10.25772/YSHN-SC49