-
Coalescing sets preserving cospectrality of graphs arising from block similarity matrices
Authors:
Sajid Bin Mahamud,
Steve Butler,
Hannah Graff,
Nick Layman,
Taylor Luck,
Jiah Jin,
Noah Owen,
Angela Yuan
Abstract:
Coalescing involves gluing one or more rooted graphs onto another graph. Under specific conditions, it is possible to start with cospectral graphs that are coalesced in similar ways that will result in new cospectral graphs. We present a sufficient condition for this based on the block structure of similarity matrices, possibly with additional constraints depending on which type of matrix is being…
▽ More
Coalescing involves gluing one or more rooted graphs onto another graph. Under specific conditions, it is possible to start with cospectral graphs that are coalesced in similar ways that will result in new cospectral graphs. We present a sufficient condition for this based on the block structure of similarity matrices, possibly with additional constraints depending on which type of matrix is being considered. The matrices considered in this paper include the adjacency, Laplacian, signless Laplacian, distance, and generalized distance matrix.
△ Less
Submitted 1 April, 2024;
originally announced April 2024.
-
Self-sustained deformable rotating liquid He cylinders: The pure normal fluid $^3$He and superfluid $^4$He cases
Authors:
Martí Pi,
Francesco Ancilotto,
Manuel Barranco,
Samuel L. Butler,
José María Escartín
Abstract:
We have studied self-sustained, deformable, rotating liquid He cylinders of infinite length. In the normal fluid $^3$He case, we have employed a classical model where only surface tension and centrifugal forces are taken into account, as well as the Density Functional Theory (DFT) approach in conjunction with a semi-classical Thomas-Fermi approximation for the kinetic energy. In both approaches, i…
▽ More
We have studied self-sustained, deformable, rotating liquid He cylinders of infinite length. In the normal fluid $^3$He case, we have employed a classical model where only surface tension and centrifugal forces are taken into account, as well as the Density Functional Theory (DFT) approach in conjunction with a semi-classical Thomas-Fermi approximation for the kinetic energy. In both approaches, if the angular velocity is sufficiently large, it is energetically favorable for the $^3$He cylinder to undergo a shape transition, acquiring an elliptic-like cross section which eventually becomes two-lobed. In the $^4$He case, we have employed a DFT approach that takes into account its superfluid character, limiting the description to vortex-free configurations where angular momentum is exclusively stored in capillary waves on a deformed cross section cylinder. The calculations allow us to carry out a comparison between the rotational behavior of a normal, rotational fluid ($^3$He) and a superfluid, irrotational fluid ($^4$He).
△ Less
Submitted 22 March, 2023;
originally announced March 2023.
-
Modeling and Exploration of Gain Competition Attacks in Optical Network-on-Chip Architectures
Authors:
Khushboo Rani,
Hansika Weerasena,
Stephen A. Butler,
Subodha Charles,
Prabhat Mishra
Abstract:
Network-on-Chip (NoC) enables energy-efficient communication between numerous components in System-on-Chip architectures. The optical NoC is widely considered a key technology to overcome the bandwidth and energy limitations of traditional electrical on-chip interconnects. While optical NoC can offer high performance, they come with inherent security vulnerabilities due to the nature of optical in…
▽ More
Network-on-Chip (NoC) enables energy-efficient communication between numerous components in System-on-Chip architectures. The optical NoC is widely considered a key technology to overcome the bandwidth and energy limitations of traditional electrical on-chip interconnects. While optical NoC can offer high performance, they come with inherent security vulnerabilities due to the nature of optical interconnects.
In this paper, we investigate the gain competition attack in optical NoCs, which can be initiated by an attacker injecting a high-power signal to the optical waveguide, robbing the legitimate signals of amplification. To the best of our knowledge, our proposed approach is the first attempt to investigate gain competition attacks as a security threat in optical NoCs. We model the attack and analyze its effects on optical NoC performance. We also propose potential attack detection techniques and countermeasures to mitigate the attack. Our experimental evaluation using different NoC topologies and diverse traffic patterns demonstrates the effectiveness of our modeling and exploration of gain competition attacks in optical NoC architectures.
△ Less
Submitted 2 March, 2023;
originally announced March 2023.
-
Spectral faux trees
Authors:
Steve Butler,
Elena D'Avanzo,
Rachel Heikkinen,
Joel Jeffries,
Alyssa Kruczek,
Harper Niergarth
Abstract:
A spectral faux tree with respect to a given matrix is a graph which is not a tree but is cospectral with a tree for the given matrix. We consider the existence of spectral faux trees for several matrices, with emphasis on constructions.
For the Laplacian matrix, there are no spectral faux trees. For the adjacency matrix, almost all trees are cospectral with a faux tree. For the signless Laplaci…
▽ More
A spectral faux tree with respect to a given matrix is a graph which is not a tree but is cospectral with a tree for the given matrix. We consider the existence of spectral faux trees for several matrices, with emphasis on constructions.
For the Laplacian matrix, there are no spectral faux trees. For the adjacency matrix, almost all trees are cospectral with a faux tree. For the signless Laplacian matrix, spectral faux trees can only exist when the number of vertices is of the form $n=4k$. For the normalized adjacency, spectral faux trees exist when the number of vertices $n\ge 4$, and we give an explicit construction for a family whose size grows exponentially with $k$ for $n=αk+1$ where $α$ is fixed.
△ Less
Submitted 7 September, 2022;
originally announced September 2022.
-
Complements of coalescing sets
Authors:
Steve Butler,
Elena D'Avanzo,
Rachel Heikkinen,
Joel Jeffries,
Alyssa Kruczek,
Harper Niergarth
Abstract:
We consider matrices of the form $qD+A$, with $D$ being the diagonal matrix of degrees, $A$ being the adjacency matrix, and $q$ a fixed value. Given a graph $H$ and $B\subseteq V(G)$, which we call a coalescent pair $(H,B)$, we derive a formula for the characteristic polynomial where a copy of same rooted graph $G$ is attached by the root to \emph{each} vertex of $B$. Moreover, we establish if…
▽ More
We consider matrices of the form $qD+A$, with $D$ being the diagonal matrix of degrees, $A$ being the adjacency matrix, and $q$ a fixed value. Given a graph $H$ and $B\subseteq V(G)$, which we call a coalescent pair $(H,B)$, we derive a formula for the characteristic polynomial where a copy of same rooted graph $G$ is attached by the root to \emph{each} vertex of $B$. Moreover, we establish if $(H_1,B_1)$ and $(H_2,B_2)$ are two coalescent pairs which are cospectral for any possible rooted graph $G$, then $(H_1,V(H_1)\setminus B_1)$ and $(H_2,V(H_2)\setminus B_2)$ will also always be cospectral for any possible rooted graph $G$.
△ Less
Submitted 7 September, 2022;
originally announced September 2022.
-
Reactive Answer Set Programming
Authors:
Krysia Broda,
Fariba Sadri,
Stephen Butler
Abstract:
Logic Production System (LPS) is a logic-based framework for modelling reactive behaviour. Based on abductive logic programming, it combines reactive rules with logic programs, a database and a causal theory that specifies transitions between the states of the database. This paper proposes a systematic mapping of the Kernel of this framework (called KELPS) into an answer set program (ASP). For thi…
▽ More
Logic Production System (LPS) is a logic-based framework for modelling reactive behaviour. Based on abductive logic programming, it combines reactive rules with logic programs, a database and a causal theory that specifies transitions between the states of the database. This paper proposes a systematic mapping of the Kernel of this framework (called KELPS) into an answer set program (ASP). For this purpose a new variant of KELPS with finite models, called $n$-distance KELPS, is introduced. A formal definition of the mapping from this $n$-distance KELPS to ASP is given and proven sound and complete. The Answer Set Programming paradigm allows to capture additional behaviours to the basic reactivity of KELPS, in particular proactive, preemptive and prospective behaviours. These are all discussed and illustrated with examples. Then a hybrid framework is proposed that integrates KELPS and ASP, allowing to combine the strengths of both paradigms. Under consideration in Theory and Practice of Logic Programming (TPLP).
△ Less
Submitted 22 September, 2021;
originally announced September 2021.
-
Impressions of the GDMC AI Settlement Generation Challenge in Minecraft
Authors:
Christoph Salge,
Claus Aranha,
Adrian Brightmoore,
Sean Butler,
Rodrigo Canaan,
Michael Cook,
Michael Cerny Green,
Hagen Fischer,
Christian Guckelsberger,
Jupiter Hadley,
Jean-Baptiste Hervé,
Mark R Johnson,
Quinn Kybartas,
David Mason,
Mike Preuss,
Tristan Smith,
Ruck Thawonmas,
Julian Togelius
Abstract:
The GDMC AI settlement generation challenge is a PCG competition about producing an algorithm that can create an "interesting" Minecraft settlement for a given map. This paper contains a collection of written experiences with this competition, by participants, judges, organizers and advisors. We asked people to reflect both on the artifacts themselves, and on the competition in general. The aim of…
▽ More
The GDMC AI settlement generation challenge is a PCG competition about producing an algorithm that can create an "interesting" Minecraft settlement for a given map. This paper contains a collection of written experiences with this competition, by participants, judges, organizers and advisors. We asked people to reflect both on the artifacts themselves, and on the competition in general. The aim of this paper is to offer a shareable and edited collection of experiences and qualitative feedback - which seem to contain a lot of insights on PCG and computational creativity, but would otherwise be lost once the output of the competition is reduced to scalar performance values. We reflect upon some organizational issues for AI competitions, and discuss the future of the GDMC competition.
△ Less
Submitted 6 August, 2021;
originally announced August 2021.
-
Semisolid sets and topological measures
Authors:
Svetlana V. Butler
Abstract:
This paper is one in a series that investigates topological measures on locally compact spaces. A topological measure is a set function which is finitely additive on the collection of open and compact sets, inner regular on open sets, and outer regular on closed sets. We examine semisolid sets and give a way of constructing topological measures from solid-set functions on locally compact, connecte…
▽ More
This paper is one in a series that investigates topological measures on locally compact spaces. A topological measure is a set function which is finitely additive on the collection of open and compact sets, inner regular on open sets, and outer regular on closed sets. We examine semisolid sets and give a way of constructing topological measures from solid-set functions on locally compact, connected, locally connected spaces. For compact spaces our approach produces a simpler method than the current one. We give examples of finite and infinite topological measures on locally compact spaces and present an easy way to generate topological measures on spaces whose one-point compactification has genus 0. Results of this paper are necessary for various methods for constructing topological measures, give additional properties of topological measures, and provide a tool for determining whether two topological measures or quasi-linear functionals are the same.
△ Less
Submitted 16 March, 2021;
originally announced March 2021.
-
Clarification of Video Retrieval Query Results by the Automated Insertion of Supporting Shots
Authors:
Sean Butler
Abstract:
Computational Video Editing Systems output video generally follows a particular form, e.g. conversation or music videos, in this way they are domain specific. We describe a recent development in our video annotation and segmentation system to support general computational video editing in which we derive a single generic editing strategy from general cinema narrative principles instead of using a…
▽ More
Computational Video Editing Systems output video generally follows a particular form, e.g. conversation or music videos, in this way they are domain specific. We describe a recent development in our video annotation and segmentation system to support general computational video editing in which we derive a single generic editing strategy from general cinema narrative principles instead of using a hierarchical film gram-mar. We demonstrate how this single principle coupled with a database of scripts derived from annotated videos leverages the existing video editing knowledge encoded within the editing of those sequences in a flexible and generic manner. We discuss the cinema theory foundations for this generic editing strategy, review the algorithms used to effect it, and goon by means of examples to show its appropriateness in an automated system.
△ Less
Submitted 19 February, 2021;
originally announced February 2021.
-
Integration of an Energy Management Tool and Digital Twin for Coordination and Control of Multi-vector Smart Energy Systems
Authors:
Edward O'Dwyer,
Indranil Pan,
Richard Charlesworth,
Sarah Butler,
Nilay Shah
Abstract:
As Internet of Things (IoT) technologies enable greater communication between energy assets in smart cities, the operational coordination of various energy networks in a city or district becomes more viable. Suitable tools are needed that can harness advanced control and machine learning techniques to achieve environmental, economic and resilience objectives. In this paper, an energy management to…
▽ More
As Internet of Things (IoT) technologies enable greater communication between energy assets in smart cities, the operational coordination of various energy networks in a city or district becomes more viable. Suitable tools are needed that can harness advanced control and machine learning techniques to achieve environmental, economic and resilience objectives. In this paper, an energy management tool is presented that can offer optimal control, scheduling, forecasting and coordination services to energy assets across a district, enabling optimal decisions under user-defined objectives. The tool presented here can coordinate different sub-systems in a district to avoid the violation of high-level system constraints and is designed in a generic fashion to enable transferable use across different energy sectors. The work demonstrates the potential for a single open-source optimisation framework to be applied across multiple energy vectors, providing local government the opportunity to manage different assets in a coordinated fashion. This is shown through case studies that integrate low-carbon communal heating for social housing with electric vehicle charge-point management to achieve high-level system constraints and local government objectives in the borough of Greenwich, London. The paper illustrates the theoretical methodology, the software architecture and the digital twin-based testing environment underpinning the proposed approach.
△ Less
Submitted 23 July, 2020;
originally announced July 2020.
-
Hadamard diagonalizable graphs of order at most 36
Authors:
Jane Breen,
Steve Butler,
Melissa Fuentes,
Bernard Lidický,
Michael Phillips,
Alexander W. N. Riasanovksy,
Sung-Yell Song,
Ralihe R. Villagrán,
Cedar Wiseman,
Xiaohong Zhang
Abstract:
If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $\pm1$, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable.
In this article, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$, $K_{n/2,n/2}$, $2K_{n/2}$, and $nK_1$, and we develop an e…
▽ More
If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $\pm1$, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable.
In this article, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$, $K_{n/2,n/2}$, $2K_{n/2}$, and $nK_1$, and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to order 36. Note that it is not even known how many Hadamard matrices there are of order 36.
△ Less
Submitted 15 August, 2020; v1 submitted 17 July, 2020;
originally announced July 2020.
-
Heterogeneous partition of cellular blood-borne nanoparticles through microvascular bifurcations
Authors:
Zixiang L. Liu,
Jonathan R. Clausen,
Justin L. Wagner,
Kimberly S. Butler,
Dan S. Bolintineanu,
Jeremy B. Lechman,
Rekha R. Rao,
Cyrus K. Aidun
Abstract:
Blood flowing through microvascular bifurcations has been an active research topic for many decades, while the partitioning pattern of nanoscale solutes in the blood remains relatively unexplored. Here, we demonstrate a multiscale computational framework for direct numerical simulation of the nanoparticle (NP) partitioning through physiologically-relevant vascular bifurcations in the presence of r…
▽ More
Blood flowing through microvascular bifurcations has been an active research topic for many decades, while the partitioning pattern of nanoscale solutes in the blood remains relatively unexplored. Here, we demonstrate a multiscale computational framework for direct numerical simulation of the nanoparticle (NP) partitioning through physiologically-relevant vascular bifurcations in the presence of red blood cells (RBCs). The computational framework is established by embedding a newly-developed particulate suspension inflow/outflow boundary condition into a multiscale blood flow solver. The computational framework is verified by recovering a tubular blood flow without a bifurcation and validated against the experimental measurement of an intravital bifurcation flow. The classic Zweifach-Fung (ZF) effect is shown to be well captured by the method. Moreover, we observe that NPs exhibit a ZF-like heterogeneous partition in response to the heterogeneous partition of the RBC phase. The NP partitioning prioritizes the high-flow-rate daughter branch except for extreme (large or small) suspension flow partition ratios under which the complete phase separation tends to occur. By analyzing the flow field and the particle trajectories, we show that the ZF-like heterogeneity in NP partition can be explained by the RBC-entrainment effect caused by the deviation of the flow separatrix preceded by the tank-treading of RBCs near the bifurcation junction. The recovery of homogeneity in the NP partition under extreme flow partition ratios is due to the plasma skimming of NPs in the cell-free layer. These findings, based on the multiscale computational framework, provide biophysical insights to the heterogeneous distribution of NPs in microvascular beds that are observed pathophysiologically.
△ Less
Submitted 17 June, 2020;
originally announced June 2020.
-
Enumerating Parking Completions Using Join and Split
Authors:
Ayomikun Adeniran,
Steve Butler,
Galen Dorpalen-Barry,
Pamela E. Harris,
Cyrus Hettle,
Qingzhong Liang,
Jeremy L. Martin,
Hayan Nam
Abstract:
Given a strictly increasing sequence $\mathbf{t}$ with entries from $[n]:=\{1,\ldots,n\}$, a parking completion is a sequence $\mathbf{c}$ with $|\mathbf{t}|+|\mathbf{c}|=n$ and $|\{t\in \mathbf{t}\mid t\le i\}|+|\{c\in \mathbf{c}\mid c\le i\}|\ge i$ for all $i$ in $[n]$. We can think of $\mathbf{t}$ as a list of spots already taken in a street with $n$ parking spots and $\mathbf{c}$ as a list of…
▽ More
Given a strictly increasing sequence $\mathbf{t}$ with entries from $[n]:=\{1,\ldots,n\}$, a parking completion is a sequence $\mathbf{c}$ with $|\mathbf{t}|+|\mathbf{c}|=n$ and $|\{t\in \mathbf{t}\mid t\le i\}|+|\{c\in \mathbf{c}\mid c\le i\}|\ge i$ for all $i$ in $[n]$. We can think of $\mathbf{t}$ as a list of spots already taken in a street with $n$ parking spots and $\mathbf{c}$ as a list of parking preferences where the $i$-th car attempts to park in the $c_i$-th spot and if not available then proceeds up the street to find the next available spot, if any. A parking completion corresponds to a set of preferences $\mathbf{c}$ where all cars park.
We relate parking completions to enumerating restricted lattice paths and give formulas for both the ordered and unordered variations of the problem by use of a pair of operations termed \textbf{Join} and \textbf{Split}. Our results give a new volume formula for most Pitman-Stanley polytopes, and enumerate the signature parking functions of Ceballos and González D'León.
△ Less
Submitted 27 October, 2020; v1 submitted 3 December, 2019;
originally announced December 2019.
-
Spectral properties of the exponential distance matrix
Authors:
Steve Butler,
Elizabeth Coper,
Aaron Li,
Kate Lorenzen,
Zoe Schopick
Abstract:
Given a graph $G$, the exponential distance matrix is defined entry-wise by letting the $(u,v)$-entry be $q^{\text{dist}(u,v)}$, where $\text{dist}(u,v)$ is the distance between the vertices $u$ and $v$ with the convention that if vertices are in different components, then $q^{\text{dist}(u,v)}=0$. In this paper, we will establish several properties of the characteristic polynomial (spectrum) for…
▽ More
Given a graph $G$, the exponential distance matrix is defined entry-wise by letting the $(u,v)$-entry be $q^{\text{dist}(u,v)}$, where $\text{dist}(u,v)$ is the distance between the vertices $u$ and $v$ with the convention that if vertices are in different components, then $q^{\text{dist}(u,v)}=0$. In this paper, we will establish several properties of the characteristic polynomial (spectrum) for this matrix, give some families of graphs which are uniquely determined by their spectrum, and produce cospectral constructions.
△ Less
Submitted 14 October, 2019;
originally announced October 2019.
-
Weak convergence of topological measures
Authors:
Svetlana V. Butler
Abstract:
Topological measures and deficient topological measures are defined on open and closed subsets of a topological space, generalize regular Borel measures, and correspond to (non-linear in general) functionals that are linear on singly generated subalgebras or singly generated cones of functions. They lack subadditivity, and many standard techniques of measure theory and functional analysis do not a…
▽ More
Topological measures and deficient topological measures are defined on open and closed subsets of a topological space, generalize regular Borel measures, and correspond to (non-linear in general) functionals that are linear on singly generated subalgebras or singly generated cones of functions. They lack subadditivity, and many standard techniques of measure theory and functional analysis do not apply to them. Nevertheless, we show that many classical results of probability theory hold for topological and deficient topological measures. In particular, we prove a version of Aleksandrov's Theorem for equivalent definitions of weak convergence of deficient topological measures. We also prove a version of Prokhorov's Theorem which relates the existence of a weakly convergent subsequence in any sequence in a family of topological measures to the characteristics of being a uniformly bounded in variation and uniformly tight family. We define Prokhorov and Kantorovich-Rubenstein metrics and show that convergence in either of them implies weak convergence of (deficient) topological measures on metric spaces. We also generalize many known results about various dense and nowhere dense subsets of deficient topological measures. The present paper constitutes a first step to further research in probability theory and its applications in the context of topological measures and corresponding non-linear functionals.
△ Less
Submitted 21 May, 2020; v1 submitted 5 July, 2019;
originally announced July 2019.
-
Integration with respect to deficient topological measures on locally compact spaces
Authors:
Svetlana V. Butler
Abstract:
Topological measures and deficient topological measures generalize Borel measures and correspond to certain non-linear functionals. We study integration with respect to deficient topological measures on locally compact spaces. Such an integration over sets yields a new deficient topological measure if we integrate a nonnegative vanishing at infinity function; and it produces a signed deficient top…
▽ More
Topological measures and deficient topological measures generalize Borel measures and correspond to certain non-linear functionals. We study integration with respect to deficient topological measures on locally compact spaces. Such an integration over sets yields a new deficient topological measure if we integrate a nonnegative vanishing at infinity function; and it produces a signed deficient topological measure if we use a continuous function on a compact space. We present many properties of these resulting deficient topological measures and of signed deficient topological measures. In particular, they are absolutely continuous with respect to the original deficient topological measure and Lipschitz continuous. Deficient topological measures obtained by integration over sets can also be obtained from non-linear functionals. We show that for a deficient topological measure $ μ$ that assumes finitely many values, there is a function $ f $ such that $\int_X f \, d μ= 0$, but $\int_X (-f )\, d μ\neq 0$. We present different criteria for $\int_X f \, d μ= 0$. We also prove some convergence results, including a Monotone convergence theorem.
△ Less
Submitted 22 February, 2019;
originally announced February 2019.
-
Decompositions of signed deficient topological measures
Authors:
Svetlana V. Butler
Abstract:
This paper focuses on various decompositions of topological measures, deficient topological measures, signed topological measures, and signed deficient topological measures. These set functions generalize measures and correspond to certain non-linear functionals. They may assume $\infty$ or $-\infty$. We introduce the concept of a proper signed deficient topological measure and show that a signed…
▽ More
This paper focuses on various decompositions of topological measures, deficient topological measures, signed topological measures, and signed deficient topological measures. These set functions generalize measures and correspond to certain non-linear functionals. They may assume $\infty$ or $-\infty$. We introduce the concept of a proper signed deficient topological measure and show that a signed deficient topological measure can be represented as a sum of a signed Radon measure and a proper signed deficient topological measure. We also generalize practically all known results that involve proper deficient topological measures and proper topological measures on compact spaces to locally compact spaces. We prove that the sum of two proper (deficient) topological measures is a proper (deficient) topological measure. We give a criterion for a (deficient) topological measure to be proper.
△ Less
Submitted 21 February, 2019;
originally announced February 2019.
-
Signed topological measures on locally compact spaces
Authors:
Svetlana V. Butler
Abstract:
In this paper we define and study signed deficient topological measures and signed topological measures (which generalize signed measures) on locally compact spaces. We prove that a signed deficient topological measure is $τ$-smooth on open sets and $τ$-smooth on compact sets. We show that the family of signed measures that are differences of two Radon measures is properly contained in the family…
▽ More
In this paper we define and study signed deficient topological measures and signed topological measures (which generalize signed measures) on locally compact spaces. We prove that a signed deficient topological measure is $τ$-smooth on open sets and $��$-smooth on compact sets. We show that the family of signed measures that are differences of two Radon measures is properly contained in the family of signed topological measures, which in turn is properly contained in the family of signed deficient topological measures. Extending known results for compact spaces, we prove that a signed topological measure is the difference of its positive and negative variations if at least one variation is finite; we also show that the total variation is the sum of the positive and negative variations. If the space is locally compact, connected, locally connected, and has the Alexandroff one-point compactification of genus 0, a signed topological measure of finite norm can be represented as a difference of two topological measures.
△ Less
Submitted 20 February, 2019;
originally announced February 2019.
-
Repeated quasi-integration on locally compact spaces
Authors:
Svetlana V. Butler
Abstract:
When $X$ is locally compact, a quasi-integral (also called a quasi-linear functional) on $ C_c(X)$ is a homogeneous, positive functional that is only assumed to be linear on singly-generated subalgebras. We study simple and almost simple quasi-integrals, i.e., quasi-integrals whose corresponding compact-finite topological measures assume exactly two values. We present a criterion for repeated quas…
▽ More
When $X$ is locally compact, a quasi-integral (also called a quasi-linear functional) on $ C_c(X)$ is a homogeneous, positive functional that is only assumed to be linear on singly-generated subalgebras. We study simple and almost simple quasi-integrals, i.e., quasi-integrals whose corresponding compact-finite topological measures assume exactly two values. We present a criterion for repeated quasi-integration (i.e., iterated integration with respect to topological measures) to yield a quasi-linear functional. We find a criterion for a double quasi-integral to be simple. We describe how a product of topological measures acts on open and compact sets. We show that different orders of integration in repeated quasi-integrals give the same quasi-integral if and only if the corresponding topological measures are both measures or one of the corresponding topological measures is a positive scalar multiple of a point mass.
△ Less
Submitted 19 February, 2019;
originally announced February 2019.
-
Non-linear functionals, deficient topological measures, and representation theorems on locally compact spaces
Authors:
Svetlana V. Butler
Abstract:
We study non-linear functionals, including quasi-linear functionals, p-conic quasi-linear functionals, d-functionals, r-functionals, and their relationships to deficient topological measures and topological measures on locally compact spaces. We prove representation theorems and show, in particular, that there is an order-preserving, conic-linear bijection between the class of finite deficient top…
▽ More
We study non-linear functionals, including quasi-linear functionals, p-conic quasi-linear functionals, d-functionals, r-functionals, and their relationships to deficient topological measures and topological measures on locally compact spaces. We prove representation theorems and show, in particular, that there is an order-preserving, conic-linear bijection between the class of finite deficient topological measures and the class of bounded p-conic quasi-linear functionals. Our results imply known representation theorems for finite topological measures and deficient topological measures. When the space is compact we obtain four equivalent definitions of a quasi-linear functional and four equivalent definitions of functionals corresponding to deficient topological measures.
△ Less
Submitted 15 February, 2019;
originally announced February 2019.
-
Quasi-linear functionals on locally compact spaces
Authors:
Svetlana V. Butler
Abstract:
This paper has two goals: to present some new results that are necessary for further study and applications of quasi-linear functionals, and, by combining known and new results, to serve as a convenient single source for anyone interested in quasi-linear functionals on locally compact non-compact spaces or on compact spaces. We study signed and positive quasi-linear functionals paying close attent…
▽ More
This paper has two goals: to present some new results that are necessary for further study and applications of quasi-linear functionals, and, by combining known and new results, to serve as a convenient single source for anyone interested in quasi-linear functionals on locally compact non-compact spaces or on compact spaces. We study signed and positive quasi-linear functionals paying close attention to singly generated subalgebras. The paper gives representation theorems for quasi-linear functionals on $C_c(X)$ and for bounded quasi-linear functionals on $C_0(X)$ on a locally compact space, and for quasi-linear functionals on $C(X)$ on a compact space. There is an order-preserving bijection between quasi-linear functionals and compact-finite topological measures, which is also "isometric" when topological measures are finite. Finally, we further study properties of quasi-linear functionals and give an explicit example of a quasi-linear functional.
△ Less
Submitted 8 February, 2019;
originally announced February 2019.
-
Deficient topological measures on locally compact spaces
Authors:
Svetlana V. Butler
Abstract:
Topological measures and quasi-linear functionals generalize measures and linear functionals. We define and study deficient topological measures on locally compact spaces. A deficient topological measure on a locally compact space is a set function on open and closed subsets which is finitely additive on compact sets, inner regular on open sets, and outer regular on closed sets. Deficient topologi…
▽ More
Topological measures and quasi-linear functionals generalize measures and linear functionals. We define and study deficient topological measures on locally compact spaces. A deficient topological measure on a locally compact space is a set function on open and closed subsets which is finitely additive on compact sets, inner regular on open sets, and outer regular on closed sets. Deficient topological measures generalize measures and topological measures. First we investigate positive, negative, and total variation of a signed set function that is only assumed to be finitely additive on compact sets. These positive, negative, and total variations turn out to be deficient topological measures. Then we examine finite additivity, superadditivity, smoothness, and other properties of deficient topological measures. We obtain methods for generating new deficient topological measures. We provide necessary and sufficient conditions for a deficient topological measure to be a topological measure and to be a measure. The results presented are necessary for further study of topological measures, deficient topological measures, and corresponding non-linear functionals on locally compact spaces.
△ Less
Submitted 6 February, 2019;
originally announced February 2019.
-
Solid-set functions and topological measures on locally compact spaces
Authors:
Svetlana Butler
Abstract:
A topological measure on a locally compact space is a set function on open and closed subsets which is finitely additive on the collection of open and compact sets, inner regular on open sets, and outer regular on closed sets. Almost all works devoted to topological measures, corresponding non-linear functionals, and their applications deal with compact spaces. The present paper is one in a series…
▽ More
A topological measure on a locally compact space is a set function on open and closed subsets which is finitely additive on the collection of open and compact sets, inner regular on open sets, and outer regular on closed sets. Almost all works devoted to topological measures, corresponding non-linear functionals, and their applications deal with compact spaces. The present paper is one in a series that investigates topological measures and corresponding non-linear functionals on locally compact spaces. Here we examine solid and semi-solid sets on a locally compact space. We then give a method of constructing topological measures from solid-set functions on a locally compact, connected, locally connected space. The paper gives examples of finite and infinite topological measures on locally compact, non-compact spaces and presents an easy way to generate topological measures on spaces whose one-point compactification has genus 0 from existing examples of topological measures on compact spaces.
△ Less
Submitted 5 February, 2019;
originally announced February 2019.
-
On the genus of a quotient of a numerical semigroup
Authors:
Ayomikun Adeniran,
Steve Butler,
Colin Defant,
Yibo Gao,
Pamela E. Harris,
Cyrus Hettle,
Qingzhong Liang,
Hayan Nam,
Adam Volk
Abstract:
We find a relation between the genus of a quotient of a numerical semigroup $S$ and the genus of $S$ itself. We use this identity to compute the genus of a quotient of $S$ when $S$ has embedding dimension $2$. We also exhibit identities relating the Frobenius numbers and the genus of quotients of numerical semigroups that are generated by certain types of arithmetic progressions.
We find a relation between the genus of a quotient of a numerical semigroup $S$ and the genus of $S$ itself. We use this identity to compute the genus of a quotient of $S$ when $S$ has embedding dimension $2$. We also exhibit identities relating the Frobenius numbers and the genus of quotients of numerical semigroups that are generated by certain types of arithmetic progressions.
△ Less
Submitted 24 November, 2018; v1 submitted 25 September, 2018;
originally announced September 2018.
-
Properties of a $q$-analogue of zero forcing
Authors:
Steve Butler,
Craig Erickson,
Shaun Fallat,
H. Tracy Hall,
Brenda Kroschel,
Jephian C. -H. Lin,
Bryan Shader,
Nathan Warnberg,
Boting Yang
Abstract:
Zero forcing is a combinatorial game played on a graph where the goal is to start with all vertices unfilled and to change them to filled at minimal cost. In the original variation of the game there were two options. Namely, to fill any one single vertex at the cost of a single token; or if any currently filled vertex has a unique non-filled neighbor, then the neighbor is filled for free. This pap…
▽ More
Zero forcing is a combinatorial game played on a graph where the goal is to start with all vertices unfilled and to change them to filled at minimal cost. In the original variation of the game there were two options. Namely, to fill any one single vertex at the cost of a single token; or if any currently filled vertex has a unique non-filled neighbor, then the neighbor is filled for free. This paper investigates a $q$-analogue of zero forcing which introduces a third option involving an oracle. Basic properties of this game are established including determining all graphs which have minimal cost $1$ or $2$ for all possible $q$, and finding the zero forcing number for all trees when $q=1$.
△ Less
Submitted 20 September, 2018;
originally announced September 2018.
-
Graphs with at most two trees in a forest building process
Authors:
Steve Butler,
Misa Hamanaka,
Marie Hardt
Abstract:
Given a graph, we can form a spanning forest by first sorting the edges in some order, and then only keep edges incident to a vertex which is not incident to any previous edge. The resulting forest is dependent on the ordering of the edges, and so we can ask, for example, how likely is it for the process to produce a graph with $k$ trees.
We look at all graphs which can produce at most two trees…
▽ More
Given a graph, we can form a spanning forest by first sorting the edges in some order, and then only keep edges incident to a vertex which is not incident to any previous edge. The resulting forest is dependent on the ordering of the edges, and so we can ask, for example, how likely is it for the process to produce a graph with $k$ trees.
We look at all graphs which can produce at most two trees in this process and determine the probabilities of having either one or two trees. From this we construct infinite families of graphs which are non-isomorphic but produce the same probabilities.
△ Less
Submitted 14 February, 2018;
originally announced February 2018.
-
Maximally Rotating Supermassive Stars at the Onset of Collapse: The Perturbative Effects of Gas Pressure, Magnetic Fields, Dark Matter and Dark Energy
Authors:
Satya P. Butler,
Alicia R. Lima,
Thomas W. Baumgarte,
Stuart L. Shapiro
Abstract:
The discovery of quasars at increasingly large cosmological redshifts may favor "direct collapse" as the most promising evolutionary route to the formation of supermassive black holes. In this scenario, supermassive black holes form when their progenitors - supermassive stars - become unstable to gravitational collapse. For uniformly rotating stars supported by pure radiation pressure and spinning…
▽ More
The discovery of quasars at increasingly large cosmological redshifts may favor "direct collapse" as the most promising evolutionary route to the formation of supermassive black holes. In this scenario, supermassive black holes form when their progenitors - supermassive stars - become unstable to gravitational collapse. For uniformly rotating stars supported by pure radiation pressure and spinning at the mass-shedding limit, the critical configuration at the onset of collapse is characterized by universal values of the dimensionless spin and radius parameters $J/M^2$ and $R/M$, independent of mass $M$. We consider perturbative effects of gas pressure, magnetic fields, dark matter and dark energy on these parameters, and thereby determine the domain of validity of this universality. We obtain leading-order corrections for the critical parameters and establish their scaling with the relevant physical parameters. We compare two different approaches to approximate the effects of gas pressure, which plays the most important role, find identical results for the above dimensionless parameters, and also find good agreement with recent numerical results.
△ Less
Submitted 26 July, 2018; v1 submitted 2 February, 2018;
originally announced February 2018.
-
Graph switching, 2-ranks, and graphical Hadamard matrices
Authors:
Aida Abiad,
Steve Butler,
Willem H. Haemers
Abstract:
We study the behaviour of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil-McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order $64$, we find (by computer) many Godsil-McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters…
▽ More
We study the behaviour of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil-McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order $64$, we find (by computer) many Godsil-McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behaviour of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the related strongly regular graphs have an unbounded number of different 2-ranks. The paper extends results from the article 'Switched symplectic graphs and their 2-ranks' by the first and the last author.
△ Less
Submitted 3 January, 2018;
originally announced January 2018.
-
Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
Authors:
John Ahn,
Christine Alar,
Beth Bjorkman,
Steve Butler,
Joshua Carlson,
Audrey Goodnight,
Haley Knox,
Casandra Monroe,
Michael C. Wigal
Abstract:
For a graph $G$, we associate a family of real symmetric matrices, $\mathcal{S}(G)$, where for any $M \in \mathcal{S}(G)$, the location of the nonzero off-diagonal entries of $M$ are governed by the adjacency structure of $G$. The ordered multiplicity Inverse Eigenvalue Problem of a Graph (IEPG) is concerned with finding all attainable ordered lists of eigenvalue multiplicities for matrices in…
▽ More
For a graph $G$, we associate a family of real symmetric matrices, $\mathcal{S}(G)$, where for any $M \in \mathcal{S}(G)$, the location of the nonzero off-diagonal entries of $M$ are governed by the adjacency structure of $G$. The ordered multiplicity Inverse Eigenvalue Problem of a Graph (IEPG) is concerned with finding all attainable ordered lists of eigenvalue multiplicities for matrices in $\mathcal{S}(G)$.
For connected graphs of order six, we offer significant progress on the IEPG, as well as a complete solution to the ordered multiplicity IEPG. We also show that while $K_{m,n}$ with $\min(m,n)\ge 3$ attains a particular ordered multiplicity list, it cannot do so with arbitrary spectrum.
△ Less
Submitted 8 October, 2017; v1 submitted 8 August, 2017;
originally announced August 2017.
-
The inverse eigenvalue problem of a graph: Multiplicities and minors
Authors:
Wayne Barrett,
Steve Butler,
Shaun M. Fallat,
H. Tracy Hall,
Leslie Hogben,
Jephian C. -H. Lin,
Bryan L. Shader,
Michael Young
Abstract:
The inverse eigenvalue problem of a given graph $G$ is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in $G$. Barrett et al. introduced the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP) in [8]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a…
▽ More
The inverse eigenvalue problem of a given graph $G$ is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in $G$. Barrett et al. introduced the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP) in [8]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a matrix with the same spectrum (or ordered multiplicity list) augmented with simple eigenvalues if necessary, that is, subgraph monotonicity. In this paper we extend this to a form of minor monotonicity, with restrictions on where the new eigenvalues appear. These ideas are applied to solve the inverse eigenvalue problem for all graphs of order five, and to characterize forbidden minors of graphs having at most one multiple eigenvalue.
△ Less
Submitted 31 July, 2017;
originally announced August 2017.
-
Enumerating multiplex juggling patterns
Authors:
Steve Butler,
Jeongyoon Choi,
Kimyung Kim,
Kyuhyeok Seo
Abstract:
Mathematics has been used in the exploration and enumeration of juggling patterns. In the case when we catch and throw one ball at a time the number of possible juggling patterns is well-known. When we are allowed to catch and throw any number of balls at a given time (known as multiplex juggling) the enumeration is more difficult and has only been established in a few special cases. We give a met…
▽ More
Mathematics has been used in the exploration and enumeration of juggling patterns. In the case when we catch and throw one ball at a time the number of possible juggling patterns is well-known. When we are allowed to catch and throw any number of balls at a given time (known as multiplex juggling) the enumeration is more difficult and has only been established in a few special cases. We give a method of using cards related to "embeddings" of ordered partitions to enumerate the count of multiplex juggling sequences, determine these counts for small cases, and establish some combinatorial properties of the set of cards needed.
△ Less
Submitted 9 May, 2017; v1 submitted 19 February, 2017;
originally announced February 2017.
-
A forest building process on simple graphs
Authors:
Zhanar Berikkyzy,
Steve Butler,
Jay Cummings,
Kristin Heysse,
Paul Horn,
Ruth Luo,
Brent Moran
Abstract:
Consider the following process on a simple graph without isolated vertices: Order the edges randomly and keep an edge if and only if it contains a vertex which is not contained in some preceding edge. The resulting set of edges forms a spanning forest of the graph.
The probability of obtaining $k$ components in this process for complete bipartite graphs is determined as well as a formula for the…
▽ More
Consider the following process on a simple graph without isolated vertices: Order the edges randomly and keep an edge if and only if it contains a vertex which is not contained in some preceding edge. The resulting set of edges forms a spanning forest of the graph.
The probability of obtaining $k$ components in this process for complete bipartite graphs is determined as well as a formula for the expected number of components in any graph. A generic recurrence and some additional basic properties are discussed.
△ Less
Submitted 8 September, 2017; v1 submitted 1 August, 2016;
originally announced August 2016.
-
Counting prime juggling patterns
Authors:
Esther Banaian,
Steve Butler,
Christopher Cox,
Jeffrey Davis,
Jacob Landgraf,
Scarlitte Ponce
Abstract:
Juggling patterns can be described by a closed walk in a (directed) state graph, where each vertex (or state) is a landing pattern for the balls and directed edges connect states that can occur consecutively. The number of such patterns of length $n$ is well known, but a long-standing problem is to count the number of prime juggling patterns (those juggling patterns corresponding to cycles in the…
▽ More
Juggling patterns can be described by a closed walk in a (directed) state graph, where each vertex (or state) is a landing pattern for the balls and directed edges connect states that can occur consecutively. The number of such patterns of length $n$ is well known, but a long-standing problem is to count the number of prime juggling patterns (those juggling patterns corresponding to cycles in the state graph). For the case of $b=2$ balls we give an expression for the number of prime juggling patterns of length $n$ by establishing a connection with partitions of $n$ into distinct parts. From this we show the number of two-ball prime juggling patterns of length $n$ is $(γ-o(1))2^n$ where $γ=1.32963879259...$. For larger $b$ we show there are at least $b^{n-1}$ prime cycles of length $n$.
△ Less
Submitted 12 November, 2015; v1 submitted 21 August, 2015;
originally announced August 2015.
-
A generalization of Eulerian numbers via rook placements
Authors:
Esther Banaian,
Steve Butler,
Christopher Cox,
Jeffrey Davis,
Jacob Landgraf,
Scarlitte Ponce
Abstract:
We consider a generalization of Eulerian numbers which count the number of placements of $cn$ "rooks" on an $n\times n$ board where there are exactly $c$ rooks in each row and each column, and exactly $k$ rooks below the main diagonal. The standard Eulerian numbers correspond to the case $c=1$. We show that for any $c$ the resulting numbers are symmetric and give generating functions of these numb…
▽ More
We consider a generalization of Eulerian numbers which count the number of placements of $cn$ "rooks" on an $n\times n$ board where there are exactly $c$ rooks in each row and each column, and exactly $k$ rooks below the main diagonal. The standard Eulerian numbers correspond to the case $c=1$. We show that for any $c$ the resulting numbers are symmetric and give generating functions of these numbers for small values of $k$.
△ Less
Submitted 12 November, 2015; v1 submitted 14 August, 2015;
originally announced August 2015.
-
A cospectral family of graphs for the normalized Laplacian found by toggling
Authors:
Steve Butler,
Kristin Heysse
Abstract:
We give a construction of a family of (weighted) graphs that are pairwise cospectral with respect to the normalized Laplacian matrix, or equivalently probability transition matrix. This construction can be used to form pairs of cospectral graphs with differing number of edges, including situations where one graph is a subgraph of the other. The method used to demonstrate cospectrality is by showin…
▽ More
We give a construction of a family of (weighted) graphs that are pairwise cospectral with respect to the normalized Laplacian matrix, or equivalently probability transition matrix. This construction can be used to form pairs of cospectral graphs with differing number of edges, including situations where one graph is a subgraph of the other. The method used to demonstrate cospectrality is by showing the characteristic polynomials are equal.
△ Less
Submitted 7 July, 2015;
originally announced July 2015.
-
Juggling card sequences
Authors:
Steve Butler,
Fan Chung,
Jay Cummings,
Ron Graham
Abstract:
Juggling patterns can be described by a sequence of cards which keep track of the relative order of the balls at each step. This interpretation has many algebraic and combinatorial properties, with connections to Stirling numbers, Dyck paths, Narayana numbers, boson normal ordering, arc-labeled digraphs, and more. Some of these connections are investigated with a particular focus on enumerating ju…
▽ More
Juggling patterns can be described by a sequence of cards which keep track of the relative order of the balls at each step. This interpretation has many algebraic and combinatorial properties, with connections to Stirling numbers, Dyck paths, Narayana numbers, boson normal ordering, arc-labeled digraphs, and more. Some of these connections are investigated with a particular focus on enumerating juggling patterns satisfying certain ordering constraints, including where the number of crossings is fixed.
△ Less
Submitted 6 April, 2015;
originally announced April 2015.
-
Partition and sum is fast
Authors:
Steve Butler,
Ron Graham,
Richard Stong
Abstract:
We consider the following "partition and sum" operation on a natural number: Treating the number as a long string of digits insert several plus signs in between some of the digits and carry out the indicated sum. This results in a smaller number and repeated application can always reduce the number to a single digit. We show that surprisingly few iterations of this operation are needed to get down…
▽ More
We consider the following "partition and sum" operation on a natural number: Treating the number as a long string of digits insert several plus signs in between some of the digits and carry out the indicated sum. This results in a smaller number and repeated application can always reduce the number to a single digit. We show that surprisingly few iterations of this operation are needed to get down to a single digit.
△ Less
Submitted 14 January, 2015;
originally announced January 2015.
-
The mathematics of the flip and horseshoe shuffles
Authors:
Steve Butler,
Persi Diaconis,
Ron Graham
Abstract:
We consider new types of perfect shuffles wherein a deck is split in half, one half of the deck is "reversed", and then the cards are interlaced. Flip shuffles are when the reversal comes from flipping the half over so that we also need to account for face-up/face-down configurations while horseshoe shuffles are when the order of the cards are reversed but all cards still face the same direction.…
▽ More
We consider new types of perfect shuffles wherein a deck is split in half, one half of the deck is "reversed", and then the cards are interlaced. Flip shuffles are when the reversal comes from flipping the half over so that we also need to account for face-up/face-down configurations while horseshoe shuffles are when the order of the cards are reversed but all cards still face the same direction. We show that these shuffles are closely related to faro shuffling and determine the order of the associated shuffling groups.
△ Less
Submitted 29 December, 2014;
originally announced December 2014.
-
Using twins and scaling to construct cospectral graphs for the normalized Laplacian
Authors:
Steve Butler
Abstract:
The spectrum of the normalized Laplacian matrix cannot determine the number of edges in a graph, however finding constructions of cospectral graphs with differing number of edges has been elusive. In this paper we use basic properties of twins and scaling to show how to construct such graphs. We also give examples of families of graphs which are cospectral with a subgraph for the normalized Laplac…
▽ More
The spectrum of the normalized Laplacian matrix cannot determine the number of edges in a graph, however finding constructions of cospectral graphs with differing number of edges has been elusive. In this paper we use basic properties of twins and scaling to show how to construct such graphs. We also give examples of families of graphs which are cospectral with a subgraph for the normalized Laplacian matrix.
△ Less
Submitted 23 October, 2014; v1 submitted 29 September, 2014;
originally announced September 2014.
-
Rainbow arithmetic progressions
Authors:
Steve Butler,
Craig Erickson,
Leslie Hogben,
Kirsten Hogenson,
Lucas Kramer,
Richard L. Kramer,
Jephian Chin-Hung Lin,
Ryan R. Martin,
Derrick Stolee,
Nathan Warnberg,
Michael Young
Abstract:
In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $aw([n],k)$ denotes the smallest number of colors with which the integers $\{1,\ldots,n\}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $aw([n],3)=Θ(\log n)$ and…
▽ More
In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $aw([n],k)$ denotes the smallest number of colors with which the integers $\{1,\ldots,n\}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $aw([n],3)=Θ(\log n)$ and $aw([n],k)=n^{1-o(1)}$ for $k\geq 4$.
For positive integers $n$ and $k$, the expression $aw(Z_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. In this setting, arithmetic progressions can "wrap around," and $aw(Z_n,3)$ behaves quite differently from $aw([n],3)$, depending on the divisibility of $n$. As shown in [Jungić et al., \textit{Combin. Probab. Comput.}, 2003], $aw(Z_{2^m},3) = 3$ for any positive integer $m$. We establish that $aw(Z_n,3)$ can be computed from knowledge of $aw(Z_p,3)$ for all of the prime factors $p$ of $n$. However, for $k\geq 4$, the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$.
△ Less
Submitted 11 January, 2016; v1 submitted 29 April, 2014;
originally announced April 2014.
-
Simple identification of fake Lax pairs
Authors:
Samuel Butler,
Mike Hay
Abstract:
Two simple ways to identify and explain fake Lax pairs are provided. The two methods are complementary, one involves finding a gauge transformation which can be used to remove the associated nonlinear system's dependent variable(s) from a fake Lax pair. The second method shows that excess degrees of freedom exist in fake Lax pairs. We provide several examples to illustrate both tests. The tests pr…
▽ More
Two simple ways to identify and explain fake Lax pairs are provided. The two methods are complementary, one involves finding a gauge transformation which can be used to remove the associated nonlinear system's dependent variable(s) from a fake Lax pair. The second method shows that excess degrees of freedom exist in fake Lax pairs. We provide several examples to illustrate both tests. The tests proposed here can be applied to all types of Lax pairs, including scalar or matrix linear problems associated with ordinary or partial difference and/or differential systems.
△ Less
Submitted 11 November, 2013;
originally announced November 2013.
-
Zero forcing for inertia sets
Authors:
Steve Butler,
Jason Grout,
H. Tracy Hall
Abstract:
Zero forcing is a combinatorial game played on a graph with a goal of turning all of the vertices of the graph black while having to use as few "unforced" moves as possible. This leads to a parameter known as the zero forcing number which can be used to give an upper bound for the maximum nullity of a matrix associated with the graph.
We introduce a new variation on the zero forcing game which c…
▽ More
Zero forcing is a combinatorial game played on a graph with a goal of turning all of the vertices of the graph black while having to use as few "unforced" moves as possible. This leads to a parameter known as the zero forcing number which can be used to give an upper bound for the maximum nullity of a matrix associated with the graph.
We introduce a new variation on the zero forcing game which can be used to give an upper bound for the maximum nullity of a matrix associated with a graph that has $q$ negative eigenvalues. This gives some limits to the number of positive eigenvalues that such a graph can have and so can be used to form lower bounds for the inertia set of a graph.
△ Less
Submitted 19 November, 2012;
originally announced November 2012.
-
A Discrete Inverse Scattering Transform for Q3$_δ$
Authors:
Samuel Butler
Abstract:
We derive a fully discrete Inverse Scattering Transform as a method for solving the initial-value problem for the Q3$_δ$ lattice (difference-difference) equation for real-valued solutions. The initial condition is given on an infinite staircase within an N-dimensional lattice and must obey a given summability condition. The forward scattering problem is one-dimensional and the solution to Q3$_δ$ i…
▽ More
We derive a fully discrete Inverse Scattering Transform as a method for solving the initial-value problem for the Q3$_δ$ lattice (difference-difference) equation for real-valued solutions. The initial condition is given on an infinite staircase within an N-dimensional lattice and must obey a given summability condition. The forward scattering problem is one-dimensional and the solution to Q3$_δ$ is expressed through the solution of a singular integral equation. The solutions obtained depend on N discrete independent variables and N parameters.
△ Less
Submitted 5 October, 2012;
originally announced October 2012.
-
Unrolling residues to avoid progressions
Authors:
Steve Butler,
Ron Graham,
Linyuan Lu
Abstract:
We consider the problem of coloring $[n]={1,2,...,n}$ with $r$ colors to minimize the number of monochromatic $k$ term arithmetic progressions (or $k$-APs for short). We show how to extend colorings of $\mathbb{Z}_m$ which avoid nontrivial $k$-APs to colorings of $[n]$ by an unrolling process. In particular, by using residues to color $\mathbb{Z}_m$ we produce the best known colorings for minimizi…
▽ More
We consider the problem of coloring $[n]={1,2,...,n}$ with $r$ colors to minimize the number of monochromatic $k$ term arithmetic progressions (or $k$-APs for short). We show how to extend colorings of $\mathbb{Z}_m$ which avoid nontrivial $k$-APs to colorings of $[n]$ by an unrolling process. In particular, by using residues to color $\mathbb{Z}_m$ we produce the best known colorings for minimizing the number of monochromatic $k$-APs for coloring with $r$ colors for several small values of $r$ and $k$.
△ Less
Submitted 12 September, 2012;
originally announced September 2012.
-
Multidimensional Inverse Scattering of Integrable Lattice Equations
Authors:
Samuel Butler
Abstract:
We present a discrete inverse scattering transform for all ABS equations excluding Q4. The nonlinear partial difference equations presented in the ABS hierarchy represent a comprehensive class of scalar affine-linear lattice equations which possess the multidimensional consistency property. Due to this property it is natural to consider these equations living in an N-dimensional lattice, where the…
▽ More
We present a discrete inverse scattering transform for all ABS equations excluding Q4. The nonlinear partial difference equations presented in the ABS hierarchy represent a comprehensive class of scalar affine-linear lattice equations which possess the multidimensional consistency property. Due to this property it is natural to consider these equations living in an N-dimensional lattice, where the solutions depend on N distinct independent variables and associated parameters. The direct scattering procedure, which is one-dimensional, is carried out along a staircase within this multidimensional lattice. The solutions obtained are dependent on all N lattice variables and parameters. We further show that the soliton solutions derived from the Cauchy matrix approach are exactly the solutions obtained from reflectionless potentials, and we give a short discussion on inverse scattering solutions of some previously known lattice equations, such as the lattice KdV equation.
△ Less
Submitted 21 March, 2012; v1 submitted 22 January, 2012;
originally announced January 2012.
-
An Inverse Scattering Transform for the Lattice Potential KdV Equation
Authors:
Samuel Butler,
Nalini Joshi
Abstract:
The lattice potential Korteweg-de Vries equation (LKdV) is a partial difference equation in two independent variables, which possesses many properties that are analogous to those of the celebrated Korteweg-de Vries equation. These include discrete soliton solutions, Backlund transformations and an associated linear problem, called a Lax pair, for which it provides the compatibility condition. In t…
▽ More
The lattice potential Korteweg-de Vries equation (LKdV) is a partial difference equation in two independent variables, which possesses many properties that are analogous to those of the celebrated Korteweg-de Vries equation. These include discrete soliton solutions, Backlund transformations and an associated linear problem, called a Lax pair, for which it provides the compatibility condition. In this paper, we solve the initial value problem for the LKdV equation through a discrete implementation of the inverse scattering transform method applied to the Lax pair. The initial value used for the LKdV equation is assumed to be real and decaying to zero as the absolute value of the discrete spatial variable approaches large values. An interesting feature of our approach is the solution of a discrete Gel'fand-Levitan equation. Moreover, we provide a complete characterization of reflectionless potentials and show that this leads to the Cauchy matrix form of N-soliton solutions.
△ Less
Submitted 21 November, 2011;
originally announced November 2011.
-
Origami rings
Authors:
Joe Buhler,
Steve Butler,
Warwick de Launey,
Ron Graham
Abstract:
Motivated by a question in origami, we consider sets of points in the complex plane constructed in the following way. Let $L_α(p)$ be the line in the complex plane through $p$ with angle $α$ (with respect to the real axis). Given a fixed collection $U$ of angles, let $\RU$ be the points that can be obtained by starting with $0$ and $1$, and then recursively adding intersection points of the form…
▽ More
Motivated by a question in origami, we consider sets of points in the complex plane constructed in the following way. Let $L_α(p)$ be the line in the complex plane through $p$ with angle $α$ (with respect to the real axis). Given a fixed collection $U$ of angles, let $\RU$ be the points that can be obtained by starting with $0$ and $1$, and then recursively adding intersection points of the form $L_α(p) \cap L_β(q)$, where $p, q$ have been constructed already, and $α, β$ are distinct angles in $U$.
Our main result is that if $U$ is a group with at least three elements, then $\RU$ is a subring of the complex plane, i.e., it is closed under complex addition and multiplication. This enables us to answer a specific question about origami folds: if $n \ge 3$ and the allowable angles are the $n$ equally spaced angles $kπ/n$, $0 \le k < n$, then $\RU$ is the ring $\Z[ζ_n]$ if $n$ is prime, and the ring $\Z[1/n,ζ_{n}]$ if $n$ is not prime, where $ζ_n := \exp(2πi/n)$ is a primitive $n$-th root of unity.
△ Less
Submitted 11 November, 2010;
originally announced November 2010.
-
A construction of cospectral graphs for the normalized Laplacian
Authors:
Steve Butler,
Jason Grout
Abstract:
We give a method to construct cospectral graphs for the normalized Laplacian by a local modification in some graphs with special structure. Namely, under some simple assumptions, we can replace a small bipartite graph with a cospectral mate without changing the spectrum of the entire graph. We also consider a related result for swapping out biregular bipartite graphs for the matrix $A+tD$.
We pr…
▽ More
We give a method to construct cospectral graphs for the normalized Laplacian by a local modification in some graphs with special structure. Namely, under some simple assumptions, we can replace a small bipartite graph with a cospectral mate without changing the spectrum of the entire graph. We also consider a related result for swapping out biregular bipartite graphs for the matrix $A+tD$.
We produce (exponentially) large families of non-bipartite, non-regular graphs which are mutually cospectral, and also give an example of a graph which is cospectral with its complement but is not self-complementary.
△ Less
Submitted 26 January, 2012; v1 submitted 21 August, 2010;
originally announced August 2010.
-
Hypercube orientations with only two in-degrees
Authors:
Joe Buhler,
Steve Butler,
Ron Graham,
Eric Tressler
Abstract:
We consider the problem of orienting the edges of the $n$-dimensional hypercube so only two different in-degrees $a$ and $b$ occur. We show that this can be done, for two specified in-degrees, if and only if an obvious necessary condition holds. Namely, there exist non-negative integers $s$ and $t$ so that $s+t=2^n$ and $as+bt=n2^{n-1}$. This is connected to a question arising from constructing a…
▽ More
We consider the problem of orienting the edges of the $n$-dimensional hypercube so only two different in-degrees $a$ and $b$ occur. We show that this can be done, for two specified in-degrees, if and only if an obvious necessary condition holds. Namely, there exist non-negative integers $s$ and $t$ so that $s+t=2^n$ and $as+bt=n2^{n-1}$. This is connected to a question arising from constructing a strategy for a "hat puzzle."
△ Less
Submitted 14 July, 2010;
originally announced July 2010.
-
Subdivision by bisectors is dense in the space of all triangles
Authors:
Steve Butler,
Ron Graham
Abstract:
Starting with any nondegenerate triangle we can use a well defined interior point of the triangle to subdivide it into six smaller triangles. We can repeat this process with each new triangle, and continue doing so over and over. We show that starting with any arbitrary triangle, the resulting set of triangles formed by this process contains triangles arbitrarily close (up to similarity) any given…
▽ More
Starting with any nondegenerate triangle we can use a well defined interior point of the triangle to subdivide it into six smaller triangles. We can repeat this process with each new triangle, and continue doing so over and over. We show that starting with any arbitrary triangle, the resulting set of triangles formed by this process contains triangles arbitrarily close (up to similarity) any given triangle when the point that we use to subdivide is the incenter. We also show that the smallest angle in a "typical" triangle after repeated subdivision for many generations does not have the smallest angle going to zero.
△ Less
Submitted 14 July, 2010;
originally announced July 2010.