Search

The search for the electromagnetic counterparts to gravitational wave (GW) events has been rapidly gathering pace in recent years thanks to the increasing number and capabilities of both gravitational wave detectors and wide field survey telescopes. Difficulties remain, however, in detecting these counterparts due to their inherent scarcity, faintness and rapidly evolving nature. To find these counterparts, it is important that one optimises the observing strategy for their recovery. This can be difficult due to the large number of potential variables at play. Such follow-up campaigns are also capable of detecting hundreds or potentially thousands of unrelated transients, particularly for GW events with poor localisation. Even if the observations are capable of detecting a counterpart, finding it among the numerous contaminants can prove challenging. Here we present the Gravitational wave Electromagnetic RecovRY code (GERry) to perform detailed analysis and survey-agnostic quantification of observing campaigns attempting to recover electromagnetic counterparts. GERry considers the campaign's spatial, temporal and wavelength coverage, in addition to Galactic extinction and the expected counterpart light curve evolution from the GW 3D localisation volume. It returns quantified statistics that can be used to: determine the probability of having detected the counterpart, identify the most promising sources, and assess and refine strategy. Here we demonstrate the code to look at the performance and parameter space probed by current and upcoming wide-field surveys such as GOTO & VRO., Comment: 19 pages, 11 figures, submitted to SPIE Astronomical Telescopes + Instrumentation 2024

The Gravitational-wave Optical Transient Observer (GOTO) is a project dedicated to identifying optical counter-parts to gravitational-wave detections using a network of dedicated, wide-field telescopes. After almost a decade of design, construction, and commissioning work, the GOTO network is now fully operational with two antipodal sites: La Palma in the Canary Islands and Siding Spring in Australia. Both sites host two independent robotic mounts, each with a field-of-view of 44 square degrees formed by an array of eight 40 cm telescopes, resulting in an instantaneous 88 square degree field-of-view per site. All four telescopes operate as a single integrated network, with the ultimate aim of surveying the entire sky every 2-3 days and allowing near-24-hour response to transient events within a minute of their detection. In the modern era of transient astronomy, automated telescopes like GOTO form a vital link between multi-messenger discovery facilities and in-depth follow-up by larger telescopes. GOTO is already producing a wide range of scientific results, assisted by an efficient discovery pipeline and a successful citizen science project: Kilonova Seekers., Comment: 8 pages, 5 figures, submitted to SPIE Astronomical Telescopes + Instrumentation 2024

