††thanks: The following article has been submitted to the Review of Scientific
Instruments. After it is published, it will be found at Link.

# An ultra-low field SQUID magnetometer for measuring antiferromagnetic and
weakly remanent magnetic materials at low temperatures

Michael Paulsen<EMAIL_ADDRESS>Physikalisch-Technische Bundesanstalt
Berlin (PTB), 7.6 Cryosensors, Abbestrasse 2-12, 10587 Berlin, Germany  Julian
Lindner  Helmholtz-Zentrum Berlin für Materialien und Energie (HZB), Sample
Environment Group, Hahn-Meitner-Platz 1, 14109 Berlin, Germany  Bastian Klemke
Helmholtz-Zentrum Berlin für Materialien und Energie (HZB), Sample Environment
Group, Hahn-Meitner-Platz 1, 14109 Berlin, Germany  Jörn Beyer  Physikalisch-
Technische Bundesanstalt Berlin (PTB), 7.6 Cryosensors, Abbestrasse 2-12,
10587 Berlin, Germany  Michael Fechner  Max Planck Institute for the Structure
and Dynamics of Matter, Luruper Chaussee 149, 22761 Hamburg, Germany
Dennis Meier  Norwegian University of Science and Technology (NTNU),
Department of Materials Science and Engineering, Sem Sælandsvei 12, N-7034
Trondheim, Norway  Center for Quantum Spintronics, Department of Physics,
NTNU, Trondheim 7491, Norway  Klaus Kiefer  Helmholtz-Zentrum Berlin für
Materialien und Energie (HZB), Sample Environment Group, Hahn-Meitner-Platz 1,
14109 Berlin, Germany

###### Abstract

A novel setup for the measurement of magnetic fields external to certain
antiferromagnets and generally weakly remanent magnetic materials is
presented. The setup features a highly sensitive Super Conducting Quantum
Interference Device (SQUID) magnetometer with a magnetic field resolution
$\sim$ $10\text{\,}\mathrm{fT}$, non-electric thermalization of the sample
space for a temperature range of 1.5 – $65\text{\,}\mathrm{K}$ with a non-
electric sample movement drive and optical position encoding. To minimize
magnetic susceptibility effects, the setup components are degaussed and
realized with plastic materials in sample proximity. Running the setup in
magnetically shielded rooms allows for a well-defined ultra low magnetic
background field well below $150\text{\,}\mathrm{nT}$ in situ. The setup
enables studies of inherently weak magnetic materials which cannot be measured
with high field susceptibility setups, optical methods or neutron scattering
techniques, giving new opportunities for the research on e.g. spin-spiral
multiferroics, skyrmion materials and spin ices.

††preprint: AIP/123-QED

##  I Introduction

The external magnetic field of a material is given by its susceptibility as a
function of the magnetic background field and, depending on the micromagnetic
moments of the sample, its inherent magnetism. Conventional
ferro-/ferrimagnets, such as compounds of iron, cobalt and nickel, exhibit
pronounced magnetic fields $>$ $\text{\,}\mathrm{\SIUnitSymbolMicro T}$ that
can readily be measured by inductive coils or fluxgate devices. In contrast,
the complex magnetic order of spin ice, spin-spiral multiferroics, skyrmions
lattices, antiferromagnets, and other emergent functional materials is often
hard to detect with characteristic magnetic field values as low as
$\text{\,}\mathrm{pT}$. Furthermore, depending on the material’s
susceptibility, it can be difficult to ensure non-invasive magnetization
measurements and to probe the intrinsic magnetic properties free from
interfering magnetic background contributions. Achieving such experimental
conditions is challenging due to the earth magnetic field, remanence of setup
materials and currents of electronic devices, as depicted in Fig. 1.

Figure 1: Overview of temperatures Pobell (2007) $T_{x}$ ($x$ = b [boiling], c
[critical]), materials and magnetic field strengths Vrba (2002) that are
relevant for the type of measurements addressed by the developed setup.
Significant examples of material systems are spin-spiral multiferroics such as
orthorhombic rare-earth manganites Goto  _et al._ (2004); Kimura (2007) RMnO3
(R = Gd, Tb, Dy), manganese tungstate Arkenbout  _et al._ (2006) and the
olivine White  _et al._ (2012) Mn2GeO4, classical skyrmion materials Mühlbauer
_et al._ (2009); Münzer  _et al._ (2010) (e.g. MnSi, Fe1-xCoxSi) and spin ice
materials like the pyrochlore Matsuhira, Hinatsu, and Sakakibara (2001)
Dy2Ti2O7.

The motivation for realizing an appropriate ultra low-field variable
temperature magnetometer were seminal magnetization measurements on
antiferromagnets. Generally, antiferromagnets have been studied for several
decades in fundamental research and, more recently, as materials of interest
in spintronic devices Jungwirth  _et al._ (2016). As there is no net external
dipole field in the antiferromagnetic phase, measuring this state usually
involves sophisticated methods e.g. neutron scattering facilities Brockhouse
(1953); Kenzelmann  _et al._ (2005) or susceptibility setups involving high
magnetic fields Buchner  _et al._ (2018). An instructive classical example of
an antiferromagnetic solid state system with an ultra-weak external magnetic
field is Cr2O3. It was predicted Dzyaloshinskii (1992) to exhibit very weak,
higher order net external magnetization ($\sim$ $10\text{\,}\mathrm{nT}$ for a
single domain, spherical sample with radius $\sim$ $5\text{\,}\mathrm{mm}$).
The few confirmed measurements of the respective quadrupolar magnetic fields
were all conducted using dedicated SQUID setups which are not commercially
available Astrov and Ermakov (1994); Astrov  _et al._ (1996). Common to these
setups is that the SQUID sensor and its superconducting pick-up coil need to
be operated at an ideally constant low temperature ($<$ $9\text{\,}\mathrm{K}$
[$77\text{\,}\mathrm{K}$] for low [high] temperature superconductors). Also,
the pick-up coil needs to be close ($\leq$ $15\text{\,}\mathrm{mm}$) to the
sample to cause a sufficiently strong magnetic signal. Since SQUID
magnetometers detect magnetic flux change, the sample is typically moved
relative to the pick-up coil. Furthermore, the magnetic background field must
be kept extremely low to avoid magnetization of the sample due to its magnetic
susceptibility. Notably, the magnetic shielding was not quantitatively
described in the constant- and variable-temperature setups in the literature
Astrov and Ermakov (1994); Astrov  _et al._ (1996); Borovik-Romanov and
Nizhankovskii (1997). This is a crucial issue as unwanted magnetization may
lead to false quadrupole-like signals in case of anisotropic magnetic
susceptibility. It should be noted that commercially available SQUID
measurement systems typically involve electrical heaters and large
magnetsBuchner  _et al._ (2018). While these can nominally be degaussed down
to zero field, it is not clear if the actual background field within such a
setup is significantly below the necessary 1 Oe, i.e.
$100\text{\,}\mathrm{\SIUnitSymbolMicro T}$ to avoid false signals due to
anisotropic susceptibilityAstrov  _et al._ (1996). Furthermore, the
gradiometric pick-up coil of commercial systems is usually optimized for
measuring the magnetic dipole moment of the sample, rather than higher order
magnetic contributions.
The realization of a magnetometer with very low magnetic background and high
magnetic field resolution was recently described Paulsen  _et al._ (2019) by
the authors. In that setup, the sample was kept at constant liquid helium
temperature ($T_{\text{LHe}}$=$4.2\text{\,}\mathrm{K}$) and slowly rotated,
using a plastic gravity-driven pendulum motor along with an optical encoder,
$\sim$ $4\text{\,}\mathrm{mm}$ in front of a superconducting pick-up coil
connected to a SQUID sensor. The magnetometer can advantageously be used in
combination with a Glass-Fiber-reinforced Cryostat (GFC) inside of a
magnetically shielded environment such as the Berlin Magnetically Shielded
Room-2 (BMSR-2) Knappe-Grueneberg  _et al._ (2008) or a smaller ultra-low
magnetic field shieldingSun  _et al._ (2020).
In this work, we present the realization of a novel experimental setup Lindner
_et al._ (8 23), which enables temperature-dependent measurements of external
fields of magnetically ordered materials. The sample temperature is varied
without electric heating and the setup consists of very low remanence
materials, such as PolyEther Ether Ketone (PEEK) and PolyVinyl Chloride (PVC).

##  II Description of Experimental Setup

The measurement principle is based on varying the temperature of the sample
while moving/rotating it in front of a magnetometer in an ultra-low magnetic
field. This is realized with a custom-built continuous Variable Temperature
Magnetometer Insert (VTMI), as schematically depicted in Fig. 2.

Figure 2: Schematic measurement principle of the VTMI.

Liquid and gaseous helium enter and then flow downwards into the VTMI. At the
bottom, the mixture enters the sample tube where it flows upwards and
thermalizes the sample. A small thermometer mounted to the end of a small
hollow temperature holder is placed centrally above the sample to measure the
temperature of the upwardly flowing helium mixture. The sample tube can be
moved to rotate the sample in front of a SQUID magnetometer. In order to
perform such measurements in practice, the VTMI fulfills additional
requirements.

  * •

The SQUID magnetometer is based on the superconductivity of niobium (Nb) and
is operated at liquid helium temperature. A superconducting pick-up coil
consisting of niobium titanium (NbTi) is placed in close proximity to the
sample while an isolation vacuum surrounding the sample chamber is realized
which requires a further layer of material. Thus, an additional short transfer
tube to bring the liquid helium into the sample chamber is needed.

  * •

Only low remanence magnetic materials should be used for the construction,
especially regarding moving parts and all parts near the sample and SQUID to
avoid magnetic background.

  * •

To enable rotation and vertical movement of the sample holder tube, a
rotation-compatible solution for extracting the helium mixture past the sample
is called for, along with seals, which enable these movements while remaining
gas-tight. Further tight seals are needed to ensure that the thermometer tube
remains fixed during the measurements.

The design of the VTMI is depicted in Fig. 3 and was realized as follows.
Double-walled tubes, made of PEEK in its lower part and stainless steel in its
top part, are connected to a PEEK needle valve housing. This design ensures
liquid helium supply via the GFC, while a gas valve controls the supply of
exterior compressed helium gas at room temperature. The double-walled tubes
have a valve that is connected to a pump ensuring an isolating vacuum.
A carbon fiber sample holder tube is kept in position via several vacuum
seals. Its bottom part connects to a light plastic tube, e.g. a plastic straw,
in which the sample is fixed with helium-permeable holding pads. The top part
features two small holes and is located in ambient room temperature, where it
connects to an exhaust valve at its top part, such that the liquid-helium
mixture can flow past the sample. A hollow rod within the sample holder tube
holds a small Cernox® thermometer (CX-1050-BC-HT) in the gas flow centrally
above the sample. Several vacuum seals ensure that the sample holder tube can
rotate while the thermometer rod remains fixed and centered using a centering
piece such that helium gas can flow towards the exhaust valve. The thermometer
wires run through the hollow thermometer rod to electronics at room
temperature.

