Richard Anstee

A framework in Euclidean space consists of a set of points calledjoints, and line segments connecting pairs of joints called bars. Aframework is flexible if there exists a continuous motion of its jointssuch that all pairs of joints with a bar remain at a constant distance, but between at least one pair of joints not joined by a bar, the distance changes. Forexample, a square in the plane is not rigid since it can be deformedinto a family of rhombi. This thesis is mainly concerned with infinitesimal motions. Loosely speaking, a framework is infinitesimally rigid if it does not wobble. One example is a motion of a single joint, where all other joints are unmoving, such that the movement of the one joint is perpendicular to all bars attached to it. The distances in an infinitesimal motion are preserved in the initial instant of motion. Infinitesimally rigidframeworks are rigid, and is an easier quality to verify, thereby making it a popular notion of rigidity to study among engineerings, architects, and mathematicians. We present infinitesimally rigid bipartiteunit-bar frameworks in ℝ^n, and infinitesimally rigidbipartite frameworks in the plane with girth up to 12. Our constructions make use of the knight's graph; a graph such that vertices (joints) are squares of a chessboard and edges (bars) represent legal moves of the knight. We show that copies of the knight's graph can be assembled to create infinitesimally rigid frameworks in any dimension. Our constructions answer questions of Hiroshi Maehara.

View record

The forbidden configuration problem arises from a question in extremal set theory. The question seeks a bound on the maximum number of subsets of an m-set given that some trace is forbidden. In terms of hypergraphs, we seek the maximum number of edges on a simple hypergraph of m vertices such that this hypergraph does not contain a forbidden sub-hypergraph. We will use the notation of matrices to describe the problem as follows. We call a (0,1)-matrix simple if it has no repeated columns; this will be the analogue of a simple hypergraph. Let F be a given matrix. We say that a (0,1)-matrix A contains F as a configuration if there is some submatrix of A that is a row and column permutation of F. This is equivalent to a hypergraph containing some sub-hypergraph. F need not be simple. We define forb(m, F ) as the maximum number of columns possible for a simple, m-rowed, (0,1)-matrix that does not contain F as a configuration. A variation of the forbidden configuration problem forbids a family of configurations F = {F₁, F₂, ... Fn} instead of a single configuration F. Thus, forb(m, F) becomes the maximum number of columns possible for a simple, m-rowed, (0,1)-matrix that does not contain any one of the matrices in the family as a configuration. We will present a series of results organized by the character of forb(m, F). These include a classification of families such that forb(m, F) is a constant and the unexpected result that for a certain family, forb(m, F) is on the order of m³/², where previous results typically had forb(m, F) on the order of integer powers of m. We will conclude with a case study of families of forbidden configurations and suggestions for future work.

View record