BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Bill Jackson

Bill Jackson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.MGmath-phmath.MP

Catalog footprint

What is connected

14works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

14 published item(s)

preprint2022arXiv

Abstract 3-Rigidity and Bivariate $C_2^1$-Splines I: Whiteley's Maximality Conjecture

A conjecture of Graver from 1991 states that the generic $3$-dimensional rigidity matroid is the unique maximal abstract $3$-rigidity matroid with respect to the weak order on matroids. Based on a close similarity between the generic $d$-dimensional rigidity matroid and the generic $C_{d-2}^{d-1}$-cofactor matroid from approximation theory, Whiteley made an analogous conjecture in 1996 that the generic $C_{d-2}^{d-1}$-cofactor matroid is the unique maximal abstract $d$-rigidity matroid for all $d\geq 2$. We verify the case $d=3$ of Whiteley's conjecture in this paper. A key step in our proof is to verify a second conjecture of Whiteley that the `double V-replacement operation' preserves independence in the generic $C_2^1$-cofactor matroid.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Abstract 3-Rigidity and Bivariate $C_2^1$-Splines II: Combinatorial Characterization

We showed in the first paper of this series that the generic $C_2^1$-cofactor matroid is the unique maximal abstract $3$-rigidity matroid. In this paper we obtain a combinatorial characterization of independence in this matroid. This solves the cofactor counterpart of the combinatorial characterization problem for the rigidity of generic 3-dimensional bar-joint frameworks. We use our characterization to verify that the counterparts of conjectures of Dress (on the rank function) and Lovász and Yemini (which suggested a sufficient connectivity condition for rigidity) hold for this matroid.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An improved bound for the rigidity of linearly constrained frameworks

We consider the problem of characterising the generic rigidity of bar-joint frameworks in $\mathbb{R}^d$ in which each vertex is constrained to lie in a given affine subspace. The special case when $d=2$ was previously solved by I. Streinu and L. Theran in 2010 and the case when each vertex is constrained to lie in an affine subspace of dimension $t$, and $d\geq t(t-1)$ was solved by Cruickshank, Guler and the first two authors in 2019. We extend the latter result by showing that the given characterisation holds whenever $d\geq 2t$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A characterisation of the generic rigidity of 2-dimensional point-line frameworks

A 2-dimensional point-line framework is a collection of points and lines in the plane which are linked by pairwise constraints that fix some angles between pairs of lines and also some point-line and point-point distances. It is rigid if every continuous motion of the points and lines which preserves the constraints results in a point-line framework which can be obtained from the initial framework by a translation or a rotation. We characterise when a generic point-line framework is rigid. Our characterisation gives rise to a polynomial algorithm for solving this decision problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Antistrong digraphs

An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NP-complete to decide whether two vertices $x,y$ in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. A digraph $D$ is antistrong if it contains an antidirected $(x,y)$-trail starting and ending with a forward arc for every choice of $x,y\in V(D)$. We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to $D$ makes the resulting digraph the arc-disjoint union of $k$ antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2-detachment. Finally, we study arc-decompositions of antistrong digraphs and pose several problems and conjectures.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Global rigidity of 2-dimensional direction-length frameworks

A 2-dimensional direction-length framework is a collection of points in the plane which are linked by pairwise constraints that fix the direction or length of the line segments joining certain pairs of points. We represent it as a pair $(G,p)$, where $G=(V;D,L)$ is a `mixed' graph and $p:V\to{\mathbb R}^2$ is a point configuration for $V$. It is globally rigid if every direction-length framework $(G,q)$ which satisfies the same constraints can be obtained from $(G,p)$ by a translation or a rotation by $180^\circ$. We show that the problem of characterising when a generic framework $(G,p)$ is globally rigid can be reduced to the case when $G$ belongs to a special family of `direction irreducible' mixed graphs, and prove that {every} generic realisation of a direction irreducible mixed graph $G$ is globally rigid if and only if $G$ is 2-connected, direction-balanced and redundantly rigid.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Rigid cylindrical frameworks with two coincident points

We develop a rigidity theory for frameworks in $\mathbb{R}^3$ which have two coincident points but are otherwise generic and only infinitesimal motions which are tangential to a family of cylinders induced by the realisation are considered. We then apply our results to show that vertex splitting, under the additional assumption that the new edge is redundant, preserves the property of being generically globally rigid on families of concentric cylinders.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The number of equivalent realisations of a rigid graph