Figure 3: Schematic view of the realized VTMILindner  _et al._ (8 23) placed
in a GFC.

The sample movement is provided by an ultra-low field drive, which is realized
as a three cylinder pneumatic engine using commercially available LEGO® and
custom-built plastic parts, as depicted in Fig. 4. While the pneumatic engine
itself runs at about 120 rpm at a pressure of $\approx$
$1.5\text{\,}\mathrm{bar}$ it is geared down several times to increase the
torque which is needed for rotating the sample holder tube between the seals.
The resulting rotation speed of the sample holder is $\approx$ 0.5 rpm. The
sample position is determined using a custom-built optical system, which is
realized as a three-channel quadrature encoder consisting of SensoPart FL 70
light sensors, optical fiber cables along with an optical fork barrier and a
plastic encoder disc.

Figure 4: The non-electric sample movement drive and optical position encoder
in operation with a liquid helium temperature magnetometer insertPaulsen  _et
al._ (2019).

A PVC mounting supports the SQUID magnetometer and an optional superconducting
lead (Pb) shielding. These components and the needle valve piece of the
double-walled tubes are completely immersed in the liquid helium of the GFC
and attached to the bottom part of the double-walled tube. The SQUID
magnetometer is based on a PTB C6XXL1 single-stage current sensor Drung  _et
al._ (2007). Due to the Nb materials used in the chip, the sensor is operated
at the very stable temperature of LHe at $4.2\text{\,}\mathrm{K}$. The control
and readout of the sensor was done using Magnicon GmbH XXF-1 electronics. The
output voltage of the SQUID electronics was read out with a Keithley 2010
multimeter. The current sensor is connected to a superconducting pick-up coil,
consisting of NbTi-wire with a diameter of $0.102\text{\,}\mathrm{mm}$ around
a hollow PEEK tube. It has an outer diameter of $10.5\text{\,}\mathrm{mm}$ and
a coil of eleven turns with an inductance $\approx$ $900\text{\,}\mathrm{nH}$
was realized around it. The leads to the coil were carefully twisted to avoid
parasitic inductance, which was estimated to be approximately
$50\text{\,}\mathrm{nH}$ as the leads had an approximate length of
$0.1\text{\,}\mathrm{m}$. The complete measurement setup consists of
electronics and vacuum pumps outside of a magnetic shielding, which contains a
GFC with the custom-built VTMI.

##  III Operating Principle

Before operation, the sample is placed within the sample tube in front of the
SQUID magnetometer. While still at room temperature, an isolating vacuum of
$\sim 10^{-4}$ mbar is pumped. The sample holder tube is carefully flooded
with gaseous helium at a slight overpressure of around
$10\text{\,}\mathrm{mbar}$. The VTMI is cooled down by careful lowering into
the helium-filled GFC and by fixing it at the cryostat flange such that the
liquid helium level is well above the needle valve housing. The needle valve
is opened to allow liquid helium to enter from the GFC into the sample
chamber. To set the temperature, room-tempered helium gas is lead into the
sample chamber and when the exhaust valve is kept open, the helium mixture
flows through the outer sample holder tube and the sample is thermalized. To
achieve a low consumption of helium and to avoid turbulence, which could cause
a jiggle of the sample, the setup is operated at minimal flows. For
temperatures above the boiling temperature of liquid helium at normal
pressure, i.e. $>$ $4.2\text{\,}\mathrm{K}$, gas flows corresponding to
between 10 and $25\text{\,}\mathrm{mbar}$ of overpressure in the exhaust pipe
are used.
During measurement operation, the temperature must be set manually by
adjusting the helium gas valve and liquid helium needle valve, respectively.
If the temperature at the sample location is intended to decline, the needle
valve may be opened a little further or one may gradually close the helium gas
valve. To increase the temperature, one proceeds vice versa. The settings of
the valves should result in a pressure of the mixture flow within the verified
range corresponding to 10 – $25\text{\,}\mathrm{mbar}$. Comparably high
temperatures $>$$100\text{\,}\mathrm{K}$ can necessitate the complete closing
of the needle valve. To reach temperatures below the boiling point of liquid
helium at normal pressure, the setup makes use of the decreasing boiling
temperature at diminishing pressure. Therefore, the sample chamber must be
filled with some liquid helium and then the needle valve must be closed
further, partially or completely. That way, sample temperatures as low as
$1.5\text{\,}\mathrm{K}$ can be reached.
During development, tests of the variable temperature insert under realistic
ambient conditions, with a sample dummy and two thermometers (one attached to
the sample dummy and one at standard position), were performed. The
temperature difference was lower than $1\text{\,}\mathrm{K}$. The in situ
temperature range proved to be 1.5 – 65 K with a temperature stability $\pm 2$
K of several minutes. The helium consumption was approximately 1.5 l/h, which
allows for over 150 rotations of the sample within one run, corresponding to
approximately four hours of measurement time for the 8 l GFC that we used.
When the realized setup was placed in the magnetically shielded room BMSR-2 at
the PTB Berlin, the magnetic background field in situ was measured to be
significantly less than $150\text{\,}\mathrm{nT}$ using hand-held fluxgate
devices. The main magnetic contribution came from a remanent steel part in the
needle valve, which in principle could be replaced with a PEEK version to
allow for $<$ $10\text{\,}\mathrm{nT}$ in situ magnetic background.

##  IV Prototypical Measurement

In order to demonstrate the sensitivity of our setup, we performed
temperature-dependent measurements on the spin-spiral multiferroic TbMnO3
Kimura  _et al._ (2003). The material exhibits different magnetic phase
transitions at cryogenic temperature, going from paramagnetic (PM) to
sinusoidal (AP1) to cycloidal (AP2) to Tb3+ induced (AP3) antiferromagnetic
order as explained elsewhere Kenzelmann  _et al._ (2005); Kimura (2007). Most
important for this work, the magnetic order and transition temperatures are
well-known and it is established that TbMnO3 displays a compensated spin
structure that allows only for weak higher-order contributions, whereas
magnetic dipole contributions are forbidden by symmetry, with the temperature
intervals of interestKimura (2007) $\text{PM}>T_{\text{N}}=41$ K $>$ AP1
$>T_{\text{C}}=28$ K $>$ AP2 $>T_{\text{A}}=7\,$K $>$ AP3.
Fig. 5 presents a temperature-dependent measurement gained on a TbMnO3 single
crystal with side length $\approx$ $5\text{\,}\mathrm{mm}$. The recorded
output SQUID voltage, thermometer temperature and the exhaust pressure are
plotted over the measurement time, which was 52 minutes. At the start, while
rotating the sample using the pneumatic drive, the liquid helium needle valve
was opened and the valve for room-temperature helium gas was gradually closed.
This caused the temperature to reach a stable $1.5\text{\,}\mathrm{K}$, i.e.
the AP3 state of the sample, for six minutes. By closing the needle valve and
opening the helium gas valve appropriately, the AP2, AP1 and finally the PM
state of the sample were measured. Thus, the intended functionality of the
developed setup was successfully verified.

Figure 5: Raw data plot of a test measurement using the novel setup: a TbMnO3
sample was rotated at $\approx$ 0.5 rpm. The output SQUID voltage [top],
thermometer temperature [middle] and exhaust pressure [bottom] are shown, with
transitions and stable regions depicted as shaded and transparent,
respectively.

##  V Summary

A novel setup designed for measuring ultra-small magnetic fields was
presented. It is readily applicable to measure weak magnetic remanence of a
wide range of solid state materials including spin-spiral multiferroicsVopson
(2015), spin icesGingras (2011) and 3D printed nanomaterials Löwa  _et al._
(2019) which are used as phantoms in magnetic resonance imaging researchArenas
_et al._ (2022). Compared to other setups reported in literature and
commercial SQUID systems, the apparatus features several advantages. The
sample movement and thermalization are entirely composed of non-metallic and
non-electric components, which greatly reduces magnetic interactions with the
sample along with customized state-of-the-art SQUID magnetometry. The setup
performed excellently in a controlled, magnetically shielded room. The
realized prototype can measure the external magnetic field of small (diameters
$\sim$ 1–$7\text{\,}\mathrm{mm}$) very weakly remanent ($\sim$
$0.1\text{\,}\mathrm{pT}$ at sample surface) samples in the temperature range
1.5 – $65\text{\,}\mathrm{K}$ with an in-situ background field well below
$150\text{\,}\mathrm{nT}$, giving new opportunities for the study of complex
low-remanent materials with otherwise hard-to-measure magnetic properties.

###### Acknowledgements.

The technical support of Martin Petsche at HZB, Lars Schikowski at PTB,
Monique Klemm and Sassan AliValiollahi at Magnicon GmbH is gratefully
acknowledged. The setup was tested at the BMSR-2 within the Deutsche
Forschungsgemeinschaft core facility Metrology for Ultra-Low Magnetic Fields
with the generous help of Rainer Körber, Allard Schnabel and Jens Voigt. The
authors thank Tsuyoshi Kimura for providing the TbMnO3 single crystal for our
experiments. We further thank Niclas Scholz (manufacturing), Dirk Gutkelch
(development) and Norbert Löwa (research) of the B-smart Lab at PTB for the
support with additive manufacturing concerning a 3D-printed magnetic
nanomaterial phantom sample that was kindly provided to us. DM acknowledges
funding from the Research Council of Norway, project number 263228 and support
through its Centres of Excellence funding scheme, Project No. 262633,
“QuSpin”, and thanks NTNU for support via the Onsager Fellowship Program and
the Outstanding Academic Fellows Program.

