Search

The first problem of the 2017 Putnam competition was to characterize a set of natural numbers closed under both the square-root map $n^2 \mapsto n$ and the "add 5 and square" map $ n \mapsto (n+5)^2$. We reframe this as a problem on an infinite directed graph, using this framing both to generalize the problem and its solution, as well as to determine the first appearance of each number in this set under a row-wise algorithm that outputs all its elements.

The question of characterizing the (finite) representable relation algebras in a ``nice" way is open. The class $\mathbf{RRA}$ is known to be not finitely axiomatizable in first-order logic. Nevertheless, it is conjectured that ``almost all'' finite relation algebras are representable. All finite relation algebras with three or fewer atoms are representable. So one may ask, Over what cardinalities of sets are they representable? This question was answered completely by Andr\'eka and Maddux (``Representations for small relation algebras,'' \emph{Notre Dame J. Form. Log.}, \textbf{35} (1994)); they determine the spectrum of every finite relation algebra with three or fewer atoms. In the present paper, we restrict attention to cyclic group representations, and completely determine the cyclic group spectrum for all seven symmetric integral relation algebras on three atoms. We find that in some instances, the spectrum and cyclic spectrum agree; in other instances, the spectra disagree for finitely many $n$; finally, for other instances, the spectra disagree for infinitely many $n$. The proofs employ constructions, SAT solvers, and the probabilistic method.

In this paper, we shed new light on the spectrum of the relation algebra we call $A_{n}$, which is obtained by splitting the non-flexible diversity atom of $6_{7}$ into $n$ symmetric atoms. Precisely, we show that the minimum value in $\text{Spec}(A_{n})$ is at most $2n^{6 + o(1)}$, which is the first polynomial bound and improves upon the previous bound due to Dodd \& Hirsch (\textit{J. Relational Methods in Computer Science} 2013). We also improve the lower bound to $2n^{2} + 4n + 1$, which is asymptotically double the trivial bound of $n^{2} + 2n + 3$. In the process, we obtain stronger results regarding $\text{Spec}(A_{2}) =\text{Spec}(32_{65})$. Namely, we show that $1024$ is in the spectrum, and no number smaller than 26 is in the spectrum. Our improved lower bounds were obtained by employing a SAT solver, which suggests that such tools may be more generally useful in obtaining representation results., Comment: 17 pages

In this paper, we consider relational structures arising from Comer's finite field construction, where the cosets need not be sum free. These Comer schemes generalize the notion of a Ramsey scheme and may be of independent interest. As an application, we give the first finite representation of $34_{65}$. This leaves $33_{65}$ as the only remaining relation algebra in the family $N_{65}$ with a flexible atom that is not known to be finitely representable. Motivated by this, we complement our upper bounds with some lower bounds. Using a SAT solver, we show that $33_{65}$ is not finitely representable on fewer than $24$ points, and that $33_{65}$ does not admit a cyclic group representation on fewer than $120$ points. We also employ a SAT solver to show that $34_{65}$ is not representable on fewer than $24$ points., Comment: Full version of paper that previously appeared in RAMiCS 2023

In this paper, we give an algorithm for detecting non-trivial 3-APs in multiplicative subgroups of $\mathbb{F}_p^\times$ that is substantially more efficient than the naive approach. It follows that certain Var der Waerden-like numbers can be computed in polynomial time., Comment: 8 pages, 2 figures. The proof of Theorem 2 follows closely the proof of Theorem 4 from arXiv:1609.01817

In this paper, we shed new light on the Flexible Atom Conjecture. We first give finite representation results for relation algebras $33_{37}, 35_{37}$, $77_{83}$, $78_{83}$, $80_{83}$, $82_{83}$, $83_{83}$, $1310_{1316}$, $1313_{1316}$, $1315_{1316}$, and $1316_{1316}$. Prior to our paper, only $83_{83}$ and $1316_{1316}$ were known to be finitely representable. We accomplish this by generalizing the notion of a relation algebra generated by a Ramsey scheme to the directed (antisymmetric) setting, and then showing that each of these algebras embeds into a finite directed (anti-)Ramsey scheme. The notion of a directed (anti-)Ramsey scheme may be of independent interest. We complement our upper bounds with some lower bounds. Namely, we show that any square representation of $31_{37}$ requires at least $14$ points, any square representation of $33_{37}$ requires at least $11$ points, and any square representation of $35_{37}$ requires at least $12$ points. Our technique adapts previous work of Alm, et. al. (Algebra Universalis 2022), in that we examine the combinatorial structure induced by the flexible atom.

