Abstract
dc:description.abstractIn 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 × 8Rights
dc:rights- Statement dc:rights
-
- © Robert Jacobs
Identifiers
dc:identifier.*- Identifier
- https://scholarscompass.vcu.edu/etd/7767