## References

  * Pobell (2007) F. Pobell,  _Matter and methods at low temperatures_ (Springer Science & Business Media, 2007).
  * Vrba (2002) J. Vrba, “Magnetoencephalography: the art of finding a needle in a haystack,” Physica C: Superconductivity 368, 1–9 (2002).
  * Goto  _et al._ (2004) T. Goto, T. Kimura, G. Lawes, A. Ramirez, and Y. Tokura, “Ferroelectricity and Giant Magnetocapacitance in Perovskite Rare-Earth Manganites,” Physical review letters 92, 257201 (2004).
  * Kimura (2007) T. Kimura, “Spiral magnets as magnetoelectrics,” Annu. Rev. Mater. Res. 37, 387–413 (2007).
  * Arkenbout  _et al._ (2006) A. Arkenbout, T. Palstra, T. Siegrist, and T. Kimura, “Ferroelectricity in the cycloidal spiral magnetic phase of MnWO4,” Physical Review B 74, 184431 (2006).
  * White  _et al._ (2012) J. White, T. Honda, K. Kimura, T. Kimura, C. Niedermayer, O. Zaharko, A. Poole, B. Roessli, and M. Kenzelmann, “Coupling of Magnetic and Ferroelectric Hysteresis by a Multicomponent Magnetic Structure in Mn2GeO4,” Physical Review Letters 108, 077204 (2012).
  * Mühlbauer  _et al._ (2009) S. Mühlbauer, B. Binz, F. Jonietz, C. Pfleiderer, A. Rosch, A. Neubauer, R. Georgii, and P. Böni, “Skyrmion lattice in a chiral magnet,” Science 323, 915–919 (2009).
  * Münzer  _et al._ (2010) W. Münzer, A. Neubauer, T. Adams, S. Mühlbauer, C. Franz, F. Jonietz, R. Georgii, P. Böni, B. Pedersen, M. Schmidt, _et al._ , “Skyrmion lattice in the doped semiconductor Fe1-xCoxSi,” Physical Review B 81, 041203 (2010).
  * Matsuhira, Hinatsu, and Sakakibara (2001) K. Matsuhira, Y. Hinatsu, and T. Sakakibara, “Novel dynamical magnetic properties in the spin ice compound Dy2Ti2O7,” Journal of Physics: Condensed Matter 13, L737 (2001).
  * Jungwirth  _et al._ (2016) T. Jungwirth, X. Marti, P. Wadley, and J. Wunderlich, “Antiferromagnetic spintronics,” Nature Nanotechnology 11, 231–241 (2016).
  * Brockhouse (1953) B. N. Brockhouse, “Antiferromagnetic Structure in Cr2O3,” The Journal of Chemical Physics 21, 961–962 (1953).
  * Kenzelmann  _et al._ (2005) M. Kenzelmann, A. B. Harris, S. Jonas, C. Broholm, J. Schefer, S. Kim, C. Zhang, S.-W. Cheong, O. P. Vajk, and J. W. Lynn, “Magnetic Inversion Symmetry Breaking and Ferroelectricity in TbMnO3,” Physical review letters 95, 087206 (2005).
  * Buchner  _et al._ (2018) M. Buchner, K. Höfler, B. Henne, V. Ney, and A. Ney, “Tutorial: Basic principles, limits of detection, and pitfalls of highly sensitive SQUID magnetometry for nanomagnetism and spintronics,” Journal of Applied Physics 124, 161101 (2018).
  * Dzyaloshinskii (1992) I. Dzyaloshinskii, “External magnetic fields of antiferromagnets,” Solid state communications 82, 579–580 (1992).
  * Astrov and Ermakov (1994) D. Astrov and N. Ermakov, “Quadrupole magnetic field of magnetoelectric Cr2O3,” Soviet Journal of Experimental and Theoretical Physics Letters 59, 297 (1994).
  * Astrov  _et al._ (1996) D. Astrov, N. Ermakov, A. Borovik-Romanov, E. Kolevatov, and V. Nizhankovskii, “External quadrupole magnetic field of antiferromagnetic Cr2O3,” Journal of Experimental and Theoretical Physics Letters 63, 745–751 (1996).
  * Borovik-Romanov and Nizhankovskii (1997) A. Borovik-Romanov and V. Nizhankovskii, “Quadrupolar magnetic field outside antiferromagnetic Cr2O3,” Acta Physica Polonica A 92, 371–374 (1997).
  * Paulsen  _et al._ (2019) M. Paulsen, K. Kiefer, D. Meier, M. Fechner, B. Klemke, M. Petsche, and H. Lucht, “Device for determining small magnetic fields with at least one SQUID sensor,” (2019), Patent DE102017122028B4.
  * Knappe-Grueneberg  _et al._ (2008) S. Knappe-Grueneberg, A. Schnabel, G. Wuebbeler, and M. Burghoff, “Influence of demagnetization coil configuration on residual field in an extremely magnetically shielded room: Model and measurements,” Journal of Applied Physics 103, 07E925 (2008).
  * Sun  _et al._ (2020) Z. Sun, P. Fierlinger, J. Han, L. Li, T. Liu, A. Schnabel, S. Stuiber, and J. Voigt, “Limits of Low Magnetic Field Environments in Magnetic Shields,” IEEE Transactions on Industrial Electronics 68, 5385–5395 (2020).
  * Lindner  _et al._ (8 23) J. Lindner, M. Paulsen, K. Kiefer, D. Meier, M. Fechner, B. Klemke, M. Petsche, and L. Schikowski, “Vorrichtung zur variablen Temperatureinstellung in einem Durchflusskryostaten,” (Granted 2022-08-23), Patent Application DE102020123664A1.
  * Drung  _et al._ (2007) D. Drung, C. Aßmann, J. Beyer, A. Kirste, M. Peters, F. Ruede, and T. Schurig, “Highly Sensitive and Easy-to-Use SQUID Sensors,” IEEE Transactions on Applied Superconductivity 17, 699–704 (2007).
  * Kimura  _et al._ (2003) T. Kimura, T. Goto, H. Shintani, K. Ishizaka, T.-h. Arima, and Y. Tokura, “Magnetic control of ferroelectric polarization,” nature 426, 55–58 (2003).
  * Vopson (2015) M. M. Vopson, “Fundamentals of Multiferroic Materials and Their Possible Applications,” Critical Reviews in Solid State and Materials Sciences 40, 223–250 (2015).
  * Gingras (2011) M. J. Gingras, “Spin ice,” Introduction to Frustrated Magnetism , 293–329 (2011).
  * Löwa  _et al._ (2019) N. Löwa, J.-M. Fabert, D. Gutkelch, H. Paysen, O. Kosch, and F. Wiekhorst, “3D-printing of novel magnetic composites based on magnetic nanoparticles and photopolymers,” Journal of Magnetism and Magnetic Materials 469, 456–460 (2019).
  * Arenas  _et al._ (2022) M. A. A. Arenas, D. Gutkelch, O. Kosch, R. Brühl, F. Wiekhorst, and N. Löwa, “Development of Phantoms for Multimodal Magnetic Resonance Imaging and Magnetic Particle Imaging,” Polymers 14 (2022), 10.3390/polym14193925.


# Analysis and Algorithmic Construction of Self-Assembled DNA Complexes

Cory Johnson  California State University, San Bernardino, Department of
Mathematics, San Bernardino, CA<EMAIL_ADDRESS>Andrew Lavengood-
Ryan  Nevada State University, Department of Data, Media, and Design,
Henderson, NV<EMAIL_ADDRESS>
###### Abstract

DNA self-assembly is an important tool that has a wide range of applications
such as building nanostructures, the transport of target virotherapies, and
nano-circuitry. Tools from graph theory can be used to encode the biological
process of DNA self-assembly. The principle component of this process is to
examine collections of branched junction molecules, called pots, and study the
types of structures that can be constructed. We restrict our attention to pots
which contain one set of complementary cohesive-ends, i.e. a single bond-edge
type, and we identify the types and sizes of structures that can be built from
such a pot. In particular, we show a dependence between the order of graphs in
the output of the pot and the number of arms on the corresponding tiles.
Furthermore, we provide two algorithms which will construct complete complexes
for a pot with a single bond-edge type.

###### keywords:

graph theory , graph algorithms , DNA self-assembly , flexible tile model

##  1 Introduction

DNA self-assembly is a vital experimental process that is being utilized in
labs across the country. The use of DNA self-assembly as a bottom-up
technology for creating target nanostructures was introduced in Seeman’s
laboratory in the 1980s [13]. The process relies on the complementary nature
of nucleotides that comprise the structure of DNA. DNA self-assembly has
applications ranging from the construction of nanostructures to experimental
virotherapies [5, 14]. Graphs are natural mathematical models for DNA self-
assembled structures and we use a combination of graph theoretic and algebraic
tools to optimize the assembly process.

The nature of the nucleotide base pairing allows DNA to be configured into a
variety of shapes, such as hairpins, cubes, and other non-traditional
structures [2, 7, 10, 15, 18]. The nature of the nucleotide base pairing may
also be utilized to build larger structures [2, 15, 18]. Two models of the
assembly process emerge: a model which utilizes rigid tiles [16, 17, 11], and
the other using flexible tiles [9, 12]. We study the flexible tile model which
has been used to construct structures such as the cube and truncated
octahedron [2, 15, 18]. A detailed description of the graph theoretic model of
flexible tile DNA self-assembly can be found in [1, 4, 5].

In the DNA self-assembly process, target structures are built from branched
junction molecules, which are asterisk-shaped molecules whose arms consist of
strands of DNA. The end of each arm contains unsatisfied nucleotide bases
creating a cohesive-end. Each cohesive-end will bond with a complementary
cohesive-end from another arm via Watson-Crick base pairing. We will formalize
this process in Section 2. Rather than referring to the precise nature of a
cohesive-end (such as the exact nucleotide configuration), we use single
alphabet letters to distinguish between cohesive-ends of different types. For
example, $a$ and $b$ denote two non-compatible cohesive-ends, but cohesive-end
$a$ will bond with cohesive-end $\hat{a}$ . We use the term bond-edge type to
refer to a pair of complementary cohesive-ends.

A collection of branched junction molecules used in the self-assembly process
is called a pot. Previous research has investigated questions arising from
determining the most efficient pot given a target complete complex [1, 4, 5].
We study the inverse question: given a pot, what are the complete complexes
that can be assembled? In [1], it was shown that determining if a given pot
will realize a graph of a given order is NP-hard. Thus, we restrict our
attention to specialized cases; in particular, we study the case where the pot
contains one bond-edge type. At this time we reserve our attention to three
open questions:

  1. 1.

What are the sizes of the DNA complexes that can be realized by a specific
pot?

  2. 2.

What types and what distributions of branched junction molecules does a pot
use in realizing a target DNA complex?

  3. 3.

Exactly what types of DNA complexes do we expect a pot to realize? (e.g.
disconnected or connected complexes)