An ordered graph $H$ on $n$ vertices is a graph whose vertices have been labeled bijectively with $\{1,...,n\}$. The ordered Ramsey number $r_<(H)$ is the minimum $n$ such that every two-coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $H$ such that the vertices in the copy appear in the same order as in $H$. Although some bounds on the ordered Ramsey numbers of certain infinite families of graphs are known, very little is known about the ordered Ramsey numbers of specific small graphs compared to how much we know about the usual Ramsey numbers for these graphs. In this paper we tackle the problem of proving non-trivial upper bounds on orderings of graphs on four vertices. We also extend one of our results to $n+1$ vertex graphs that consist of a complete graph on $n$ vertices with a pendant edge to vertex 1. Finally, we use a SAT solver to compute some numbers exactly., Comment: 14 pages. Updated paper with new SAT solver results

We develop a random model for relation algebras. We prove some preliminary results and pose questions that lay out a new direction of research.

In this note, we give two different proofs that relation algebra $52_{65}$ is representable over a finite set. The first is probabilistic, and uses Johnson schemes. The second is an explicit group representation over $ (\mathbb{Z}/2\mathbb{Z})^{10}$. We also give a finite representation of $59_{65}$ over $\mathbb{Z}/113\mathbb{Z}$ using a technique due to Comer.

We consider a variant on the Tetranacci sequence, where one adds the previous four terms, then divides the sum by two until the result is odd. We give an algorithm for constructing "initially division-poor" sequences, where over an initial segment one divides by two only once for each term. We develop a probabilistic model that suggests that "most" sequences are unbounded, and provide computational data to support the underlying assumptions of the model.

Proper relation algebras can be constructed using $\mathbb{Z}/p\mathbb{Z}$ as a base set using a method due to Comer. The cycle structure of such an algebra must, in general, be determined \emph{a posteriori}, normally with the aid of a computer. In this paper, we give an improved algorithm for checking the cycle structure that reduces the time complexity from $\mathcal{O}(p^2)$ to $\mathcal{O}(p)$.

In Alm-Hirsch-Maddux (2016), relation algebras $\mathfrak{L}(q,n)$ were defined that generalize Roger Lyndon's relation algebras from projective lines, so that $\mathfrak{L}(q,0)$ is a Lyndon algebra. In that paper, it was shown that if $q>2304n^2+1$, $\mathfrak{L}(q,n)$ is representable, and if $q<2n$, $\mathfrak{L}(q,n)$ is not representable. In the present paper, we reduced this gap by proving that if $q\geq n(\log n)^{1+\varepsilon}$, $\mathfrak{L}(q,n)$ is representable., Comment: 8 pages, 2 figures

In this paper, we discuss an improvement of an algorithm to search for primes $p$ and coset-partitions of Z/pZ* that yield Ramsey algebras over Z/pZ. We also prove an upper bound on the modulus p in terms of the number of cosets. We have, as a corollary, that there is no prime $p$ for which there exists a partition of Z/pZ* into 13 cosets that yields a 13-color Ramsey algebra. Thus A263308(13) = 0.

Many naturally occurring networks have a power-law degree distribution as well as a non-zero degree correlation. Despite this, most studies analyzing the robustness to random node-deletion and vulnerability to targeted node-deletion have concentrated only on power-law degree distribution and ignored degree correlation. This study looks specifically at the effect degree-correlation has on robustness and vulnerability in scale-free networks. Our results confirm Newman's finding that positive degree-correlation increases robustness and decreases vulnerability. However, we found that networks with positive degree-correlation are more vulnerable to random node-deletion than to targeted deletion methods that utilize knowledge of initial node-degree only. Targeted deletion sufficiently alters the topology of the network to render this method less effective than uniform random methods unless changes in topology are accounted for. This result indicates the importance of degree correlation in certain network applications., Comment: 7 pages

This is the author's 2004 Master's thesis at Iowa State University, done under the supervision of Roger D. Maddux. It provides a background in relation algebras. Three results from the literature are demonstrated in full: (i.) RRA is a variety. (ii.) RRA is not finitely based. (iii.) Any equational basis for RRA has infinitely many variables. We also give an elementary proof of Birkoff's variety theorem., Comment: 56 pages. Because the source code and packages are old, some of the diagrams are missing line segments. Iowa State University MS thesis, 2004

The chromatic number $\chi\left(\mathcal{E^2}\right)$ of the plane is known to be some integer between 4 and 7, inclusive. We prove a limiting result that says, roughly, that one cannot increase the lower bound on $\chi\left(\mathcal{E^2}\right)$ by pasting Moser Spindles together, even countably many., Comment: To appear in Australasian Journal of Combinatorics

We construct an edge-coloring of $K_{N}$ (for $N = 3432$) in colors red, dark blue, and light blue, such that there are no monochromatic blue triangles and such that the coloring satisfies a certain strong universal-existential property. The edge-coloring of $K_{N}$ depends on a cyclic coloring of $K_{17}$ whose two color classes are $K_{4}$-, $K_{4,3}$-, and $K_{5,2}$-free. This construction yields the smallest known representation of the relation algebra $32_{65}$, reducing the upper bound from 8192 to 3432.