AM CVn-type systems are ultracompact, helium-accreting binary systems which are evolutionarily linked to the progenitors of thermonuclear supernovae and are expected to be strong Galactic sources of gravitational waves detectable to upcoming space-based interferometers. AM CVn binaries with orbital periods $\lesssim$ 20--23 min exist in a constant high state with a permanently ionised accretion disc. We present the discovery of TIC 378898110, a bright ($G=14.3$ mag), nearby ($309.3 \pm 1.8$ pc), high-state AM CVn binary discovered in TESS two-minute-cadence photometry. At optical wavelengths this is the third-brightest AM CVn binary known. The photometry of the system shows a 23.07172(6) min periodicity, which is likely to be the `superhump' period and implies an orbital period in the range 22--23 min. There is no detectable spectroscopic variability. The system underwent an unusual, year-long brightening event during which the dominant photometric period changed to a shorter period (constrained to $20.5 \pm 2.0$ min), which we suggest may be evidence for the onset of disc-edge eclipses. The estimated mass transfer rate, $\log (\dot{M} / \mathrm{M_\odot} \mathrm{yr}^{-1}) = -6.8 \pm 1.0$, is unusually high and may suggest a high-mass or thermally inflated donor. The binary is detected as an X-ray source, with a flux of $9.2 ^{+4.2}_{-1.8} \times 10^{-13}$ erg cm$^{-2}$ s$^{-1}$ in the 0.3--10 keV range. TIC 378898110 is the shortest-period binary system discovered with TESS, and its large predicted gravitational-wave amplitude makes it a compelling verification binary for future space-based gravitational wave detectors., Comment: 15 pages, 14 figures. Accepted to MNRAS

We consider classes of graphs, which we call thick graphs, that have the vertices of a corresponding thin graph replaced by cliques and the edges replaced by cobipartite graphs. In particular, we consider the case of thick forests, which are a class of perfect graphs. Whereas recognising membership of most classes of thick graphs is NP-complete, we show that thick forests can be recognised in polynomial time. We consider two well-studied combinatorial problems on thick graphs, independent sets and proper colourings. Since finding the independence or chromatic number of a perfect graph is well known to be in polynomial time, we examine the complexity of counting all independent sets and colourings in a thick forest. Finally, we consider two extensions of our results to larger classes: thick triangle-free graphs and thick bounded-treewidth graphs., Comment: 44 pages, 19 figures

White dwarfs, the extremely dense remnants left behind by most stars after their death, are characterised by a mass comparable to that of the Sun compressed into the size of an Earth-like planet. In the resulting strong gravity, heavy elements sink toward the centre and the upper layer of the atmosphere contains only the lightest element present, usually hydrogen or helium. Several mechanisms compete with gravitational settling to change a white dwarf's surface composition as it cools, and the fraction of white dwarfs with helium atmospheres is known to increase by a factor ~2.5 below a temperature of about 30,000 K; therefore, some white dwarfs that appear to have hydrogen-dominated atmospheres above 30,000 K are bound to transition to be helium-dominated as they cool below it. Here we report observations of ZTF J203349.8+322901.1, a transitioning white dwarf with two faces: one side of its atmosphere is dominated by hydrogen and the other one by helium. This peculiar nature is likely caused by the presence of a small magnetic field, which creates an inhomogeneity in temperature, pressure or mixing strength over the surface. ZTF J203349.8+322901.1 might be the most extreme member of a class of magnetic, transitioning white dwarfs -- together with GD 323, a white dwarf that shows similar but much more subtle variations. This new class could help shed light on the physical mechanisms behind white dwarf spectral evolution., Comment: 45 pages, 11 figures

We present the discovery of the eclipsing double white dwarf (WD) binary WDJ 022558.21-692025.38 that has an orbital period of 47.19 min. Following identification with the Transiting Exoplanet Survey Satellite, we obtained time-series ground based spectroscopy and high-speed multi-band ULTRACAM photometry which indicate a primary DA WD of mass 0.40 +- 0.04 Msol and a 0.28 +- 0.02 Msol mass secondary WD, which is likely of type DA as well. The system becomes the third-closest eclipsing double WD binary discovered with a distance of approximately 400 pc and will be a detectable source for upcoming gravitational wave detectors in the mHz frequency range. Its orbital decay will be measurable photometrically within 10 yrs to a precision of better than 1%. The fate of the binary is to merge in approximately 41 Myr, likely forming a single, more massive WD., Comment: Accepted for publication in MNRAS, 8 pages + 2 appendix pages, 6 figures

Wide-field time-domain photometric sky surveys are now finding hundreds of eclipsing white dwarf plus M dwarf binaries, a population encompassing a wealth of information and potential insight into white dwarf and close binary astrophysics. Precise follow-up observations are essential in order to fully constrain these systems and capitalise on the power of this sample. We present the first results from our program of high-speed, multi-band photometric follow-up. We develop a method to measure temperatures, (model-dependent) masses, and radii for both components from the eclipse photometry alone and characterize 34 white dwarf binaries, finding general agreement with independent estimates using an alternative approach while achieving around a factor of two increase in parameter precision. In addition to these parameter estimates, we discover a number of interesting systems -- finding four with sub-stellar secondaries, doubling the number of eclipsing examples, and at least six where we find the white dwarf to be strongly magnetic, making these the first eclipsing examples of such systems and key to investigating the mechanism of magnetic field generation in white dwarfs. We also discover the first two pulsating white dwarfs in detached and eclipsing post-common-envelope binaries -- one with a low-mass, likely helium core, and one with a relatively high mass, towards the upper end of the known sample of ZZ Cetis. Our results demonstrate the power of eclipse photometry, not only as a method of characterising the population, but as a way of discovering important systems that would have otherwise been missed by spectroscopic follow-up., Comment: 12 pages with a 5 page appendix and 14 figures. Accepted for publication in MNRAS

The triangle switch Markov chain is designed to generate random graphs with given degree sequence, but having more triangles than would appear under the uniform distribution. Transition probabilities of the chain depends on a parameter, called the activity, which is used to assign higher stationary probability to graphs with more triangles. In previous work we proved ergodicity of the triangle switch chain for regular graphs. Here we prove ergodicity for all sequences with minimum degree at least 3, and show rapid mixing of the chain when the activity and the maximum degree are not too large. As far as we are aware, this is the first rigorous analysis of a Markov chain algorithm for generating graphs from a a known non-uniform distribution., Comment: 35 pages

The shortest-period binary star system known to date, RX J0806.3+1527 (HM Cancri), has now been observed in the optical for more than two decades. Although it is thought to be a double degenerate binary undergoing mass transfer, an early surprise was that its orbital frequency, $f_0$, is currently increasing as the result of gravitational wave radiation. This is unusual since it was expected that the mass donor was degenerate and would expand on mass loss, leading to a decreasing $f_0$. We exploit two decades of high-speed photometry to precisely quantify the trajectory of HM Cancri, allowing us to find that $\ddot f_0$ is negative, where $\ddot f_0~=~(-5.38\pm2.10)\times10^{-27}$ Hz s$^{-2}$. Coupled with our positive frequency derivative, we show that mass transfer is counteracting gravitational-wave dominated orbital decay and that HM Cancri will turn around within $2100\pm800\,$yrs from now. We present Hubble Space Telescope ultra-violet spectra which display Lyman-$\alpha$ absorption, indicative of the presence of hydrogen accreted from the donor star. We use these pieces of information to explore a grid of permitted donor and accretor masses with the Modules for Experiments in Stellar Astrophysics suite, finding models in good accordance with many of the observed properties for a cool and initially hydrogen-rich extremely-low-mass white dwarf ($\approx0.17\,$M$_\odot$) coupled with a high accretor mass white dwarf ($\approx 1.0\,$M$_\odot$). Our measurements and models affirm that HM~Cancri is still one of the brightest verification binaries for the Laser Interferometer Space Antenna spacecraft., Comment: 12 pages (+5 pages appendix), 9 figures, 6 tables. Accepted for publication in MNRAS

The Gravitational-wave Optical Transient Observer (GOTO) is a wide-field telescope project focused on detecting optical counterparts to gravitational-wave sources. Each GOTO robotic mount holds eight 40 cm telescopes, giving an overall field of view of 40 square degrees. As of 2022 the first two GOTO mounts have been commissioned at the Roque de los Muchachos Observatory on La Palma, Canary Islands, and construction of the second node with two additional 8-telescope mounts has begin at Siding Spring Observatory in New South Wales, Australia. Once fully operational each GOTO mount will be networked to form a robotic, multi-site observatory, which will survey the entire visible sky every two nights and enable rapid follow-up detections of transient sources., Comment: 8 pages, 5 figures, submitted to SPIE Astronomical Telescopes + Instrumentation 2022

With the prevalence of wide-field, time-domain photometric sky surveys, the number of eclipsing white dwarf systems being discovered is increasing dramatically. An efficient method to follow these up will be key to determining any population trends and finding any particularly interesting examples. We demonstrate that multi-band eclipse photometry of binaries containing a white dwarf and an M~dwarf can be used to determine the masses and temperatures of the white dwarfs to better than 5 per cent. For the M~dwarfs we measure their parameters to a precision of better than 6 per cent with the uncertainty dominated by the intrinsic scatter of the M~dwarf mass-radius relationship. This precision is better than what can typically be achieved with low-resolution spectroscopy. The nature of this method means that it will be applicable to LSST data in the future, enabling direct characterisation without follow-up spectroscopy. Additionally, we characterise three new post-common-envelope binaries from their eclipse photometry, finding two systems containing hot helium-core white dwarfs with low-mass companions (one near the brown dwarf transition regime) and a possible detached cataclysmic variable at the lower edge of the period gap., Comment: 10 pages (and appendix), 5 figures, accepted to MNRAS

Gravitational-wave (GW) data contains non-Gaussian noise transients called "glitches". During the third LIGO-Virgo observing run about 24% of all gravitational-wave candidates were in the vicinity of a glitch, while even more events could be affected in future observing runs due to increasing detector sensitivity. This poses a problem since glitches can affect the estimation of GW source parameters, including sky localisation, which is crucial to identify an electromagnetic (EM) counterpart. In this paper we present a study that estimates how much sky localisation is affected by a nearby glitch in low latency. We injected binary black hole (BBH), binary neutron star (BNS) and neutron star-black hole (NSBH) signals into data containing three different classes of glitches: blips, thunderstorms and fast scatterings. The impact of these glitches was assessed by estimating the number of tile pointings that a telescope would need to search over until the true sky location of an event is observed. We found that blip glitches affect the localisation of BBH mergers the most; in the most extreme cases a BBH event is completely missed even by a 20 deg$^2$ field-of-view (FOV) telescope. Thunderstorm glitches have the biggest impact on BBH and NSBH events, especially if there is no third interferometer, while BNS events appear to be not affected. Fast scattering glitches impact low latency localisation only for NSBH signals. For two-interferometer network small (FOV=1 deg$^2$) and large (FOV=20 deg$^2$) telescopes are affected, whereas three-interferometer localisation bias is small enough not to affect large (FOV=20 deg$^2$) telescopes., Comment: 16 pages, 7 figures, 3 tables. Accepted to PRD

Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one triangle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all $d$-regular graphs on $n$ vertices, for all $d\geq 3$. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs., Comment: 19 pages, 17 figures

The Gravitational-wave Optical Transient Observer (GOTO) is a wide-field telescope project focused on detecting optical counterparts to gravitational-wave sources. The GOTO Telescope Control System (G-TeCS) is a custom robotic control system which autonomously manages the GOTO telescope hardware and nightly operations. Since the commissioning the GOTO prototype on La Palma in 2017, development of the control system has focused on the alert handling and scheduling systems. These allow GOTO to receive and process transient alerts and then schedule and carry out observations, all without the need for human involvement. GOTO is ultimately anticipated to include multiple telescope arrays on independent mounts, both on La Palma and at a southern site in Australia. When complete these mounts will be linked to form a single multi-site observatory, requiring more advanced scheduling systems to best optimise survey and follow-up observations., Comment: 12 pages, 6 figures, 2 tables, submitted to SPIE Astronomical Telescopes + Instrumentation 2020

The Gravitational-wave Optical Transient Observer (GOTO) is a wide-field telescope project focused on detecting optical counterparts to gravitational-wave sources. GOTO uses arrays of 40 cm unit telescopes (UTs) on a shared robotic mount, which scales to provide large fields of view in a cost-effective manner. A complete GOTO mount uses 8 unit telescopes to give an overall field of view of 40 square degrees, and can reach a depth of 20th magnitude in three minutes. The GOTO-4 prototype was inaugurated with 4 unit telescopes in 2017 on La Palma, and was upgraded to a full 8-telescope array in 2020. A second 8-UT mount will be installed on La Palma in early 2021, and another GOTO node with two more mount systems is planned for a southern site in Australia. When complete, each mount will be networked to form a robotic, dual-hemisphere observatory, which will survey the entire visible sky every few nights and enable rapid follow-up detections of transient sources., Comment: 8 pages, 5 figures, 1 table, submitted to SPIE Astronomical Telescopes + Instrumentation 2020

The amount of observational data produced by time-domain astronomy is exponentially in-creasing. Human inspection alone is not an effective way to identify genuine transients fromthe data. An automatic real-bogus classifier is needed and machine learning techniques are commonly used to achieve this goal. Building a training set with a sufficiently large number of verified transients is challenging, due to the requirement of human verification. We presentan approach for creating a training set by using all detections in the science images to be thesample of real detections and all detections in the difference images, which are generated by the process of difference imaging to detect transients, to be the samples of bogus detections. This strategy effectively minimizes the labour involved in the data labelling for supervised machine learning methods. We demonstrate the utility of the training set by using it to train several classifiers utilizing as the feature representation the normalized pixel values in 21-by-21pixel stamps centered at the detection position, observed with the Gravitational-wave Optical Transient Observer (GOTO) prototype. The real-bogus classifier trained with this strategy can provide up to 95% prediction accuracy on the real detections at a false alarm rate of 1%., Comment: 9 pages, 8 figures

There is a well-known connection between hypergraphs and bipartite graphs, obtained by treating the incidence matrix of the hypergraph as the biadjacency matrix of a bipartite graph. We use this connection to describe and analyse a rejection sampling algorithm for sampling simple uniform hypergraphs with a given degree sequence. Our algorithm uses, as a black box, an algorithm $\mathcal{A}$ for sampling bipartite graphs with given degrees, uniformly or nearly uniformly, in (expected) polynomial time. The expected runtime of the hypergraph sampling algorithm depends on the (expected) runtime of the bipartite graph sampling algorithm $\mathcal{A}$, and the probability that a uniformly random bipartite graph with given degrees corresponds to a simple hypergraph. We give some conditions on the hypergraph degree sequence which guarantee that this probability is bounded below by a positive constant., Comment: 21 pages. This version addresses referees' comments

Ultracompact accreting binary systems each consist of a stellar remnant accreting helium-enriched material from a compact donor star. Such binaries include two related sub-classes, AM CVn-type binaries and helium cataclysmic variables, in both of which the central star is a white dwarf. We present a spectroscopic and photometric study of six accreting binaries with orbital periods in the range of 40--70 min, including phase-resolved VLT spectroscopy and high-speed ULTRACAM photometry. Four of these are AM CVn systems and two are helium cataclysmic variables. For four of these binaries we are able to identify orbital periods (of which three are spectroscopic). SDSS J1505+0659 has an orbital period of 67.8 min, significantly longer than previously believed, and longer than any other known AM CVn binary. We identify a WISE infrared excess in SDSS J1505+0659 that we believe to be the first direct detection of an AM CVn donor star in a non-direct impacting binary. The mass ratio of SDSS J1505+0659 is consistent with a white dwarf donor. CRTS J1028-0819 has an orbital period of 52.1 min, the shortest period of any helium cataclysmic variable. MOA 2010-BLG-087 is co-aligned with a K-class star that dominates its spectrum. ASASSN-14ei and ASASSN-14mv both show a remarkable number of echo outbursts following superoutbursts (13 and 10 echo outbursts respectively). ASASSN-14ei shows an increased outburst rate over the years following its superoutburst, perhaps resulting from an increased accretion rate., Comment: 22 pages, 21 figures. Accepted for publication by MNRAS

We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the "winding" technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514-527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice., Comment: Minor revisions. The version is accepted for publication in Combinatorics, Probability and Computing

White dwarfs are the burnt out cores of Sun-like stars and are the final fate of 97% of all stars in our Galaxy. The internal structure and composition of white dwarfs are hidden by their high gravities, which causes all elements, apart from the lightest ones, to settle out of their atmospheres. The most direct method to probe the inner structure of stars and white dwarfs in detail is via asteroseismology. Here we present the first known pulsating white dwarf in an eclipsing binary system, enabling us to place extremely precise constraints on the mass and radius of the white dwarf from the light curve, independent of the pulsations. This 0.325M$_\odot$ white dwarf --- one member of SDSS J115219.99+024814.4 --- will serve as a powerful benchmark to constrain empirically the core composition of low-mass stellar remnants and investigate the effects of close binary evolution on the internal structure of white dwarfs., Comment: Accepted for publication in Nature Astronomy

The detection of the first electromagnetic counterpart to a gravitational-wave signal in August 2017 marked the start of a new era of multi-messenger astrophysics. An unprecedented number of telescopes around the world were involved in hunting for the source of the signal, and although more gravitational-wave signals have been since detected, no further electromagnetic counterparts have been found. In this thesis, I present my work to help build a telescope dedicated to the hunt for these elusive sources: the Gravitational-wave Optical Transient Observer (GOTO). I detail the creation of the GOTO Telescope Control System, G-TeCS, which includes the software required to control multiple wide-field telescopes on a single robotic mount. G-TeCS also includes software that enables the telescope to complete a sky survey and transient alert follow-up observations completely autonomously, whilst monitoring the weather conditions and automatically fixing any hardware issues that arise. I go on to describe the routines used to determine target priorities, as well as how the all-sky survey grid is defined, how gravitational-wave and other transient alerts are received and processed, and how the optimum follow-up strategies for these events were determined. The GOTO prototype, situated on La Palma, saw first light in June 2017. I detail the work I carried out on the site to help commission the prototype, and how the control software was developed during the commissioning phase. I also analyse the GOTO CCD cameras and optics, building a complete theoretical model of the system to confirm the performance of the prototype. Finally, I describe the results of simulations I carried out predicting the future of the GOTO project, with multiple robotic telescopes on La Palma and in Australia, and how G-TeCS might be modified to operate these telescopes as a single, global observatory., Comment: 344 pages, PhD Thesis (submitted 26 September 2019, awarded 10 January 2020), abstract and some images compressed for space (see https://etheses.whiterose.ac.uk/25648/ for original)

We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix $A$. Each symmetric matrix $A$ defines a graph homomorphism function $Z_A(\cdot)$, also known as the partition function. Dyer and Greenhill [10] established a complexity dichotomy of $Z_A(\cdot)$ for symmetric $\{0, 1\}$-matrices $A$, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [4] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices $A$. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric $A$, either $Z_A(G)$ is in polynomial time for all graphs $G$, or it is #P-hard for bounded degree (and simple) graphs $G$. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [12] for $Z_A(\cdot)$ also holds for simple graphs, where $A$ is any real symmetric matrix.

Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs, and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvatal and Sbihi (1988), Maffray and Reed (1999) and Lozin and Milanic (2008)., Comment: 25 pages, 11 figures

An edge switch is an operation which makes a local change in a graph while maintaining the degree of every vertex. We introduce a switch move, called a triangle switch, which creates or deletes at least one triangle. Specifically, a make move is a triangle switch which chooses a path $zwvxy$ of length 4 and replaces it by a triangle $vxwv$ and an edge $yz$, while a break move performs the reverse operation. We consider various Markov chains which perform random triangle switches, and assume that every possible make or break move has positive probability of being performed. Our first result is that any such Markov chain is irreducible on the set of all 3-regular graphs with vertex set $\{1,2,\ldots, n\}$. For a particular, natural Markov chain of this type, we obtain a non-trivial linear upper and lower bounds on the number of triangles in the long run. These bounds are almost surely obtained in linear time, irrespective of the starting graph.

We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The class is determined by boundedness of a new graph parameter called bipartite pathwidth. This result, which we prove for the more general hardcore distribution with fugacity $\lambda$, can be viewed as a strong generalisation of Jerrum and Sinclair's work on approximately counting matchings, that is, independent sets in line graphs. The class of graphs with bounded bipartite pathwidth includes claw-free graphs, which generalise line graphs. We consider two further generalisations of claw-free graphs and prove that these classes have bounded bipartite pathwidth. We also show how to extend all our results to polynomially-bounded vertex weights., Comment: 39 pages, 7 figures

We show that the number of independent sets in cocomparability graphs can be counted in linear time, as can counting cliques in comparability graphs. By contrast, counting cliques in cocomparabilty graphs and counting independent sets in comparability graphs are #P-complete. We extend these results to counting maximal cliques and independent sets. We also consider the fixed-parameter versions of counting cliques and independent sets of given size $k$. Finally, we combine the results to show that both counting cliques and independent sets in permutation graphs are in linear time., Comment: 9 pages

The Gravitational-wave Optical Transient Observer (GOTO) is a wide-field telescope project aimed at detecting optical counterparts to gravitational wave sources. The prototype instrument was inaugurated in July 2017 on La Palma in the Canary Islands. We describe the GOTO Telescope Control System (G-TeCS), a custom robotic control system written in Python which autonomously manages the telescope hardware and nightly operations. The system comprises of multiple independent control daemons, which are supervised by a master control program known as the "pilot". Observations are decided by a "just-in-time" scheduler, which instructs the pilot what to observe in real time and provides quick follow-up of transient events., Comment: 14 pages, 6 figures, 1 table, SPIE Astronomical Telescopes + Instrumentation, Austin, Texas, 10-15 June 2018

For any class $\mathcal{C}$ of bipartite graphs, we define quasi-$\cal C$ to be the class of all graphs $G$ such that every bipartition of $G$ belongs to $\cal C$. This definition is motivated by a generalisation of the switch Markov chain on perfect matchings from bipartite graphs to nonbipartite graphs. The monotone graphs, also known as bipartite permutation graphs and proper interval bigraphs, are such a class of bipartite graphs. We investigate the structure of quasi-monotone graphs and hence construct a polynomial time recognition algorithm for graphs in this class., Comment: 37 pages, 56 figures

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices $\{u,v\}$ with distance $d>1$ is added as a "long-range" edge with probability proportional to $d^{-r}$, where $r\geq 0$ is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is $O((\log n)^2)$ when $r=2$ and $n^{\Omega(1)}$ when $r\neq 2$. Here, we prove that the random walk also undergoes a phase transition at $r=2$, but in this case the phase transition is of a different form. We establish that the mixing time is $\Theta(\log n)$ for $r<2$, $O((\log n)^4)$ for $r=2$ and $n^{\Omega(1)}$ for $r>2$., Comment: To appear in Transactions of Algorithms (TALG)

We present a new, but simple, randomised order-preserving encryption (OPE) scheme based on the general approximate common divisor problem (GACDP). This appears to be the first OPE scheme to be based on a computational hardness primitive, rather than a security game. This scheme requires only $O(1)$ arithmetic operations for encryption and decryption. We show that the scheme has optimal information leakage under the assumption of uniformly distributed plaintexts, and we indicate that this property extends to some non-uniform distributions. We report on an extensive evaluation of our algorithms. The results clearly demonstrate highly favourable execution times in comparison with existing OPE schemes.

We examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of nonbipartite graphs. In particular, we consider the switch Markov chain of Diaconis, Graham and Holmes. We determine the largest hereditary class for which the chain is ergodic, and define a large new hereditary class of graphs for which it is rapidly mixing. We go on to show that the chain has exponential mixing time for a slightly larger class. We also examine the question of ergodicity of the switch chain in a arbitrary graph. Finally, we give exact counting algorithms for three classes., Comment: 34 pages, 26 figures

We present novel homomorphic encryption schemes for integer arithmetic, intended for use in secure single-party computation in the cloud. These schemes are capable of securely computing only low degree polynomials homomorphically, but this appears sufficient for most practical applications. In this setting, our schemes lead to practical key and ciphertext sizes. We present a sequence of generalisations of our basic schemes, with increasing levels of security, but decreasing practicality. We have evaluated the first four of these algorithms by computing a low-degree inner product. The timings of these computations are extremely favourable. Finally, we use our ideas to derive a fully homomorphic system, which appears impractical, but can homomorphically evaluate arbitrary Boolean circuits.

Mahlmann and Schindelhauer (2005) defined a Markov chain which they called $k$-Flipper, and showed that it is irreducible on the set of all connected regular graphs of a given degree (at least 3). We study the 1-Flipper chain, which we call the flip chain, and prove that the flip chain converges rapidly to the uniform distribution over connected $2r$-regular graphs with $n$ vertices, where $n\geq 8$ and $r = r(n)\geq 2$. Formally, we prove that the distribution of the flip chain will be within $\varepsilon$ of uniform in total variation distance after $\text{poly}(n,r,\log(\varepsilon^{-1}))$ steps. This polynomial upper bound on the mixing time is given explicitly, and improves markedly on a previous bound given by Feder et al.(2006). We achieve this improvement by using a direct two-stage canonical path construction, which we define in a general setting. This work has applications to decentralised networks based on random regular connected graphs of even degree, as a self-stabilising protocol in which nodes spontaneously perform random flips in order to repair the network., Comment: 40 pages, addresses referee comments. An earlier version of this paper appeared as an extended abstract in PODC 2009

We present the discovery of the hot subdwarf B star (sdB) binary PTF1 J082340.04+081936.5. The system has an orbital period P$_{\rm orb}=87.49668(1)$ min (0.060761584(10) days), making it the second-most compact sdB binary known. The lightcurve shows ellipsoidal variations. Under the assumption that the sdB primary is synchronized with the orbit, we find a mass $M_{\rm sdB}=0.45^{+0.09}_{-0.07}$ M$_\odot$, a companion white dwarf mass $M_{\rm WD}=0.46^{+0.12}_{-0.09}$ M$_\odot$ and a mass ratio $q = \frac{M_{\rm WD}}{M_{\rm sdB}}=1.03^{+0.10}_{-0.08}$. The future evolution was calculated using the MESA stellar evolution code. Adopting a canonical sdB mass of $M_{\rm sdB}=0.47$ M$_\odot$, we find that the sdB still burns helium at the time it will fill its Roche lobe if the orbital period was less than 106 min at the exit from the last common envelope phase. For longer common envelope exit periods the sdB will have stopped burning helium and turned into a C/O white dwarf at the time of contact. Comparing the spectroscopically derived log(g) and $T_{\rm eff}$ with our MESA models, we find that an sdB model with a hydrogen envelope mass of $5\times10^{-4} M_\odot$ matches the measurements at a post-common envelope age of 94 Myr, corresponding to a post-common envelope orbital period of 109 min which is close to the limit to start accretion while the sdB is still burning helium., Comment: Accepted for publication in ApJ, 9 pages, 8 figures

We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus , i.e. the number of interactions needed for all vertices have the same colour. An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point. We show that E(T), the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, E(T) =n^2/4 independent of the underlying graph. For the complete graph K_n, the push protocol has E(T)= Theta(n log(n)), whereas the pull protocol has E(T)= Theta(2^n). For the cycle C_n all three protocols have E(T) = Theta(n^2). For the star graph however, the pull protocol has E(T)=O(n^2), whereas the push protocol is slower with E(T) = Theta(n^2 log(n)). The wide variation in E(T) for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which E(T) = O(n) on many classes of expanders.

We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possible approach to a sampling problem arising in Statistics. We ask: for which classes of graphs is the Markov chain ergodic and for which is it rapidly mixing? We provide a precise answer to the ergodicity question and close bounds on the mixing question. We show for the first time that the mixing time of the switch chain is polynomial in the case of monotone graphs, a class that includes examples of interest in the statistical setting., Comment: 31 pages

Given a symmetric matrix $M\in \{0,1,*\}^{D\times D}$, an $M$-partition of a graph $G$ is a function from $V(G)$ to $D$ such that no edge of $G$ is mapped to a $0$ of $M$ and no non-edge to a $1$. We give a computer-assisted proof that, when $|D|=4$, the problem of counting the $M$-partitions of an input graph is either in FP or is #P-complete. Tractability is proved by reduction to the related problem of counting list $M$-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for $|D|>4$. More specifically, we conjecture that, for any symmetric matrix $M\in\{0,1,*\}^{D\times D}$, the complexity of counting $M$-partitions is the same as the related problem of counting list $M$-partitions.