Section 2 formalizes the graph theoretic model of the DNA self-assembly
process. Section 3 is a collection of our results related to the three
questions above, with Section 4 providing algorithms for producing connected
graphs. We end in Section 5 with some insight into future directions.

##  2 Encoding DNA Complexes using Graph Theory

The following graph theoretic model of DNA self-assembly is consistent with
[1, 4, 5, 8]. Relevant definitions are copied here for the reader. A graph $G$
consists of a set $V=V(G)$ of vertices and a set $E=E(G)$ of 2-element subsets
of $V$, called edges. Note that we allow for $G$ to be a multigraph.

A DNA complex is composed of $k$-armed branched junction molecules, which are
asterisk-shaped molecules with $k$ arms of strands of DNA. Two arms can bond
only if they have complementary base pairings. See Figure 1 for an example of
a branched junction molecule along with an example of Definition 1. Definition
1 translates the biological process of self-assembly into a combinatorial
representation.

######  Definition 1.

Consider a $k$-armed branched junction molecule.

  1. 1.

A $k$-armed branched junction molecule is modeled by a tile. A tile is a
vertex with $k$ half-edges representing the cohesive-ends (or arms) of the
molecule $a,b,c,\ldots.$ We will denote complementary cohesive-ends with
$\hat{a},\hat{b},\hat{c},\ldots.$

  2. 2.

A bond-edge type is a classification of the cohesive-ends of tiles (without
regard to hatted and unhatted letters). For example, $a$ and $\hat{a}$ will
bond to form bond-edge type $a$.

  3. 3.

We denote tile types by $t_{j}$, where
$t_{j}=\\{a_{1}^{e_{1}},\hat{a}_{1}^{e_{2}},\ldots,a_{k}^{e_{2k-1}},\hat{a}_{k}^{e_{2k}},\ldots\\}$.
The exponent on $a_{i}$ indicates the quantity of cohesive-ends of type
$a_{i}$ present on the tile.

  4. 4.

A pot is a collection of distinct tile types such that for any cohesive-end
type that appears on any tile in the pot, its complement also appears on some
tile in the pot. We denote a pot by $P$.

  5. 5.

It is our convention to think of bonded arms (that is, where cohesive-end
$a_{i}$ has been matched with cohesive-end $\hat{a_{i}}$) as edges on a graph,
and we think of the bond-edge type as providing direction and compatibility of
edges. Unhatted cohesive-ends will denote half-edges directed away from the
vertex, and hatted cohesive-ends will denote a half-edge directed toward the
vertex. When cohesive-ends are matched, this will result in a directed edge
pointing away from the tile that had an unhatted cohesive end and toward the
vertex that had a hatted cohesive end.

######  Definition 2.

[4] An assembling pot $P_{\lambda}(G)$ for a graph $G$ with assembly design
$\lambda$ is the multiset of tiles $t_{v}$ where $t_{v}$ is associated to
vertex $v\in V(G)$. Note that it is possible that tile $t_{u}=t_{v}$ even if
$u\neq v$. If we view a vertex $v$ as its set of half-edges and a tile as a
multiset of labels, then the labeling $\lambda$ can be used to map vertices to
tiles by $\lambda:V\to P_{\lambda}(G)$ such that $\lambda(v)=t_{v}$.

(a) Example of a 4-armed branched junction molecule

$t_{1}=\\{a^{4}\\}$$t_{1}=\\{a^{4}\\}$$t_{1}=\\{a^{4}\\}$$t_{1}=\\{a^{4}\\}$
(b) Tile with four cohesive-ends of type $a$

Figure 1: A branched junction molecule and its associated tile representation.

######  Definition 3.

We say that a graph $G$ is realized by a pot $P$ if there exists a map
$f:\\{v_{*}\\}\to P$ from the set of vertices with half-edges to the tile
types with the following properties:

  1. 1.

If $v_{*}\mapsto t$, then there is an associated one-to-one correspondence
between the cohesive ends of $t$ and the half-edges of $v$.

  2. 2.

If $\\{u,v\\}\in E(G)$, then the two half-edges of $\\{u,v\\}$ are assigned
complementary cohesive ends.

The following result from [5] provides a foundation for the work presented in
Section 3. Let $P=\\{t_{1},\ldots,t_{p}\\}$ be a pot with $p$ tile types, and
define $A_{i,j}$ to be the number of cohesive ends of type $a_{i}$ on tile
$t_{j}$ and $\hat{A}_{i,j}$ to be the number of cohesive ends of type
$\hat{a}_{i}$ on tile $t_{j}$. Suppose a target graph $G$ of order $n$ is
realized by $P$ using $R_{j}$ tiles of type $j$. Since we consider only
complete complexes, we have the following equations:

$\sum_{j}R_{j}=n\text{ and
}\sum_{j}R_{j}(A_{i,j}-\hat{A}_{i,j})=0\qquad\text{for all }i.$ (1)

Define $z_{i,j}=A_{i,j}-\hat{A}_{i,j}$ and $r_{j}$ to be the proportion of
tile-type $t_{j}$ used in the construction of $G$. Then the equations in
Equation 1 become

$\sum_{j}r_{j}=1\text{ and }\sum_{j}r_{j}z_{i,j}=0\qquad\text{for all }i.$ (2)

The equations in Equation 2 naturally define a matrix associated to $P$.

######  Definition 4.

Let $P=\\{t_{1},t_{2},\ldots,t_{p}\\}$ be a pot. Then the construction matrix
of $P$ is given by

$M_{P}=\blockarray{cccccc}&t_{1}t_{2}\cdots t_{p}\hskip 14.22636pt\\\
\block{c[cccc|c]}a_{1}z_{1,1}z_{1,2}\cdots z_{1,p}0\\\
a_{2}z_{2,1}z_{2,2}\cdots z_{2,p}0\\\ \vdots\vdots\vdots\ddots\vdots\vdots\\\
a_{m}z_{m,1}z_{m,2}\cdots z_{m,p}0\\\ 11\cdots 11\\\ .$

In general, there are infinitely many solutions to the system of equations
defined by $M_{P}$, so it is desirable to concisely express these solutions.
However, we only consider those solutions in
$\left(\mathbb{Q}\cap[0,1]\right)^{p}$. That is, vectors whose entries are
rational numbers between 0 and 1.

######  Definition 5.

The solution space of $M_{P}$ is called the spectrum of $P$, and is denoted by
$\mathcal{S}(P)$.

The following lemma from [5] indicates when a solution to the construction
matrix will realize a graph of a particular order.

######  Lemma 1.

[5] Let $P=\\{t_{1},\ldots,t_{p}\\}$. If
$\left\langle{r_{1},\ldots,r_{p}}\right\rangle\in\mathcal{S}(P)$, and there
exists an $n\in\mathbb{Z}_{\geq 0}$ such that $nr_{j}\in\mathbb{Z}_{\geq 0}$
for all $j$, then there is a graph of order $n$ such that $G\in\mathcal{O}(P)$
using $nr_{j}$ tiles of type $t_{j}$. Let $m_{P}$ denote the smallest order of
a graph in $\mathcal{O}(P)$.

We will focus exclusively on pots with one bond-edge type, meaning $M_{P}$
will be a $2\times p$ matrix. The following example demonstrates there may be
more than one graph in the output of a pot $P$ with the same order.

######  Example 1.

Consider the pot
$P=\\{t_{1}=\\{a^{3}\\},,t_{2}=\\{\hat{a}^{3}\\},t_{3}=\\{\hat{a}\\}\\}$. The
construction matrix is

$M_{P}=\begin{bmatrix}3&-3&-1&\\!\\!\\!\framebox{}\\!\\!\\!&0\\\
1&1&1&\\!\\!\\!\framebox{}\\!\\!\\!&1\end{bmatrix}.$

To determine $\mathcal{S}(P)$, row-reduce $M_{P}$ to obtain

$\text{rref}(M_{P})=\begin{bmatrix}1&0&\frac{1}{3}&\\!\\!\\!\framebox{}\\!\\!\\!&\frac{1}{2}\\\
0&1&\frac{2}{3}&\\!\\!\\!\framebox{}\\!\\!\\!&\frac{1}{2}\end{bmatrix}.$

Thus we have

$\mathcal{S}(P)=\left\\{\frac{1}{6k}\left\langle{3k-2z,3k-4z,6z}\right\rangle\mid
k\in\mathbb{Z}^{+},z\in\mathbb{Q}\cap\left[0,\frac{3k}{4}\right]\right\\},$

and P realizes, for example, two nonisomorphic graphs of order 4.

(a) Star graph of order 4 obtained from $z=\frac{3}{4},k=1$.

(b) Multigraph of order 4 obtained from $z=0,k=1$.

Figure 2: A branched junction molecule and its associated tile representation.

##  3 Pots with a 1-Armed Tile

Since complementary cohesive-ends bond together, a tile type of the form
$t=\\{a^{j},\hat{a}^{k}\\}$ may form loops, leaving unmatched cohesive-ends
either of the form $a^{j-k}$ or $\hat{a}^{k-j}$ depending on the magnitude of
$j$ and $k$. For this paper, we only consider multigraphs without loops so we
study tile types with only one cohesive-end type; that is, we restrict
ourselves to the pot of tiles of the form
$P_{1}=\\{t_{1}=\\{a^{e_{1}}\\},t_{2}=\\{\hat{a}^{e_{2}}\\},t_{3}=\\{\hat{a}\\},\ldots\\}$
for some $e_{1}>0$ and $e_{2}>1$. The 1-armed tile $\\{\hat{a}\\}$ ensures
that $P$ will always realize a complete complex. In all but Theorem 3, we
assume $e_{1}\geq e_{2}$. Note that all of the results here can be stated
identically for
$P_{1}^{\prime}=\\{\\{a^{e_{1}}\\},\\{\hat{a}^{e_{2}}\\},\\{\hat{a}\\},\ldots\\}$
where $e_{1}<e_{2}$ by swapping the roles of $a$ and $\hat{a}$. The pot
$P_{1}$ has corresponding construction matrix

$M_{P_{1}}=\begin{bmatrix}e_{1}&-e_{2}&-1&\cdots&\\!\\!\\!\framebox{}\\!\\!\\!&0\\\
1&1&1&\cdots&\\!\\!\\!\framebox{}\\!\\!\\!&1\end{bmatrix}.$

