BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Joanna A. Ellis-Monaghan

Joanna A. Ellis-Monaghan contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COcond-mat.stat-mechBiomoleculesComputational Engineering, Finance, and ScienceData Structures and Algorithms

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

A Catalog of Enumeration Formulas for Bouquet and Dipole Embeddings Under Symmetries

Motivated by a problem arising out of DNA origami, we give a general counting framework and enumeration formulas for various cellular embeddings of bouquets and dipoles under different kinds of symmetries. Our algebraic framework can be used constructively to generate desired symmetry classes, and we use Burnside's Lemma with various symmetry groups to derive the enumeration formulas. Our results assimilate several existing formulas into this unified framework. Furthermore, we provide new formulas for bouquets with colored edges (and thus for bouquets in nonorientable surfaces) as well as for directed embeddings of directed bouquets. We also enumerate vertex-labeled dipole embeddings. Since dipole embeddings may be represented by permutations, the formulas also apply to certain equivalence classes of permutations and permutation matrices. The resulting bouquet and dipole symmetry formulas enumerate structures relevant to a wide variety of areas in addition to DNA origami, including RNA secondary structures, Feynman diagrams, and topological graph theory. For uncolored objects we catalog 58 distinct sequences, of which 43 have not, as far as we know, been described previously.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model

Here we observe that list coloring in graph theory coincides with the zero-temperature antiferromagnetic Potts model with an external field. We give a list coloring polynomial that equals the partition function in this case. This is analogous to the well-known connection between the chromatic polynomial and the zero-temperature, zero-field, antiferromagnetic Potts model. The subsequent cross fertilization yields immediate results for the Potts model and suggests new research directions in list coloring.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

DNA origami and the complexity of Eulerian circuits with turning costs

Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard. We then show that the problem may readily be transformed into a Traveling Salesman Problem (TSP), so that machinery that has been developed for the TSP may be applied to find optimal routes for the scaffolding strand in a DNA origami self-assembly process. We give results for a few special cases, showing for example that the problem remains intractable for graphs with maximum degree 8, but is polynomial time for 4-regular plane graphs if the circuit is restricted to following faces. We conclude with some implications of these results for related problems, such as biomolecular computing and mill routing problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Evaluations of topological Tutte polynomials

We find new properties of the topological transition polynomial of embedded graphs, $Q(G)$. We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, $R(G)$, and the topological Penrose polynomial, $P(G)$. The general framework provided by $Q(G)$ also leads to several other combinatorial interpretations these polynomials. In particular, we express $P(G)$, $R(G)$, and the Tutte polynomial, $T(G)$, as sums of chromatic polynomials of graphs derived from $G$; show that these polynomials count $k$-valuations of medial graphs; show that $R(G)$ counts edge 3-colourings; and reformulate the Four Colour Theorem in terms of $R(G)$. We conclude with a reduction formula for the transition polynomial of the tensor product of two embedded graphs, showing that it leads to additional relations among these polynomials and to further combinatorial interpretations of $P(G)$ and $R(G)$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Las Vergnas Polynomial for embedded graphs

The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion-contraction relations, its specialisation to cellularly embedded graphs does not. Here we extend the Las Vergnas polynomial to graphs in pseudo-surfaces. We show that in this setting we can define deletion and contraction for embedded graphs consistently with the deletion and contraction of the underlying matroid perspective, thus yielding a version of the Las Vergnas polynomial with complete recursive definition. This also enables us to obtain a deeper understanding of the relationships among the Las Vergnas polynomial, the Bollobas-Riordan polynomial, and the Krushkal polynomial. We also take this opportunity to extend some of Las Vergnas' results on Eulerian circuits from graphs in surfaces of low genus to surfaces of arbitrary genus.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Penrose polynomial for embedded graphs

We extend the Penrose polynomial, originally defined only for plane graphs, to graphs embedded in arbitrary surfaces. Considering this Penrose polynomial of embedded graphs leads to new identities and relations for the Penrose polynomial which can not be realized within the class of plane graphs. In particular, by exploiting connections with the transition polynomial and the ribbon group action, we find a deletion-contraction-type relation for the Penrose polynomial. We relate the Penrose polynomial of an orientable checkerboard colourable graph to the circuit partition polynomial of its medial graph and use this to find new combinatorial interpretations of the Penrose polynomial. We also show that the Penrose polynomial of a plane graph G can be expressed as a sum of chromatic polynomials of twisted duals of G. This allows us to obtain a new reformulation of the Four Colour Theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Tutte-Potts connection in the presence of an external magnetic field

The classical relationship between the Tutte polynomial of graph theory and the Potts model of statistical mechanics has resulted in valuable interactions between the disciplines. Unfortunately, it does not include the external magnetic fields that appear in most Potts model applications. Here we define the V-polynomial, which lifts the classical relationship between the Tutte polynomial and the zero field Potts model to encompass external magnetic fields. The V-polynomial generalizes Nobel and Welsh's W-polynomial, which extends the Tutte polynomial by incorporating vertex weights and adapting contraction to accommodate them. We prove that the variable field Potts model partition function (with its many specializations) is an evaluation of the V-polynomial, and hence a polynomial with deletion-contraction reduction and Fortuin-Kasteleyn type representation. This unifies an important segment of Potts model theory and brings previously successful combinatorial machinery, including complexity results, to bear on a wider range of statistical mechanics models.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Twisted duality for embedded graphs

We consider two operations on an edge of an embedded graph (or equivalently a ribbon graph): giving a half-twist to the edge and taking the partial dual with respect to the edge. These two operations give rise to an action of S_3^{|E(G)|}, the ribbon group, on G. The action of the ribbon group on embedded graphs extends the concepts of duality, partial duality and Petrie duality. We show that this ribbon group action gives a complete characterization of duality in that if G is any cellularly embedded graph with medial graph G_m, then the orbit of G under the group action is precisely the set of all graphs with medial graphs isomorphic (as abstract graphs) to G_m. We provide characterizations of special sets of twisted duals, such as the partial duals, of embedded graphs in terms of medial graphs and we show how different kinds of graph isomorphism give rise to these various notions of duality. The ribbon group action then leads to a deeper understanding of the properties of, and relationships among, various graph polynomials via the generalized transition polynomial which interacts naturally with the ribbon group action.

0 citations0 reviewsNo code linkedOpen access