It is known that the connected graphs that are $p$-good for all $p$ are the trees. In this paper, we ask which ordered trees are order-$p$-good for all $p$., Comment: 8 pages

In this paper we study Ramsey numbers for trees of diameter 3 (bistars) vs., respectively, trees of diameter 2 (stars), complete graphs, and many complete graphs. In the case of bistars vs. many complete graphs, we determine this number exactly as a function of the Ramsey number for the complete graphs. We also determine the order of growth of the bipartite $k$-color Ramsey number for a bistar., Comment: 8 pages, 6 figures

We prove that any equational basis that defines RRA over wRRA must contain infinitely many variables. The proof uses a construction of arbitrarily large finite weakly representable but not representable relation algebras whose "small" subalgebras are representable., Comment: To appear in Review of Symbolic Logic

Given $X\subseteq \mathbb{Z}_N$, $X$ is called a \emph{cyclic basis} if $(X+X)\cup X=\mathbb{Z}_N$, \emph{symmetric} if $x\in X$ implies $-x \in X$, and \emph{sum-free} if $(X+X)\cap X=\varnothing$. We ask, for which $m$, $N\in\mathbb{Z}^+$ can the set of non-identity elements of $\mathbb{Z}_N$ be partitioned into $m$ symmetric sum-free cyclic bases? If, in addition, we require that distinct cyclic bases interact in a certain way, we get a proper relation algebra called a Ramsey algebra. Ramsey algebras (which have also been called Monk algebras) have been constructed previously for $2\leq m\leq 7$. In this manuscript, we provide constructions of Ramsey algebras for every positive integer $m$ with $2\leq m\leq 400$, with the exception of $m=8$ and $m=13$., Comment: 14 pages, 2 figures

We consider the chromatic numbers of unit-distance graphs of various annuli. In particular, we consider radial colorings, which are "nice" colorings, and completely determine the radial chromatic numbers of various annuli., Comment: 11 pages, 14 figures

We generalize a result of Tibor Gallai as follows: for any finite set of points $\mathcal{S}$ in the plane, if the plane is colored in finitely many colors, then there exist $2^{\aleph_0}$ monochromatic subsets of the plane homothetic to $\mathcal{S}$. Furthermore, we prove an even stronger result for $n$-dimensional Euclidean space., Comment: 7 pages; To appear in Journal of Combinatorics

We prove that the equational complexity function for the variety of representable relation algebras is bounded below by a log-log function., Comment: 4 pages

We consider a modification of Winkler's "dots and coins" problem, where we constrain the dots to lie on a square lattice in the plane. We construct packings of "coins" (closed unit disks) using motif patterns., Comment: 10 pages, 11 figures

One of the longstanding problems in universal algebra is the question of which finite lattices are isomorphic to the congruence lattices of finite algebras. This question can be phrased as which finite lattices can be represented as lattices of equivalence relations on finite sets closed under certain first order formulas. We generalize this question to a different collection of first-order formulas, giving examples to demonstrate that our new question is distinct. We then prove that every lattice $\m M_n$ can be represented in this new way. [This is an extended version of a paper submitted to \emph{Algebra Universalis}.], Comment: 6 pages. This is an extended version of a paper published in Algebra Universalis

In this paper we prove that if $S$ is any finite configuration of points in $\mathbb{Z}^2$, then any finite coloring of $\mathbb{E}^2$ must contain uncountably many monochromatic subsets homothetic to $S$. We extend a result of Brown, Dunfield, and Perry on 2-colorings of $\mathbb{E}^2$ to any finite coloring of $\mathbb{E}^2$., Comment: 6 pages

For positive integers $m$ and $n$, define $f(m,n)$ to be the smallest integer such that any subset $A$ of the $m \times n$ integer grid with $|A| \geq f(m,n)$ contains a rectangle; that is, there are $x\in [m]$ and $y \in [n]$ and $d_{1},d_{2} \in \mathbb{Z}^{+}$ such that all four points $(x,y)$, $(x+d_{1},y)$, $(x,y+d_{2})$, and $(x+d_{1},y+d_{2})$ are contained in $A$. In \cite{kovarisosturan}, K\"ovari, S\'os, and Tur\'an showed that $\dlim_{k \to \infty}\dfrac{f(k,k)}{k^{3/2}} = 1$. They also showed that whenever $p$ is a prime number, $f(p^{2},p^{2}+p) = p^{2}(p+1)+1$. We recover their asymptotic result and strengthen the second, providing cleaner proofs which exploit a connection to projective planes, first noticed by Mendelsohn in \cite{mendelsohn87}. We also provide an explicit lower bound for $f(k,k)$ which holds for all $k$., Comment: 9 pages