Given a rigid realisation of a graph $G$ in ${\mathbb R}^2$, it is an open problem to determine the maximum number of pairwise non-congruent realisations which have the same edge lengths as the given realisation. This problem can be restated as finding the number of solutions of a related system of quadratic equations and in this context it is natural to consider the number of solutions in ${\mathbb C}^2$ rather that ${\mathbb R}^2$. We show that the number of complex solutions, $c(G)$, is the same for all generic realisations of a rigid graph $G$, characterise the graphs $G$ for which $c(G)=1$, and show that the problem of determining $c(G)$ can be reduced to the case when $G$ is $3$-connected and has no non-trivial $3$-edge-cuts. We consider the effect of the Henneberg moves and the vertex-splitting operation on $c(G)$. We use our results to determine $c(G)$ exactly for two important families of graphs, and show that the graphs in both families have $c(G)$ pairwise equivalent generic real realisations. We also show that every planar isostatic graph on $n$ vertices has at least $2^{n-3}$ pairwise equivalent real realisations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stress matrices and global rigidity of frameworks on surfaces

In 2005, Bob Connelly showed that a generic framework in $\bR^d$ is globally rigid if it has a stress matrix of maximum possible rank, and that this sufficient condition for generic global rigidity is preserved by the 1-extension operation. His results gave a key step in the characterisation of generic global rigidity in the plane. We extend these results to frameworks on surfaces in $\bR^3$. For a framework on a family of concentric cylinders, cones or ellipsoids, we show that there is a natural surface stress matrix arising from assigning edge and vertex weights to the framework, in equilibrium at each vertex. In the case of cylinders and ellipsoids, we show that having a maximum rank stress matrix is sufficient to guarantee generic global rigidity on the surface. We then show that this sufficient condition for generic global rigidity is preserved under 1-extension and use this to make progress on the problem of characterising generic global rigidity on the cylinder.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights

We find zero-free regions in the complex plane at large |q| for the multivariate Tutte polynomial (also known in statistical mechanics as the Potts-model partition function) Z_G(q,w) of a graph G with general complex edge weights w = {w_e}. This generalizes a result of Sokal (cond-mat/9904146) that applies only within the complex antiferromagnetic regime |1+w_e| \le 1. Our proof uses the polymer-gas representation of the multivariate Tutte polynomial together with the Penrose identity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Maxmaxflow and counting subgraphs

We introduce a new graph invariant Λ(G) that we call maxmaxflow, and put it in the context of some other well-known graph invariants, notably maximum degree and its relatives. We prove the equivalence of two "dual" definitions of maxmaxflow: one in terms of flows, the other in terms of cocycle bases. We then show how to bound the total number (or more generally, total weight) of various classes of subgraphs of G in terms of either maximum degree or maxmaxflow. Our results are motivated by a conjecture that the modulus of the roots of the chromatic polynomial of G can be bounded above by a function of Λ(G).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Necessary Conditions for the Generic Global Rigidity of Frameworks on Surfaces

A result due in its various parts to Hendrickson, Connelly, and Jackson and Jordán, provides a purely combinatorial characterisation of global rigidity for generic bar-joint frameworks in $\mathbb{R}^2$. The analogous conditions are known to be insufficient to characterise generic global rigidity in higher dimensions. Recently Laman-type characterisations of rigidity have been obtained for generic frameworks in $\mathbb{R}^3$ when the vertices are constrained to lie on various surfaces, such as the cylinder and the cone. In this paper we obtain analogues of Hendrickson's necessary conditions for the global rigidity of generic frameworks on the cylinder, cone and ellipsoid.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Radically solvable graphs

A 2-dimensional framework is a straight line realisation of a graph in the Euclidean plane. It is radically solvable if the set of vertex coordinates is contained in a radical extension of the field of rationals extended by the squared edge lengths. We show that the radical solvability of a generic framework depends only on its underlying graph and characterise which planar graphs give rise to radically solvable generic frameworks. We conjecture that our characterisation extends to all graphs.

0 citations0 reviewsNo code linkedOpen access