Unless otherwise specified, for the remainder of the paper we reserve the
notation $P$ for the pot
$P=\\{t_{1}=\\{a^{e_{1}}\\},t_{2}=\\{\hat{a}^{e_{2}}\\},t_{3}=\\{\hat{a}\\}\\}$
because $\mathcal{O}(P)\subseteq\mathcal{O}(P_{1})$. That is, any graph
realized by $P$ will also be realized by the pot $P_{1}$. These
simplifications are necessary since determining if a graph of order $n$ is
realized by a pot is known to be NP-hard in general [1].

The spectrum of $P$ is described in Lemma 2.

######  Lemma 2.

Consider the pot $P$ with the associated construction matrix

$M_{P}=\begin{bmatrix}e_{1}&-e_{2}&-1&\\!\\!\\!\framebox{}\\!\\!\\!&0\\\
1&1&1&\\!\\!\\!\framebox{}\\!\\!\\!&1\end{bmatrix}.$ (3)

Then

$\mathcal{S}(P)=\left\\{\frac{1}{k(e_{1}+e_{2})}\left\langle{ke_{2}-(e_{2}-1)z,ke_{1}-(e_{1}+1)z,(e_{1}+e_{2})z}\right\rangle\mid
k\in\mathbb{Z}_{\geq
0},z\in\mathbb{Q}\cap\left[0,\frac{ke_{1}}{e_{1}+1}\right]\right\\}.$

###### Proof.

Row-reduce $M_{P}$ to obtain

$\text{rref}(M_{P})=\begin{bmatrix}1&0&\frac{e_{2}-1}{e_{1}+e_{2}}&\\!\\!\\!\framebox{}\\!\\!\\!&\frac{e_{2}}{e_{1}+e_{2}}\\\
0&1&\frac{e_{1}+1}{e_{1}+e_{2}}&\\!\\!\\!\framebox{}\\!\\!\\!&\frac{e_{1}}{e_{1}+e_{2}}\end{bmatrix}.$
(4)

From Equation 4, we have

$\displaystyle x$ $\displaystyle=\frac{1}{e_{1}+e_{2}}[e_{2}-(e_{2}-1)z],$ (5)
$\displaystyle y$ $\displaystyle=\frac{1}{e_{1}+e_{2}}[e_{1}-(e_{1}+1)z],$ (6)
$\displaystyle z$ $\displaystyle=\frac{1}{e_{1}+e_{2}}[(e_{1}+e_{2})z].$ (7)

Equations 5, 6 and 7 yield the desired result. ∎

We now turn our attention to the set of graphs in the output of $P$. The
following examples demonstrate three types of graphs that are realized by $P$
for any $e_{1}$ and $e_{2}$.

######  Example 2.

The Division Algorithm guarantees there exist unique integers $q$ and $r$ such
that $e_{1}=e_{2}q+r$ where $0\leq r<e_{2}$. The pot $P$ realizes a graph of
order $q+r+1$.

###### Proof.

Set $z=\frac{r}{q+r+1}$ and $k=1$. We will use the substitution
$e_{1}=e_{2}q+r$ in strategic places in this proof. Then by Lemma 2 we have
the particular solution

$\displaystyle\frac{1}{e_{1}+e_{2}}\left\langle
e_{2}-(e_{2}-1)\left(\frac{r}{q+r+1}\right),e_{1}-(e_{1}+1)\left(\frac{r}{q+r+1}\right),(e_{1}+e_{2})\left(\frac{r}{q+r+1}\right)\right\rangle$
$\displaystyle=\frac{1}{e_{1}+e_{2}}\left\langle\frac{e_{2}q+e_{2}r+e_{2}-e_{2}r+r}{q+r+1},\frac{e_{1}q+e_{1}r+e_{1}-e_{1}r-r}{q+r+1},\frac{(e_{1}+e_{2})r}{q+r+1}\right\rangle$
$\displaystyle=\frac{1}{e_{1}+e_{2}}\left\langle\frac{e_{2}q+r+e_{2}}{q+r+1},\frac{e_{1}q+e_{1}-r}{q+r+1},\frac{(e_{1}+e_{2})r}{q+r+1}\right\rangle$
$\displaystyle=\frac{1}{e_{1}+e_{2}}\left\langle\frac{e_{1}+e_{2}}{q+r+1},\frac{e_{1}q+e_{2}q+r-r}{q+r+1},\frac{(e_{1}+e_{2})r}{q+r+1}\right\rangle$
$\displaystyle=\left\langle\frac{1}{q+r+1},\frac{q}{q+r+1},\frac{r}{q+r+1}\right\rangle.$

By Lemma 1, the graph of order $q+r+1$ has tile distribution $(1,q,r)$.

∎

######  Example 3.

The pot $P$ realizes a graph of order $1+e_{1}$.

###### Proof.

Set $z=\frac{e_{1}}{1+e_{1}}$ and $k=1$. Then by Lemma 2, we have the
particular solution

$\displaystyle\frac{1}{e_{1}+e_{2}}\left\langle
e_{2}-(e_{2}-1)\left(\frac{e_{1}}{1+e_{1}}\right),e_{1}-(e_{1}+1)\left(\frac{e_{1}}{1+e_{1}}\right),(e_{1}+e_{2})\left(\frac{e_{1}}{1+e_{1}}\right)\right\rangle$
$\displaystyle=\frac{1}{e_{1}+e_{2}}\left\langle
e_{2}-\frac{e_{1}(e_{2}-1)}{1+e_{1}},e_{1}-e_{1},\frac{e_{1}(e_{1}+e_{2})}{1+e_{1}}\right\rangle$
$\displaystyle=\left\langle\frac{e_{2}(1+e_{1})-e_{1}(e_{2}-1)}{(e_{1}+e_{2})(1+e_{1})},0,\frac{e_{1}}{1+e_{1}}\right\rangle$
$\displaystyle=\left\langle\frac{e_{2}+e_{1}e_{2}-e_{1}e_{2}+e_{1}}{(e_{1}+e_{2})(1+e_{1})},0,\frac{e_{1}}{1+e_{1}}\right\rangle$
$\displaystyle=\left\langle\frac{1}{1+e_{1}},0,\frac{e_{1}}{1+e_{1}}\right\rangle.$

By Lemma 1, the graph of order $1+e_{1}$ can be realized with tile
distribution $(1,0,e_{1})$. ∎

######  Example 4.

The pot $P$ realizes a graph of order $e_{1}+e_{2}$.

###### Proof.

Set $z=0$ and $k=1$. Then by Lemma 2, we have the particular solution
$\frac{1}{e_{1}+e_{2}}\left\langle e_{2},e_{1},0\right\rangle$ and by Lemma 1,
a graph of order $e_{1}+e_{2}$ can be realized with tile distribution
$(e_{2},e_{1},0)$. ∎

######  Example 5.

Let $P=\\{\\{a^{9}\\},\\{\hat{a}^{6}\\},\\{\hat{a}\\}\\}$. Then, according to
Examples 2, 3, and 4, $P$ will realize graphs of order 5, 10, and 15,
respectively. Examples of each of these graphs is provided in Figures 3 and 4.

(a) Graph of order $q+r+1$

(b) Graph of order $1+e_{1}$

Figure 3: Two graphs for $P=\\{\\{a^{9}\\},\\{\hat{a}^{6}\\},\\{\hat{a}\\}\\}$
Figure 4: Graph of order $e_{1}+e_{2}$ for
$P=\\{\\{a^{9}\\},\\{\hat{a}^{6}\\},\\{\hat{a}\\}\\}$

###  3.1 Connections Between $e_{1}$, $e_{2}$, and $\mathcal{O}(P)$

In this section, we demonstrate how certain relationships between $e_{1}$ and
$e_{2}$ will determine the orders of the graphs in $\mathcal{O}(P)$. In
particular, We show that if $G\in\mathcal{O}(P)$, then the order of $G$ is
dependent upon $\text{gcd}(e_{1}+1,-e_{2}+1)$. The most straightforward case
is presented in our first theorem which states the conditions in which $P$
will realize graphs of orders that are multiples of
$\text{gcd}(e_{1}+1,-e_{2}+1)$.

######  Theorem 1.

For the pot $P$, if $\text{gcd}(e_{1}+1,-e_{2}+1)=d\neq 1$, then $P$ realizes
a graph of order $n$ if and only if $n=kd$ where $k\in\mathbb{Z}_{\geq 0}$ and
$n\geq m_{P}$.

###### Proof.

From Equation 3, we have the system of equations

