Counting on Frameworks

Last updated

Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures is an undergraduate-level book on the mathematics of structural rigidity. It was written by Jack E. Graver and published in 2001 by the Mathematical Association of America as volume 25 of the Dolciani Mathematical Expositions book series. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion by undergraduate mathematics libraries. [1]

Contents

Topics

The problems considered by Counting on Frameworks primarily concern systems of rigid rods, connected to each other by flexible joints at their ends; the question is whether these connections fix such a framework into a single position, or whether it can flex continuously through multiple positions. Variations of this problem include the simplest way to add rods to a framework to make it rigid, or the resilience of a framework against the failure of one of its rods. [2]

To study this question, Graver has organized Counting on Frameworks into four chapters. The first chapter studies square grids and methods of cross bracing the grid to make it rigid, as a way of introducing the notion of the degrees of freedom of a mechanical system. [1] [3] [4] The second chapter provides an introduction to graph theory, the one-dimensional theory of rigidity through the analysis of the connected components of graphs, and a reformulation of the grid bracing problem in terms of connectivity of an associated bipartite graph. [1] [3] [4] [5] Chapter three concerns two-dimensional rigidity, the concepts of infinitesimal and generic rigidity, the combinatorial and algorithmic aspects of the subject, and the obstacles to extending this theory to three dimensions. A final chapter describes the history of rigidity theory, applications including mechanical linkages, geodesic domes, tensegrity, the rigidity of molecules in chemistry, and even art. It also discusses open problems for research in this area. [1] [3] [4]

Audience and reception

Counting on Frameworks expects its readers to be familiar with multivariable calculus, but beyond that level of background material it does not demand much mathematical sophistication. [5] More generally, the editors of Mathematika recommend it to "Any reader with at least a slight mathematical background". [6] To avoid demanding too much background of its readers, it is unable to present full proofs of some of its results, instead presenting them as intuitive proof sketches. A more advanced and rigorous treatment of the same material can be found in Combinatorial Rigidity (1993), a graduate textbook co-authored by Graver. [1]

It includes exercises for students, [1] [4] making it suitable as an undergraduate textbook. [5] Reviewer Tiong Seng Tay describes it as "an excellent expository book". [3]

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

<span class="mw-page-title-main">Three utilities problem</span> Mathematical puzzle of avoiding crossings

The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Václav Chvátal</span> Czech-Canadian mathematician

Václav (Vašek) Chvátal is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

<span class="mw-page-title-main">Structural rigidity</span> Combinatorial theory of mechanics and discrete geometry

In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.

Norman Linstead Biggs is a leading British mathematician focusing on discrete mathematics and in particular algebraic combinatorics.

<span class="mw-page-title-main">Ileana Streinu</span> Romanian-American computer scientist and mathematician

Ileana Streinu is a Romanian-American computer scientist and mathematician, the Charles N. Clark Professor of Computer Science and Mathematics at Smith College in Massachusetts. She is known for her research in computational geometry, and in particular for her work on kinematics and structural rigidity.

In graph theory, Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.

Brigitte Irma Servatius is a mathematician specializing in matroids and structural rigidity. She is a professor of mathematics at Worcester Polytechnic Institute, and has been the editor-in-chief of the Pi Mu Epsilon Journal since 1999.

Combinatorial Games: Tic-Tac-Toe Theory is a monograph on the mathematics of tic-tac-toe and other positional games, written by József Beck. It was published in 2008 by the Cambridge University Press as volume 114 of their Encyclopedia of Mathematics and its Applications book series (ISBN 978-0-521-46100-9).

<i>In Pursuit of the Traveling Salesman</i>

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation is a book on the travelling salesman problem, by William J. Cook, published in 2011 by the Princeton University Press, with a paperback reprint in 2014. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

Pearls in Graph Theory: A Comprehensive Introduction is an undergraduate-level textbook on graph theory by Nora Hartsfield and Gerhard Ringel. It was published in 1990 by Academic Press with a revised edition in 1994 and a paperback reprint of the revised edition by Dover Books in 2003. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

<i>Taking Sudoku Seriously</i> 2011 book about sudoku

Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle is a book on the mathematics of Sudoku. It was written by Jason Rosenhouse and Laura Taalman, and published in 2011 by the Oxford University Press. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries. It was the 2012 winner of the PROSE Awards in the popular science and popular mathematics category.

Introduction to Circle Packing: The Theory of Discrete Analytic Functions is a mathematical monograph concerning systems of tangent circles and the circle packing theorem. It was written by Kenneth Stephenson and published in 2005 by the Cambridge University Press.

Convex Polytopes is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics.

In the mathematics of structural rigidity, grid bracing is a problem of adding cross bracing to a square grid to make it into a rigid structure. It can be solved optimally by translating it into a problem in graph theory on the connectivity of bipartite graphs.

<i>Incidence and Symmetry in Design and Architecture</i>

Incidence and Symmetry in Design and Architecture is a book on symmetry, graph theory, and their applications in architecture, aimed at architecture students. It was written by Jenny Baglivo and Jack E. Graver and published in 1983 by Cambridge University Press in their Cambridge Urban and Architectural Studies book series. It won an Alpha Sigma Nu Book Award in 1983, and has been recommended for undergraduate mathematics libraries by the Basic Library List Committee of the Mathematical Association of America.

Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a directed graph and the goal of the problem is to add a small number of edges, or a set of edges with small total weight, so that the added edges make the graph into a strongly connected graph.

A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.

References

  1. 1 2 3 4 5 6 Langton, Stacy G. (May 2002), "Review of Counting on Frameworks", MAA Reviews, Mathematical Association of America
  2. ↑ Lloyd, E. Keith (April 2002), "Review of Counting on Frameworks" (PDF), The London Mathematical Society Newsletter (303): 9–10
  3. 1 2 3 4 Tay, Tiong Seng (2002), "Review of Counting on Frameworks", MathSciNet , MR   1843781
  4. 1 2 3 4 Servatius, Brigitte, "Review of Counting on Frameworks", zbMATH , Zbl   0982.52019
  5. 1 2 3 Schneider, Leo (May 2002), "Review of Counting on Frameworks", The Mathematics Teacher , 95 (5): 392, JSTOR   20871062
  6. ↑ "Book Reviews", Mathematika , 49 (1–2): 253–261, June 2002, doi:10.1112/s0025579300016223
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.