$\left\\{\begin{array}[]{l}e_{1}x-e_{2}y-z=0,\\\ x+y+z=n,\end{array}\right.$
(8)

where $x,y,z\in\mathbb{Z}_{\geq 0}$.

Adding these equations, we obtain

$(e_{1}+1)x+(-e_{2}+1)y=n.$ (9)

This is a linear Diophantine equation in two variables and since
$\text{gcd}(e_{1}+1,-e_{2}+1)=d\neq 1$, a solution to this equation exists if
and only if $n=kd$, which establishes the desired result. ∎

######  Corollary 1.

Let $P$ be a pot where $e_{1}$ is odd and $e_{1}=e_{2}$. Then $P$ realizes a
graph for all orders $n$ where $n\in 2\mathbb{Z}_{\geq 0}$.

###### Proof.

From Theorem 1, it is sufficient to notice that since $e_{1}$ is odd and
$e_{1}=e_{2}$, $\text{gcd}(e_{1}+1,-e_{1}+1)=2$. Hence all graphs realized by
$P$ must have order $2k$ for $k\in\mathbb{Z}_{\geq 0}$.

∎

######  Example 6.

Let $P=\\{\\{a^{3}\\},\\{\hat{a}^{3}\\},\\{\hat{a}\\}\\}$. Then by Corollary
1, $P$ realizes a graph of every even order. Two distinct connected graphs are
provided below: the graph of minimal order 2, and a graph of order 6.

(a) Graph of order 2

(b) Graph of order 6

Figure 5: Two Graphs for $P=\\{\\{a^{3}\\},\\{\hat{a}^{3}\\},\\{\hat{a}\\}\\}$

The case when $e_{1}=e_{2}$ is even is not as immediate since
$gcd(e_{1}+1,-e_{1}+1)=1$. We provide a motivating example in which
$gcd(e_{1}+1,-e_{2}+1)=1$.

######  Example 7.

Consider the pot $P=\\{\\{a^{6}\\},\\{\hat{a}^{4}\\},\\{\hat{a}\\}\\}$. The
associated construction matrix is

$M_{P}=\begin{bmatrix}6&-4&-1&\\!\\!\\!\framebox{}\\!\\!\\!&0\\\
1&1&1&\\!\\!\\!\framebox{}\\!\\!\\!&1\end{bmatrix}$

and $\mathcal{S}(P)=\\{\frac{1}{10k}\langle 4k-3z,6k-7z,10z\rangle\mid
k\in\mathbb{Z}_{\geq 0},z\in\mathbb{Q}\cap[0,\frac{6k}{7}]\\}$. When $k=1$ and
$z=\frac{1}{2}$ we obtain a graph of order 4 with tile distribution $(1,1,2)$,
which is a graph of minimal order in $\mathcal{O}(P)$ (see Figure 6). Notice
that from Equation 9, there is an associated linear Diophantine equation
$7x-3y=n$. Software can be used to verify that the pot $P$ does not realize a
graph of every order; i.e. the results of Theorem 1 do not generalize when
$gcd(e_{1}+1,-e_{2}+1)=1$.

Figure 6: Graph of order 4 for
$\\{\\{a^{6}\\},\\{\hat{a}^{4}\\},\\{\hat{a}\\}\\}$

There are some important observations from Example 7. It appears $P$ realizes
a graph for all orders $n$, except when $n=1,2,3,6$. Notice the smallest order
graph realized by $P$ is order 4, but $P$ does not realize a graph of order 5.
Theorem 2 generalizes the idea that there is some lower bound after which $P$
will realize a graph of any order and this lower bound may not be the order of
the smallest graph realized by $P$.

######  Definition 6.

Let $S_{P}=\\{n\mid n+k\text{ is the order of some }G\in\mathcal{O}(P)\text{
for every }k\in\mathbb{N}\\}$. The lower density bound of $P$ is
$\zeta=\text{min}(S_{P})$.

That is, the lower density bound $\zeta$ is the smallest order for which $P$
realizes a graph of every order larger than $\zeta$.

In general, it is difficult to predict $\zeta$ for $P$. However, Theorem 2
provides a lower bound that is close to $\zeta$.

######  Theorem 2.

Consider the pot $P$ where $\text{gcd}(e_{1}+1,-e_{2}+1)=1$. Then $P$ realizes
a graph for every order $n$ with
$n\geq\text{max}\left\\{\frac{(e_{1}+1)(e_{1}+e_{2})}{e_{1}},\frac{(e_{2}-1)(e_{1}+e_{2})}{e_{2}}\right\\}$.

###### Proof.

From Equation 9, $P$ realizes a graph $G$ of order $n$ if and only if
$(e_{1}+1)x+(-e_{2}+1)y=n$ for some $x$ and $y$. Solving for $y$ and defining
$y=f(x)$ gives the function

$f(x)=\frac{n-(e_{1}+1)x}{-e_{2}+1}.$

Since we only consider nonnegative solutions $(x,f(x))$ to Equation 9 (i.e.
$x\geq 0$ and $y=f(x)\geq 0$), then we will find upper bounds for $x$ and
$f(x)$ to guarantee that a solution exists. The key observation is to notice
$z=n-(x+f(x))$ from Equation 8. Thus, substituting for $f(x)$ we have

$z=\frac{-e_{2}n+(e_{1}+e_{2})x}{-e_{2}+1}.$

To find the upper bound on $x$ and $f(x)$, we determine the value for which
$z=0$. When $z\geq 0$, we have $x\leq\frac{e_{2}n}{e_{1}+e_{2}}$. This
provides the bounds

$\left\\{\begin{array}[]{l}0\leq x\leq\frac{e_{2}n}{e_{1}+e_{2}},\\\ 0\leq
f(x)\leq
f\left(\frac{e_{2}n}{e_{1}+e_{2}}\right)=\frac{e_{1}n}{e_{1}+e_{2}}.\end{array}\right.$

The slope of $f(x)$ is $\frac{e_{1}+1}{e_{2}-1}$. Let
$(x_{1},f(x_{1}))=\text{min}\\{(x,f(x))\in\mathbb{Z}^{2}\mid x\geq
e_{2}-1\text{ and }f(x)\geq e_{1}+1\\}$. The slope of $f(x)$ guarantees

$\left\\{\begin{array}[]{l}0\leq x_{1}-(e_{2}-1)<e_{2}-1,\\\ 0\leq
f(x_{1})-(e_{1}+1)<e_{1}+1,\end{array}\right.$

with $(x_{1}-(e_{2}-1),f(x_{1})-(e_{1}+1))\in\mathbb{Z}^{2}$. Thus an integer
point is guaranteed if the inequalities

$\left\\{\begin{array}[]{l}e_{2}-1\leq\frac{e_{2}n}{e_{1}+e_{2}},\\\
e_{1}+1\leq\frac{e_{1}n}{e_{1}+e_{2}},\end{array}\right.$

are both satisfied (see Figure 7). Thus, by solving both inequalities for $n$,
we conclude that $P$ realizes a graph for every $n$ with
$n\geq\text{max}\left\\{\frac{(e_{1}+1)(e_{1}+e_{2})}{e_{1}},\frac{(e_{2}-1)(e_{1}+e_{2})}{e_{2}}\right\\}$.

∎

Figure 7: The purple rightmost vertical line and upper horizontal line
represent the bounds on $x$ and $f(x)$, respectively, while the black lines
represent $y=e_{1}+1$ and $x=e_{2}-1$. The green line with positive slope is
the function $f(x)$.

######  Remark 1.

We denote the lower bound derived in Theorem 2 by $\eta$. That is,

$\eta=\text{max}\left\\{\frac{(e_{1}+1)(e_{1}+e_{2})}{e_{1}},\frac{(e_{2}-1)(e_{1}+e_{2})}{e_{2}}\right\\}.$

Despite the fact that $\zeta\leq\eta$, there are only finitely many orders to
check for a pot $P$ to determine the value of $\zeta$. That is, one need only
check all orders for $m_{P}\leq n\leq\eta$, which can be done using software.

###  3.2 Connected and Disconnected Graphs

Knowing orders of the graphs that can be realized by $P$ allows us to address
the next research question related to the types of graphs realized by $P$. The
following theorem demonstrates when an arbitrary pot realizes a disconnected
graph. Notice that the theorem below is applicable to any pot of tiles with
any number of bond-edge types.

######  Theorem 3.

The pot $P_{j}=\\{t_{1},t_{2},\ldots,t_{j}\\}$ realizes a disconnected graph
$G$ of order $n$ if and only if for at least one tile distribution
$(R_{1},\ldots,R_{j})$ associated to $G$,

$(R_{1},\ldots,R_{j})=\sum_{i=1}^{m}(R_{1i},\ldots,R_{ji}),$

where each $j$-tuple $(R_{1i},\ldots,R_{ji})$ is a tile distribution of
$P_{j}$ that realizes a graph of order less than $n$.

###### Proof.

Suppose $P_{j}$ realizes a disconnected graph $G$ of order $n$ and let
$(R_{1},\ldots,R_{j})$ be the tile distribution which realizes $G$. Then the
graph $G$ is a union of disjoint subgraphs; that is,

$G=\bigcup_{i=1}^{m}H_{i}$ (10)

where $V(H_{i})\cap V(H_{j})=\varnothing$ for $i\neq j$. Since each $H_{i}$ is
a graph, and hence a complete complex, there must be some tile distribution,
namely $(R_{1i},\ldots,R_{ji})$, that realizes $H_{i}$. Further, since each
$H_{i}\subset G$, it follows that $R_{ki}\leq R_{k}$ for all $1\leq k\leq j$.
Thus we translate Equation 10 into the language of tile distributions to
arrive at

$(R_{1},\ldots,R_{j})=\sum_{i=1}^{m}(R_{1i},\ldots,R_{ji}).$

Conversely, suppose $P_{j}$ realizes graphs $H_{i}$ with corresponding tile
distributions $(R_{1i},\ldots,R_{ji})$ such that

$(R_{1},\ldots,R_{j})=\sum_{i=1}^{m}(R_{1i},\ldots,R_{ji})\text{ and
}R_{1}+R_{2}+\cdots+R_{j}=n,$

then it follows immediately that $P_{j}$ realizes a disconnected graph of
order $n$ with tile distribution $(R_{1},\ldots,R_{j})$. ∎

Theorem 3 provides the conditions under which the pot
$P=\\{\\{a^{e_{1}}\\},\\{\hat{a}^{e_{2}}\\},\\{\hat{a}\\}\\}$ will realize
disconnected graphs as shown by the following two corollaries.

######  Corollary 2.

Let $\text{gcd}(e_{1}+1,-e_{2}+1)=d\neq 1$. The pot $P$ realizes a
disconnected graph of order $n$ if and only if

$n=n_{1}+n_{2}+\cdots+n_{\ell}$

where $n_{i}=k_{i}d$ for some $k_{i}\in\mathbb{Z}_{\geq 0}$ and $n_{i}\geq
m_{P}$.

###### Proof.

The proof is immediate from Theorem 1 and Theorem 3. ∎

######  Corollary 3.

For the pot $P$, if $\text{gcd}(e_{1}+1,-e_{2}+1)=1$ and
$n=n_{1}+n_{2}+\cdots+n_{\ell}$ where each $n_{i}\geq\zeta$, then $P$ realizes
a disconnected graph of order $n$.

###### Proof.

The proof is immediate from Definition 6 and Theorem 3. ∎

######  Example 8.

Consider the pot $P=\\{\\{a^{7}\\},\\{\hat{a}^{4}\\},\\{\hat{a}\\}\\}$. From
computational software, it appears that $\zeta=7$; that is, $P$ realizes a
graph of every order greater than or equal to order 7. Thus, $P$ will realize
a disconnected graph of order 15 in which one component is a subgraph of order
7 and the other component is a subgraph of order 8. However, $P$ will also
realize a disconnected graph of order 12 (See Figure 8). This shows that the
converse of Corollary 3 is not necessarily true.

Figure 8: Disconnected graph of order 12 for
$\\{\\{a^{7}\\},\\{\hat{a}^{4}\\},\\{\hat{a}\\}\\}$

Given a tile distribution $(R_{1},R_{2},R_{3})$ for the pot $P$, the following
theorem establishes a relationship between $R_{1}$ and $R_{2}$ that indicates
when any graph realized by $P$ is necessarily disconnected.

######  Theorem 4.

Let $G\in\mathcal{O}(P)$ and let $(R_{1},R_{2},R_{3})$ be a tile distribution
that constructs $G$. If $1+R_{2}(e_{2}-1)<R_{1}$, then $G$ is disconnected.

###### Proof.

Suppose $G\in\mathcal{O}(P)$ where $G=H_{1}\cup H_{2}$ and $H_{1}\cap
H_{2}=\emptyset$. We will show that despite maximizing the number of vertices
of tile-type $t_{1}$ in $H_{1}$, the subgraph $H_{2}$ will be nonempty (i.e.
$G$ is disconnected).

If $H_{2}$ is empty, then $H_{1}$ must contain $R_{2}$ vertices of tile type
$t_{2}$. To maximize the number of vertices of tile-type $t_{1}$, $H_{1}$ must
be acylic; i.e. $H_{1}$ is a tree. Consider the subgraph of $H_{1}$ whose
vertex set is only vertices of tile-types $t_{1}$ and $t_{2}$; call this
subgraph $H_{1}^{\prime}$. Since there are $R_{2}$ vertices of tile-type
$t_{2}$, there must be $e_{2}R_{2}$ edges and $e_{2}R_{2}+1$ vertices in
$H_{1}^{\prime}$. Thus, there can be at most $e_{2}R_{2}+1-R_{2}$ vertices of
tile-type $t_{1}$ in $H_{1}^{\prime}$ and hence, in $H_{1}$.

If $1+R_{2}(e_{2}-1)<R_{1}$, then $V(H_{2})$ must contain vertices labeled
with tile-type $t_{1}$. Therefore, $G$ will be disconnected. ∎

The question of when connected graphs are realized by $P$ remains open at the
time of writing. The algorithms in Section 4 provide a partial answer to this
question.

##  4 Connected Graph Algorithms

Section 3 establishes the conditions under which a pot of the form
$P=\\{\\{a^{e_{1}}\\},\\{\hat{a}^{e_{2}}\\},\\{\hat{a}\\}\\}$ realizes a
connected or disconnected graph. In this section, we provide two algorithms
which will construct a connected graph from $P$. Theorem 4 suggests a
connected graph may exist if $1+R_{2}(e_{2}-1)\geq R_{1}$ and the desired
order for a graph satisfies Theorem 1 or 2; the algorithms that follow rely on
this inequality.

###  4.1 Path Algorithm

If $1+R_{2}(e_{2}-1)\geq R_{1}$, then the following algorithm will output a
connected graph. Note that the algorithm has been written based upon the
assumption that $R_{1}\geq R_{2}$. If $R_{1}<R_{2}$, then the roles of $R_{1}$
and $R_{2}$, and $t_{1}$ and $t_{2}$ can be swapped in steps 1, 2, and 3 in
order to produce a connected graph.

Input: A pot
$P=\\{t_{1}=\\{a^{e_{1}}\\},t_{2}=\\{\hat{a}^{e_{2}}\\},t_{3}=\\{\hat{a}\\}\\}$
with corresponding tile distribution $(R_{1},R_{2},R_{3})$

Output: A labeled connected graph of order $R_{1}+R_{2}+R_{3}$

  1. 1.

Form a path graph on $2R_{2}-1$ vertices where the vertices are labeled as in
Figure 9. That is, let

$\lambda(v_{k})=\left\\{\begin{array}[]{l}t_{2}\text{ if }k\text{ odd}\\\
t_{1}\text{ if }k\text{ even},\end{array}\right.$

where $k\in\\{1,\ldots,2R_{2}-1\\}.$

Figure 9: Graph after step 1 of Algorithm 4.1 including unmatched half-edges
on $t_{1}$ and $t_{2}$

  2. 2.

If $R_{1}-(R_{2}-1)<e_{2}-1$, then attach one half-edge from each of the
remaining $R_{1}-(R_{2}-1)$ copies of $t_{1}$ to vertex $v_{1}$. Go to step 4.
Else, attach one half-edge from each of $e_{2}-1$ copies of $t_{1}$ to vertex
$v_{1}$. Set $\texttt{counter}=R_{1}-(R_{2}-1)-(e_{2}-1)$.

  3. 3.

If $\texttt{counter}<e_{2}-2$, then attach one half-edge from each of the
remaining counter copies of $t_{1}$ to vertex $v_{3}$. Else, attach one half-
edge from each of $e_{2}-2$ copies of $t_{1}$ to vertex $v_{3}$. Update
$\texttt{counter}=\texttt{counter}-(e_{2}-2)$. Continue in this way
sequentially for vertices $v_{5}$, $v_{7},\ldots$ until $\texttt{counter}=0$.
Note if $\texttt{counter}>0$ at the end of the sequence (i.e. at vertex
$v_{2R_{2}-1}$) it may be necessary to attach one half-edge from $e_{2}-1$
copies of $t_{1}$ to vertex $v_{2R_{2}-1}$.

  4. 4.

Attach any unpaired half-edges from the $t_{2}$ tile types to any unpaired
half-edges from the $t_{1}$ tile types.

  5. 5.

Attach each $t_{3}$ to an unpaired half-edge from $t_{1}$.

###### Proof.

Let $G$ be a graph constructed by Algorithm 4.1. We note that by construction,
$R_{2}$ vertices are labeled $t_{2}$ in Step 1. At the end of Step 3, $R_{1}$
vertices are labeled $t_{1}$ and at the end of Step 5, $R_{3}$ vertices are
labeled $t_{3}$. Thus, the graph constructed is realized by $P$.

We next prove that $G$ is a connected graph by showing there are no unmatched
half-edges by the end of the algorithm.

In the multiset $P_{\lambda}(G)$, there are $e_{1}R_{1}$ total half-edges
labeled $a$ associated to tile type $t_{1}$. In Step 1 of the algorithm, there
are $2(R_{2}-1)$ half-edges labeled $a$ that are joined to half-edges labeled
$\hat{a}$, and in Steps 2 and 3, there are an additional $R_{1}-(R_{2}-1)$
half-edges labeled $a$ joined to half-edges labeled $\hat{a}$. At the end of
Step 3, there are
$e_{1}R_{1}-2(R_{2}-1)-(R_{1}-(R_{2}-1))=(e_{1}-1)R_{1}-R_{2}+1$ half-edges
labeled $a$ that are unmatched.

In $P_{\lambda}(G)$, there are $e_{2}R_{2}$ total half-edges labeled $\hat{a}$
associated to tile type $t_{2}$. In Step 1, $2+2(R_{2}-2)$ half-edges labeled
$\hat{a}$ are joined to half-edges labeled $a$. In Steps 2 and 3,
$R_{1}-(R_{2}-1)$ half-edges labeled $\hat{a}$ are joined to half-edges
labeled $a$. Thus, at the end of Step 3, there are
$e_{2}R_{2}-(2+2(R_{2}-2))-(R_{1}-(R_{2}-1)=(e_{2}-1)R_{2}-R_{1}+1$ half-edges
labeled $\hat{a}$ that are unmatched.

Note that

$(e_{1}-1)R_{1}-R_{2}+1-\left((e_{2}-1)R_{2}-R_{1}+1\right)=e_{1}R_{1}-e_{2}R_{2}.$

Since $e_{1}>e_{2}$ and $R_{1}\geq R_{2}$, then $e_{1}R_{1}-e_{2}R_{2}>0$.
That is, there must be more unmatched half-edges labeled $a$ than $\hat{a}$ at
the end of Step 3. This ensures that all unmatched half-edges labeled
$\hat{a}$ will be joined to half-edges labeled $a$ in Step 4.

There will be exactly $e_{1}R_{1}-e_{2}R_{2}$ unmatched half-edges labeled $a$
at the end of Step 4. Since $e_{1}R_{1}-e_{2}R_{2}=R_{3}$ by Equation 8, then
Step 5 guarantees all remaining half-edges can be matched to a vertex labeled
$t_{3}$. Thus, there are no unmatched half-edges by the end of the algorithm.

∎

######  Theorem 5.

If $1+R_{2}(e_{2}-1)\geq R_{1}$, then there exists a connected graph
$G\in\mathcal{O}(P)$.

The proof of this theorem is immediate from Algorithm 4.1.

######  Example 9.

Consider $P=\\{\\{a^{4}\\},\\{\hat{a}^{3}\\},\\{\hat{a}\\}\\}$. $P$ realizes a
graph of order 29 with a tile distribution of $(7,3,19)$. The output of
Algorithm 4.1 is shown in Figure 10.

Figure 10: A graph of order 29 constructed using Algorithm 4.1

###  4.2 Cycle Algorithm

Ring structures naturally occur in many biological systems [3, 6]. For this
reason, we have created an algorithm to construct a connected graph from a
cycle graph. The limitation that occurs is that this algorithm only works when
$R_{1}\leq R_{2}$.

Input: A pot of the form
$P=\\{t_{1}=\\{a^{e_{1}}\\},t_{2}=\\{\hat{a}^{e_{2}}\\},t_{3}=\\{\hat{a}\\}\\}$
with corresponding tile distribution $R_{1},R_{2},R_{3}$.

Output: A labeled connected graph of order $R_{1}+R_{2}+R_{3}$.

  1. 1.

Form a cycle graph on $2R_{1}$ vertices. Alternate the labels on the vertices
for $t_{1}$ and $t_{2}$. That is, choose a vertex to be $v_{1}$, then set
$\lambda(v_{2k-1})=t_{1}$ and $\lambda({v_{2k}})=t_{2}$ for
$k\in\\{1,\ldots,R_{1}\\}$. See Figure 11.

Figure 11: Graph after step 1 of Algorithm 4.2 including unmatched half-edges
on $t_{1}$ and $t_{2}$

  2. 2.

Attach $\lfloor\frac{e_{2}-2}{2}\rfloor$ half-edges from $v_{2k}$ to
$v_{2k-1}$ and attach $\lceil\frac{e_{2}-2}{2}\rceil$ half-edges from $v_{2k}$
to $v_{2k+1}$ for each $k\in\\{1,\ldots,R_{1}\\}$. Due to the cyclic subgraph
from step 1, we note $v_{1}=v_{2k+1}$ for this process.

  3. 3.

If $R_{2}-R_{1}<e_{1}-e_{2}$, then attach the remaining $R_{2}-R_{1}$ copies
of $t_{2}$ to the half-edges of $t_{1}$ on $v_{1}$ using exactly one half-edge
for each copy of $t_{2}$. Go to step 5. Else, attach $e_{1}-e_{2}$ copies of
$t_{2}$ to the half-edges of $t_{1}$ on $v_{1}$ using exactly one half-edge of
each copy of $t_{2}$. Update $\texttt{counter}=R_{2}-R_{1}-(e_{1}-e_{2})$

  4. 4.

If $\texttt{counter}<e_{1}-e_{2}$, then attach counter copies of $t_{2}$ to
the half-edges of $t_{1}$ on $v_{3}$ using exactly one half-edge of each copy
of $t_{2}$. Else, attach $e_{1}-e_{2}$ copies of $t_{2}$ to the half-edges of
$t_{1}$ on $v_{3}$ using exactly one half-edge for each copy of $t_{2}$.
Update $\texttt{counter}=\texttt{counter}-(e_{1}-e_{2})$. Continue in this way
sequentially for vertices $v_{5},v_{7},\ldots$ until $\texttt{counter}=0$.

  5. 5.

If $R_{1}\neq R_{2}$, attach $(R_{2}-R_{1})(e_{2}-1)$ unmatched half-edges
from the vertices labeled with $t_{1}$ to the unmatched half-edges of the
vertices labeled with $t_{2}$. Else, move to step 6.

  6. 6.

Attach $R_{1}(e_{1}-e_{2})-e_{2}(R_{2}-R_{1})$ half-edges labeled $a$ from
vertices labeled with $t_{1}$ to $R_{3}$ vertices labeled with $t_{3}$.

###### Proof.

Form the graph $G$ with the labeling prescribed by Step 1 of Algorithm 4.2.
Our aim is to show that all the remaining tiles can be attached to the
vertices in $G$.

After steps 1 and 2, there are
$e_{1}-\left(\lfloor\frac{e_{2}-2}{2}\rfloor+\lceil\frac{e_{2}-2}{2}\rceil\right)-2=e_{1}-(e_{2}-2)-2=e_{1}-e_{2}$
unpaired half-edges on each vertex labeled $t_{1}$. Thus, there is a total of
$R_{1}(e_{1}-e_{2})$ unmatched $a$’s. Additionally, all tiles of type $t_{1}$
and $R_{1}$ tiles of type $t_{2}$ have been used to label the vertices of $G$,
and all of the arms of the tiles of type $t_{2}$ in $G$ have been matched.

We must ensure there are sufficiently many unmatched edges labeled $a$ for the
remaining tiles of type $t_{2}$, which is equivalent to showing
$R_{2}-R_{1}<R_{1}(e_{1}-e_{2})$. This can be shown using the substitution
$e_{1}R_{1}=e_{2}R_{2}+R_{3}$ from Equation 8 as follows:

$\displaystyle R_{1}(e_{1}-e_{2})$ $\displaystyle=e_{1}R_{1}-e_{2}R_{1}$
$\displaystyle=R_{3}+e_{2}R_{2}-e_{2}R_{1}$
$\displaystyle=R_{3}+e_{2}(R_{2}-R_{1})$ $\displaystyle\geq
e_{2}(R_{2}-R_{1})$ $\displaystyle>R_{2}-R_{1}.$

After step 5, the tiles of type $t_{2}$ that were added in steps 3 and 4 have
$(R_{2}-R_{1})(e_{2}-1)$ unmatched half-edges. To ensure each half-edge can be
matched to a free half-edge on a tile of type $t_{1}$, we must show
$(R_{2}-R_{1})(e_{2}-1)\leq R_{1}(e_{1}-e_{2})-(R_{2}-R_{1})$. Using the
substitution $e_{1}R_{1}-e_{2}R_{2}=R_{3}$, we have:

$\displaystyle R_{1}(e_{1}-e_{2})-(R_{2}-R_{1})$
$\displaystyle=e_{1}R_{1}-e_{2}R_{1}-R_{2}+R_{1}$
$\displaystyle=e_{1}R_{1}-e_{2}R_{1}-e_{2}R_{2}+e_{2}R_{2}-R_{2}+R_{1}$
$\displaystyle=e_{1}R_{1}-e_{2}R_{2}+(e_{2}R_{2}-R_{2}-e_{2}R_{1}+R_{1})$
$\displaystyle=R_{3}+(R_{2}-R_{1})(e_{2}-1)$
$\displaystyle\geq(R_{2}-R_{1})(e_{2}-1).$

With all of the arms from tiles of type $t_{2}$ matched, we finally need to
check that there are exactly the number of unmatched half-edges on tiles of
type $t_{1}$ as there are tiles of type $t_{3}$. That is, we need to show
$R_{3}=R_{1}(e_{1}-e_{2})-e_{2}(R_{2}-R_{1})$:

$\displaystyle R_{1}(e_{1}-e_{2})-e_{2}(R_{2}-R_{1})$
$\displaystyle=e_{1}R_{1}-e_{2}R_{1}-e_{2}R_{2}+e_{2}R_{1}$
$\displaystyle=e_{1}R_{1}-e_{2}R_{2}$ $\displaystyle=R_{3}.$

Thus, $G$ is a connected graph and $G\in\mathcal{O}(P)$ using tile
distribution $(R_{1},R_{2},R_{3})$. ∎

######  Example 10.

Consider $P=\\{\\{a^{6}\\},\\{\hat{a}^{4}\\},\\{\hat{a}\\}\\}$. Then $P$
realizes a graph of order 19 with a tile distribution of $(7,10,2)$. The
output of Algorithm 4.2 is shown in Figure 12.

Figure 12: A graph of order 19 constructed using Algorithm 4.2

##  5 Conclusion

We have shown that, given a pot of tiles with one bond-edge type and a 1-armed
tile, we can determine the orders of the complete complexes that can be
realized by the pot. To a lesser extent, we can also characterize whether
these complete complexes will be disconnected or connected complexes. At the
time of writing, the entire case involving a pot with one bond-edge type (i.e.
a $2\times p$ construction matrix) is close to being completely understood.
Three primary questions remain to be explored:

  1. 1.

What is a formula for $\zeta$ in terms of $e_{1}$ and $e_{2}$?

  2. 2.

Does there exist a pot where $\zeta=\eta$?

  3. 3.

Do these results extend to pots of the form
$P=\\{\\{a^{e_{1}}\\},\\{\hat{a}^{e_{2}}\\},\\{\hat{a}^{e_{3}}\\}\\}$ where
$1<e_{3}<e_{2}$?

Although the first question remains open, our results provide a lower bound
which is “close” to $\zeta$. This means that, for any pot $P$ satisfying the
relatively prime condition, there are only finitely many orders to check
between the order of the minimal graph of $P$ and the corresponding $\eta$.

With the third question, we have some indication that the results in this
paper extend to pots that do not possess a 1-armed tile, but more research is
needed in this area. Considering the conditions that occur when
$\text{gcd}(e_{1}+1,-e_{2}+1)=d\neq 1$, it would be reasonable to start in
this setting rather than the relatively prime setting.

The difficulty of determining which graphs $G$ are in $\mathcal{O}(P)$
increases dramatically when moving from pots with one bond-edge type to pots
with two bond-edge types. Preliminary research suggests the results here do
not necessarily generalize to the two bond-edge type case.

## References

  * [1] L. Almodóvar, J. Ellis-Monaghan, A. Harsy, C. Johnson, and J. Sorrells.  Computational complexity and pragmatic solutions for flexible tile-based dna self-assembly.  Under review, http://arxiv.org/abs/2108.00035.
  * [2] J. Chen and N. Neeman.  Synthesis from dna of a molecule with the connectivity of a cube.  Nature, 350:631–633, 1991.
  * [3] Y. Chen, C. Rosenkranz, S. Hirte, and J. Kirchmair.  Ring systems in natural products: structural diversity, physicochemical properties, and coverage by synthetic compounds.  Nat. Prod. Rep., 39:1544–1556, 2022.  doi:10.1039/D2NP00001F.
  * [4] J. Ellis-Monaghan, N. Jonoska, and G. Pangborn.  Tile-based DNA nanostructures: mathematical design and problem encoding.  In Algebraic and combinatorial computational biology, Math. Sci. Eng., pages 35–60. Academic Press, London, 2019.
  * [5] J. Ellis-Monaghan, G. Pangborn, L. Beaudin, D. Miller, N. Bruno, and A. Hashimoto.  Minimal tile and bond-edge types for self-assembling dna graphs.  In Discrete and Topological Models in Molecular Biology, pages 241–270. Springer, 2014.
  * [6] P. Ertl.  Magic rings: Navigation in the ring chemical space guided by the bioactive rings.  Journal of Chemical Information and Modeling, 62:2164–2170, 2021\.  doi:10.1021/acs.jcim.1c00761.
  * [7] R. Goodman, I. Schaap, C. Tardin, C. Erben, R. Berry, C. Schmidt, and A. Turberfield.  Rapid chiral assembly of rigid dna building blocks for molecular nanofabrication.  Science, 310:1661–1665, 2005.
  * [8] N. Jonoska, G. L. McColm, and A. Staninska.  On stoichiometry for the assembly of flexible tile DNA complexes.  Nat. Comput., 10(3):1121–1141, 2011.  doi:10.1007/s11047-009-9169-1.
  * [9] N. Jonoska, P. Sa-Ardyen, and N. C. Seeman.  Computation by self-assembly of dna graphs.  Genetic Programming and Evolvable Machines, 4:123–137, 2003.
  * [10] C. Mao, W. Sun, and N. Seeman.  Designed two-dimensional dna holliday junction arrays visualized by atomic force microscopy.  Journal of the American Chemical Society, 121(23):5437–5443, 1999\.
  * [11] P. W. K. Rothemund, N. Papadakis, and E. Winfree.  Algorithmic self-assembly of dna sierpinski triangles.  PLoS biology, 2(12):e424, 2004.
  * [12] P. Sa-Ardyen, N. Jonoska, and N. C. Seeman.  Self-assembling dna graphs.  In DNA Computing: 8th International Workshop on DNA-Based Computers, DNA8 Sapporo, Japan, June 10–13, 2002 Revised Papers 8, pages 1–9. Springer, 2003.
  * [13] N. C. Seeman.  Nucleic acid junctions and lattices.  Journal of Theoretical Biology, 99:237–247, 1982.
  * [14] N. C. Seeman.  An overview of structural dna nanotechnology.  Molecular biotechnology, 37(3):246, 2007.
  * [15] W. Shih, J. Quispe, and G. Joyce.  A 1.7-kilobase single stranded dna folds into a nanoscale octahedron.  Nature, 427:618–621, 2004.
  * [16] E. Winfree, F. Liu, L. A. Wenzler, and N. C. Seeman.  Design and self-assembly of two-dimensional dna crystals.  Nature, 394(6693):539–544, 1998.
  * [17] E. Winfree, X. Yang, and N. C. Seeman.  Universal computation via self-assembly of dna: Some theory and experiments.  1999\.
  * [18] Y. Zhang and N. Seeman.  The construction of a dna truncated octahedron.  Journal of the American Chemical Society, 116(5):1661–1669, 1994\.