Category Archives: Mathematics

Mathematics, Music

A Mathematical Introduction to Melody

Algebraic music theory rests on the observations that the set I of intervals forms a Z-module (or free abelian group) under concatenation and that the set of pitches forms an affine space (or torsor) over this module. A change of key is simply a shift of origin.


Within this framework a melody is a walk in the affine space subject to welldefined local constraints (conjunct motion, leap compensation, tendency-tone resolution, diatonic membership, contour, range, etc.). A chord is expressed, via Chasles’ identity, as a vector sum of intervals; the same language yields a clean description of closed and open voicings, pitch-equivalent fingerings, and the affine subspaces that correspond to whole-tone scales, augmented triads, diminished-seventh chords and tritones.

The paper develop these ideas in elementary terms, supply the necessary multiplication and inversion tables, give explicit fretboard realisations of the principal intervals and dyads, and illustrate the theory with a detailed analysis of the traditional melody and harmony of Greensleeves. An appendix collects interval-stack constructions for the most common triads, seventh chords and ninth chords.

Download paper

Climate, Mathematics

Concerning the Measurement of Global Mean Surface Temperature

Agreement concerning basic definitions, models, and measurement procedures is an objective of good science. Below a brief paper concerning GMST and some questions for Grok. It is left to the reader to ascertain if these answers by Grok are reasonable.

Download pdf:

Question 1.

Consider, for example, the concept of length in a Galilean spacetime. If a sequence of independent, identically distributed measurements X_1, X_2, \ldots ,X_n is made of the length μ of a rigid rod, then, by the central limit theorem, the sampling distribution of the mean \bar{X} of the sequence converges to a normal distribution with mean equal to the mean of the sample distributions. In the absence of bias, the mean of the sample distribution will be the exact length μ. Moreover, the variance of the data can be compared to that expected from knowledge of experimental errors inherent in the details of the measurement process. Unexpected discrepancies can then be evaluated and possible model weaknesses analyzed or unexpected sources of error sought.

Application of this measurement procedure to, for example, the temperature measurement of a homogeneous fluid body in a constant state would quite likely raise few concerns. On the other hand, the surface of the earth is not a homogeneous fluid body in a constant state. If a number of different observers each using different sets of surface points make estimates of the global mean surface temperature, then the sequence of values so obtained does not represent a list of independent, identically distributed random variables and the hypotheses of the central limit theorem do not hold. Rather, this situation is like unto a set of observers, ignorant of the precepts of special relativity, travelling at different, but high, velocities relative to each other, and attempting to ascribe a length to a rigid rod which does not lie in their respective rest frames. Since the model hypothesis of a Galilean spacetime is false, the very concept of length is physically meaningless and differences in length obtained by different observers cannot be attributed merely to technical difficulties connected with the measuring process but rather to the incorrect model assumption of a Galilean spacetime. Due to the relativity of simultaneity, different observers are, in reality, measuring the separations between different pairs of spacetime events. Discrepancies obtained by such observers cannot in this case be ascribed to experimental error which can in principle be overcome by sufficient ingenuity; rather, their explanation requires a fundamental change of philosophy and the recognition that each is measuring a different parameter. In this case, knowledge of the experimental errors involved and of the discrepancies between observers would hopefully lead to a change in the model hypothesis and the discovery of special relativity. This, in turn, would enable the observers to transform their measurements to the rest frame of the rod, thereby yielding consistent estimates of the true rest length.

Unfortunately, the measurement of global mean surface temperature turns out to be far more complex and discrepancies between different observers measuring different distributions cannot be so easily transformed away. Some authors, attribute statistical bias in global mean temperature estimates to an uneven distribution of weather stations. This attribution implicitly assumes that such errors are amenable to correction by more uniform sampling or, perhaps, by better statistical processing. Is there evidence to the earth’s continually temperature distribution does not posses similar mathematical pathology?

Question 2

Let us imagine once more that two observers, with distinct but very large relative velocity, make repeated measurements on the length of the same rigid rod so as to obtain confidence intervals. Assume also that both observers take the utmost possible care to avoid bias in their measurement techniques. After a certain number of measurements their respective confidence intervals for the length will inevitably be disjoint even though both have avoided any procedural bias. This is a simple consequence of the central limit theorem and the fact that, due to relativistic length dilation, the two observers are in effect sampling from distributions with distinct means. Suppose now that one of the observers attempts to reduce this discrepancy by taking additional measurements. No matter how careful he is, or how many measurements are made, the most that can be achieved, will be a reduction in the size of his confidence interval. The problem of disjoint intervals will not disappear. Compare this to a situation in which two climatologists independently measure the average temperature in some region, using different set of sample points, and find a similar unreconcilable discrepancy between their respective results. Since all climatologists are honest, both will dutifully increase the number of sample points in order to obtain, say, a more uniform or, perhaps, less biased sample. Notwithstanding their undoubted honesty, their best efforts and good intentions are doomed to failure. As in the relativistic situation, the distributions which each climatologist samples are distinct, and so the discrepancy cannot be so eliminated by further measurement. In reality, the temperature distribution over the surface of the earth, at any moment, is quite irregular and it seems improbable that two distinct sets of points on the surface taken at different times (or even at the same time) yield samples from the same temperature distribution. In our relativistic analogy, the discrepancy is easily corrected by a transformation to the rest frame of the rod. In the case of temperature, it would seem that one is compelled to make ad hoc assumptions concerning the regularity of the global temperature distribution. What assumptions concerning the regularity of the global temperature distribution have been made?

Question 3

To obtain a confidence interval for the (time) average temperature at a single point, assumptions have to be made concerning the temporal regularity of the temperature at the said point. In fact, the very existence an average temperature underlying the observed temporal fluctuations has to be assumed —after all, not every random variable has a mean. Thus, for the sake of simplicity, let us eliminate this difficulty from the discussion by considering the best possible scenario of a sphere whose surface temperature distribution does not change with time but is purely a function of position. Unfortunately, even in this case there exist temperature distributions which are intractable to any conceivable sampling procedure. Consider, for example, the case of a distribution which is equal to a constant c over the surface of a sphere except for a single point P at which the temperature is a delta function of weight normalized so that the average temperature over the sphere is exactly equal to \beta + c where β is non zero. Then any uniform random sample of points on the sphere would, with probability 1, fail to contain the point P and so yield a sample mean temperature equal to c. Thus, the sample mean would differ from the true mean by the “bias” β which could be any pre-prescribed large number. Infinitely many variants of this construction are possible. Moreover, weaker (physical) versions could be constructed without recourse to the theory of distributions. On the surface of the earth an infinity of sharp temperature jumps occur in such places as the boundaries of icebergs floating in warmer water, at shorelines which are ever shifting and changing and, indeed, at the border of every shadow. Moreover, when temperature is measured, there exists the eminently practical problem of deciding how much weight to allocate to sample points which might be so unlucky as to fall in such hostile and inconvenient places as on an iceberg in the middle of the ocean or at the center of a volcano. The human decisions necessary in such circumstances inevitably lead to a degree of arbitrariness which might well explain the “observed” 0.6 degrees Celsius per century (or whatever it is) temperature increase. Incidently, two icebergs of the same surface area may have considerably different volumes and, hence, correspondingly different thermodynamic contributions but that is another issue entirely.

In summary, there exists the possibility that discrepancies in the measurement of global mean surface temperature may be measure-theoretic in origin, and, therefore not amenable to correction by, say, increases in sample size and quality. Such bias is intrinsic to the situation and independent of the measurements of even the most conscientious climatologist. A finite sample of points cannot, reliably estimate a distribution of unknown form over a set of positive measure. Similarly, surface measurements cannot reliably estimate an unknown volume distribution. How do climatologists handle this problem without relying on an ad hoc model assumption?

© Philip Pennance
Climate, Mathematics

Physical Applications of the Stevens’ Classification

Restrictions on admissible changes of scale are often overlooked in science education. Ironically, this topic receives far more attention in philosophy, psychology, and sociology texts than in the natural sciences. In fact, it was the Harvard psychologist S.~S.~Stevens who introduced the now-classic taxonomy of measurement scales, classifying variables according to the transformations permitted under a change of scale. The paper below presents a brief summary of Stevens’ taxonomy and illustrates each category with examples drawn from physics. Download the PDF.

Mathematics, Music

Commutative Diagrams and the Construction of Musical Scales

This article is intended as a minimal introduction to some basic musical ideas which fall within the intersection of mathematics and music. We discuss the science underlying the construction of Pythagorean and other tunings, giving mathematically clear definitions of the necessary musical terms. Careful distinction is made between the frequential and perceptual measures of pitch. The admissible changes of scale for each of these measures are derived. It is shown that commutative diagrams can provide a useful tool for the construction and analysis of scales. All needed musical notions are explained.

Download PDF

Mathematics

Mathematics Courses

  1. Mathematics for Elementary Teachers
  2. Math3018(3171-72) Precalculus
  3. Math 3026 Statistics with Computers
  4. Math 3151 Calculus I
  5. Math 3152 Calculus II
  6. Math 3153 Calculus III
  7. Math 3325 Introduction to Discrete Mathematics
  8. Math 4009 Ordinary Differential Equations
  9. Math 4019 Metric Differential Geometry
  10. Math 4021 Mathematical Logic I
  11. Math 4031 Linear Algebra
  12. Math 4032 Abstract Algebra I
  13. Math 4033 Abstract Algebra II
  14. Math 4995 Graph Theory II
  15. Math 4995 Graph Theory I
  16. Math 5021 Advanced Calculus I
  17. Math 5037 Complex Analysis
  18. Math 5100 Applied Combinatorics
  19. Matroid Theory
  20. Ph.D Courses in Discrete Mathematics
  21. Mathematical Physics
Mathematics, Music

Guitar Chord Sequences Ordered by Pitch

Guitar Chord Sequences Ordered by Pitch

If one diatonic open/closed chord is known, anywhere on say, a guitar fretboard, then totally ordered sequences of ascending and descending voicings of the same parity can be calculated, iteratively, without reference to dictionaries of chord fingerings. As an application, tables of open and closed chords for various major scales over different regions of the guitar fret board are generated. The mathematics is contained in the paper below. Musicians can jump straight to the tables below. More tables are under construction.

Download paper.

Download PDF

Examples

  1. A Major Open Triads — Bass Note on String $6$ in Ascending Pitch Order
  2. C Major Open Triads on Frets 0 to 4 Ordered by Increasing Pitch
  3. C Major Open Triads on Frets 5 to 9 Ordered by Increasing Pitch
  4. C Major Open Triads on Frets 9 to 12 Ordered by Increasing Pitch
  5. C Major Closed Triads on Frets 0 to 5 Ordered by Increasing Pitch
  6. C-Major Harmonizations by Closed Triads

Se also Pitch Equivalent Fingerings of Specific Guitar Chords

Mathematics

Mathematical Physics

Physics Notes

  1. Concerning the Measurabilityof a Global Mean Surface Temperature
  2. Physical Applications of the Stevens’ Classification of Random Variables
  3. A Proof of the Quantum Mechanical Charge Density Formul
  4. Quantum Statistics – Algebraic and Combinatorial Aspects
  5. Isomers
  6. Special Relativity
  7. Hamilton’s Equations
  8. Physical Applications of Stokes’ Theorem
  9. Commutative Diagrams and the Construction of Musical Scales
  10. Scientific Units
  11. Waves – Terminology
  12. Table of Ph Values

Third Year Exams for the B.Sc in Physics – University of Hull, 1971

  1. Paper I
  2. Paper II
  3. Paper III
  4. Paper IV
  5. Paper V.
Mathematics

Graduate Courses in Discrete Mathematics

Some course descriptions by A. K. Kelmans, proposed for the Discrete Mathematics option of the PhD in Mathematics at the University of Puerto Rico, Río Piedras.

Graph Theory I | Discrete Algorithms | Computers and Intractability. Theory of NP-completeness. | Enumerative Combinatorics | Combinatorial Optimization | Matroid Theory I

MATH 8001 Graph Theory I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 5CCC (Graph Theory).

Review of elementary graph theory. Trees. Matrix-tree theorem. Enumerating spanning trees of a graph. Graph decompositions. Connectivity and k–connectivity of graphs. Disjoint paths and connectivity of graphs. Menger’s and Whitney’s theorems. Graph assembling and disassembling of 3–connected and quasi 4-connected graphs. Various Euler problems. Hamiltonian cycles. The k–closure of a graph. Bondy–Chvátal’s theorem. Long cycles in a graph. Dirac’s theorem. Factors. Maximum and perfect matchings. Tutte’s and Edmonds–Gallai’s theorems. Berge–Tutte duality theorem. Perfect graphs. Lovász’ theorem. Edge colorings. Vising’s theorem. Independent sets and cliques. Vertex colorings. Brook’s theorem. Embeddings of graphs in the plane. Kuratowski’s, Whitney’s, MacLane’s and Kelmans’ planarity criteria. Five-colour and four-colour theorems on planar graphs. On the hamiltonicity of planar graphs.

Justification

It is difficult to overestimate the importance of graph theory in contemporary mathematics and its applications. Deep and elegant in itself, graph theory contains many wonderful ideas and results. Methods and ideas of graph theory are widely used in many other areas of mathematics. Graph theory has a tremendous number of applications. It would not be an exaggeration to say that graph theory is one of the most applicable areas of mathematics. It serves as a theoretical basis for a great variety of applied areas such as computer science, operations research, management science, electrical and mechanical engineering, chemistry, biology, etc. This course will be useful to the students who are planning to pursue doctoral studies in mathematics and its applications.

Syllabus

  1. Historical remarks. Interrelations between graph theory and other areas of mathematics and some areas of science.
  2. The main concepts of graph theory (review).
  3. Trees. Spanning trees of a graph, and their algebraic and geometric interpretations.
  4. Enumerating spanning trees of a graph (Matrix–tree theorem. Coding of spanning trees of a graph. The number of spanning trees of decomposable graphs).
  5. Graph decompositions (Decomposition of graphs on components, edge blocks and vertex blocks (review). Decomposition of 2–connected graphs on 3–connected blocks).
  6. Graph assembling and disassembling (Ear–decompositions of 3–connected, cyclically 4–connected and quasi–4-connected graphs).
  7. Disjoint paths in a graph (Vertex and edge cuts, and connectivity of graphs. Menger’s and Whitney’s theorems. The Ford–Fulkerson theorem.).
  8. Euler problems (A criteria for a graph and digraph to have an Euler tour or Euler trail (review). Euler trail set with at most one odd trail. Arborescences and Euler tours in digraphs.).
  9. Hamiltonian problems (Hamiltonian cycles and paths. k–stable properties and k–closure of graphs. Bondy–Chvátal theorem. Sufficient conditions for graph hamiltonicity.).
  10. Long cycles in a graph. Dirac’s theorem. Cycles through a given subset of elements in a graph. Kelmans–Lomonosov’s theorems.
  11. Factors. Matchings and coverings in bipartite graphs (review). Stable marriage problem.
  12. Matchings in a graph (Maximum and perfect matchings. Tutte’s theorem. Berge–Tutte duality theorem. Edmonds–Gallai structure theorem.).
  13. Edge colorings. Vising’s theorem.
  14. Independent sets and cliques.
  15. Vertex colorings (2–coloring and odd cycles (review). Brook’s theorem (review). Coloring of special graphs. Perfect graphs. Lovász’ theorem. Strong perfect graph conjecture.).
  16. Cycle and cocycle spaces of a graph (Combinatorial duality of graphs. Whitney’s cycle isomorphism theorem and its strengthenings and generalizations. Kelmans’ cycle semi–isomorphism and semi–duality theorems.).
  17. Graph planarity (Various embeddings of a graph into a plane. Geometrical duality of graphs. Euler’s formula (review). Kuratowski’s, Whitney’s, MacLane’s and Kelmans’ planarity criteria.)
  18. Coloring of planar graphs (Five–colour and four-colour theorems on planar graphs and related topics).
  19. Hamiltonicity of planar graphs.

Text

  1. D.B. West, Introduction to Graph Theory, Prentice Hall, 1996.
  2. J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, North Holland, Amsterdam, 1976.

Bibliography

  1. B. Bollobás, Extremal Graph Theory, Academic Press, London, New York, San Francisko, 1978.
  2. M. Behzad, G. Chartrand, and L. Lesniak, Graphs and Digraphs, Wadsworth International Group, 1991.
  3. A.K. Kelmans, A New Planarity Criterion for 3-connected Graphs, J. Graph Theory, 5 (1981) 259–267.
Alexander Kelmans
San Juan 1995

MATH 8005. Discrete Algorithms.

Three credits. Three hours of lecture per week. Prerequisites: MATH 5CCC (Graph Theory).

Branch and bound strategy. Dynamic programming principle. Optimal paths in graphs. Optimal spanning trees in graphs. 2–coloring and odd cycles in a graph. Depth–first search in a graph and its applications. Properties of depth–first search tree. Graph decomposition algorithms. Graph assembling algorithms. Graph planarity algorithms. Euler problems. Hamiltonian problems. Some packing and covering problems for graphs. Metric problems on graphs. Set transformation algorithms. Search trees of different type. Various sorting algorithms. The main ideas of the NP–theory (the theory of problem complexity).

Justification

Many problems in mathematics and its applications are of a discrete nature. Usually the number of feasible solutions to such a problem increases very rapidly with its size and therefore, it is impossible to find a required solution by searching all alternatives, even with the fastest computers. Accordingly, it is imperative to seek efficient algorithms for solving discrete problems. This course will be very useful to the students studying mathematics and of particular interest to those students who are planning to pursue doctoral studies in discrete mathematics and its applications.

Syllabus

  1. Branch and bound strategy.
  2. Dynamic programming principle.
  3. Optimal paths in graphs (Shortest path in a graph or digraph with nonnegative or arbitrary edge-weights. k–shortest paths. Min-max paths).
  4. Optimal trees in graphs (A spanning tree and a minimum spanning tree in a graph, and a minimum directed tree in a digraph. Min–max and dynamic min–max spanning trees. Steiner trees in graphs. Enumerating spanning trees of graphs. Description of all minimum spanning trees of a graph.).
  5. 2–coloring and odd cycles in a graph.
  6. Depth–first search in a graph and its applications. Properties of depth–first search tree.
  7. Graph decomposition algorithms (Finding components, edge and vertex blocks of a graph, and strongly connected components of digraphs).
  8. Graph assembling algorithms (Ear–decompositions for connected, edge and vertex 2–connected, and 3–connected graphs).
  9. Graph planarity algorithms.
  10. Euler problems (Finding an Euler trail and Euler cycle in a graph or digraph, Fleury’s algorithm. Euler trail set with at most one odd trail. Labyrinth problem. De Bruijn sequences and graphs. The Chinese postman problem.)
  11. Hamiltonian problems (Finding a Hamiltonian path and cycle in a graph. Travelling salesman problem.).
  12. Packing and covering problems for graphs (Matching problems. Disjoint paths. Various generalizations and related problems).
  13. Metric problems on graphs (Radius, diameter, center, and median of a graph. Optimal center location problems for weighted graphs).
  14. Set transformation algorithms. Search trees of different type. Permutations and various sorting algorithms.
  15. The main ideas of the NP–completeness theory.

Text

  1. S. Even, Graph Algorithms, Computer Science Press, 1979.
  2. N. Christofides, Graph Theory. An Algorithmic Approach, Academic Press, 1975.

Bibliography

  1. A.V. Aho, J.E. Hopcroft, J.D. Ulman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1976.
  2. A.V. Aho, J.E. Hopcroft, J.D. Ulman, Data Structures and Algorithms, Addison-Wesley, 1983.
  3. D.E. Knuth, The Art of Computer Programming. Vol.1. Fundamental Algorithms, Addison-Wesley,, 1973.
  4. D.E. Knuth, The Art of Computer Programming. Vol.3. Sorting and Searching, Addison-Wesley, 1973.
Alexander Kelmans
San Juan 1995

MATH 8006. Computers and Intractability. Theory of NP-completeness.

Three credits. Three hours of lecture per week. Prerequisite MATH 8005.

Computers, problems, algorithms, and complexity. Polynomial time algorithms and intractable problems. Provably intractable problems. NP-complete problems. Deterministic Turing machines and the class P. Nondeterministic computation and the class NP. The relation between P and NP. Polynomial transformations and NP-completeness. The Cook–Levin theorem. Basic NP-complete problems. Applying NP-completeness to approximation problems. The structure of NP. The polynomial hierarchy. The complexity of enumeration problems.

Justification

Many problems in mathematics and its applications are of a discrete nature. Usually the number of feasible solutions to such a problem increases very rapidly with the its size and therefore, it is impossible to find a required solution by searching all alternatives, even with the fastest computers. Accordingly, it is imperative to seek efficient algorithms. Unfortunately for most problems, efficient algorithms are not known, and it is not even clear whether such algorithms exist. NP-theory provides an approach for classifying problems according to their complexity (i.e. the degree of their intractability to computers). The theory considers a very rich class of problems (the so called class NP containing most “real” problems. One of the main results of the theory is the fact that there exists a “most complicated” problem in this class. The theory provides a long list of “real” problems that are most complicated. Moreover, most of the problems arising in applications turn out to be “most complicated”. In fact it is very difficult to find a nontrivial problem which can be solved efficiently. Actually the finding of such a “good” problem is a kind of discovery. Typically such results are based on intrinsic properties of the problem and contain deep and non–trivial mathematical ideas. Various “good” problems and main ideas and approaches providing efficient algorithms are discussed in the courses “Discrete Algorithms” and “Combinatorial Optimization I”. The strategy for solving a problem depends on its complexity status. This course provides students with the main ideas, approaches and results concerning the classification of problems by their compexity. This course will be of particular interest to those students who are planning to pursue doctoral studies in discrete mathematics and theoretical computer science.

Syllabus

  1. Computers, Complexity, and Intractability: Problems, algorithms, and complexity. Polynomial time algorithms and intractable problems. Provably intractable problems. NP–complete problems.
  2. The Theory of NP-Completeness: Decision problems, languages, and encoding schemes. Deterministic Turing machines and the class P. Nondeterministic computation and the class NP. The relation between P and NP. Polynomial transformations and NP-completeness. The Cook–Levin theorem.
  3. Proving NP-Completeness Results: Basic NP-complete problems. Some techniques for proving NP-completeness.
  4. Using NP-Completeness to Analyze Problems: Analyzing subproblems. Number problems and strong NP-completeness. Time complexity as a function of natural parameters.
  5. NP-Hardness: Turing reducibility and NP-hard problems.
  6. Coping with NP-Complete Problems: Performance guarantees for approximation algorithms. Applying NP-completeness to approximation problems.
  7. Beyond NP-Completeness: The structure of NP. The polynomial hierarchy. The complexity of enumeration problems. Polynomial space completeness. Logarithmic space. Proofs of intractability and P vs. NP.

Text

M.G. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-completeness, W.H.Freeman and Company, San Francisko, 1979.

Bibliography

  1. S. Even, Graph Algorithms, Computer Science Press, 1979.
  2. A.V. Aho, J.E. Hopcroft, J.D. Ulman, Data Structures and Algorithms, Addison-Wesley, 1983.
Alexander Kelmans San Juan 1995

MATH 8011. Enumerative Combinatorics I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 8001, MATH 6201, MATH 6150

Review of elementary combinatorics. Outline of the main problems and approaches of enumerative combinatorics. Enumerating trees. Matrix–tree theorem. Coding of trees. Counting Euler cycles in a digraph. Counting and listing of nonisomorphic trees of different types. Generating function method in enumerative combinatorics. Enumerating graphs of different types. Pólya’s counting theory of nonisomorphic objects. Enumerating nonisomorphic graphs of different types. Principle of inclusion and exclusion. Lattices, their Möbius functions and Möbius algebras. Asymptotic results in enumerative combinatorics.

Justification

Enumerative combinatorics is an important area of discrete mathematics that concerns the problems of counting and/or listing of objects of different types. It contains many interesting ideas and results that are useful not only in itself but also in various areas of mathematics (analysis, probability, queuing theory, random structures, etc.) and in many applications (physics, chemistry, computer science, network reliability, statistics, electrical circuits, etc.). On the other hand, enumerative combinatorics uses concepts, ideas and results from different areas of mathematics (analysis, group theory, theory of posets and lattices, etc.).

This course will be very useful to the students who are planning to pursue doctoral studies in mathematics and its applications.

Syllabus

  1. Review of elementary combinatorics (Permutations. Combinations. Multinomial coefficient. Binomial expansion. Binomial theorem.).
  2. Outline of main problems and approaches of enumerative combinatorics (Counting and listing. Enumeration problem of different objects and their isomorphism classes.).
  3. Enumerating trees. Matrix–tree theorem. An algorithm for finding formulas of the number of spanning trees of decomposable graphs. Coding of trees of a complete graph and its generalizations. Counting Euler cycles in digraphs. Counting and listing of nonisomorphic trees of different types.
  4. Generating function method in enumerative combinatorics. Enumerating graphs of different types (graphs and digraphs of given size, connected and 2–connected graphs, rooted graphs, Eulerian graphs, tournaments, orientations of a graph, etc.).
  5. Pólya’s counting theory of nonisomorphic objects (Groups and graphs. The cycle index of a permutation group. Burnside’s theorem. Pólya’s theorem.). Enumerating nonisomorphic graphs of different types.
  6. Principle of inclusion and exclusion. Partially ordered sets and their Möbius functions (Posets of different types. Lattices. Möbius functions and Möbius algebras. The Möbius inversion formula). Enumeration of permutations of certain types.
  7. Asymptotic results in enumerative combinatorics.

Text

  1. F. Harary, E.M. Palmer, Graphical Enumeration, Academic Press, New York and London, 1973.
  2. R. Stanley, Enumerative Combinatorics, Volume I, Wadsworth and Brooks/Cole, Monterey, California, 1986.
  3. A. Tucker, Applied Combinatorics, 3rd. ed.,Wiley, 1995.

Bibliography

  1. I.P. Goulden and D.M. Jackson, Combinatorial Enumeration, Wiley, 1983.
  2. D.E. Knuth, The Art of Computer Programming, Vol. I, Addison-Weseley, 1973.
  3. F.S. Roberts, Applied Combinatorics, Prentice–Hall, 1984.
  4. C.L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, 1968.
  5. A.K. Kelmans, Spanning Trees of Extended Graphs, Combinatorica 12 (1) (1992) 45–51.
Alexander Kelmans
San Juan 1995

MATH 8031. Combinatorial Optimization I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 6881, MATH 8001.

Elements of linear and integer programming: branch and bound method and its application to combinatorial optimization problems. Network flow theory and its generalizations: statical maximal flow, feasibility theorems and combinatorial applications, minimal cost flow problems, multi–terminal maximal flows, multi–commodity flows. Matching theory and its generalizations: matchings in bipartite graphs, size and structure of maximum matchings, bipartite graphs with perfect matchings, general graphs with perfect matchings, some graph–theoretical problems related to matchings, matchings and linear programming, matching algorithms, the f–factor problem, vertex packing and covering, some generalizations of matching problems.

Justification

Optimization problems arise in various areas of mathematics as well as in applications (computer science, management science, operations research, physics, engineering, statistics, etc.). The main feature of combinatorial optimization problems is that feasible solutions are of a discrete nature, and therefore the classical methods of optimization based on “small” variations of a feasible solution cannot be applied. Typical examples are integer programming problems which are in general very difficult (NP-hard). Nevertheless efficient algorithms can be found for some natural combinatorial optimization problems. The main approaches, ideas and results along these lines will be discussed in this course. This course will be of particular interest to those students who are planning to pursue doctoral studies in Discrete Mathematics and Theoretical Computer Science.

Syllabus

  1. Elements of linear and integer programming. Branch and bound method and its application to combinatorial optimization problems.
  2. Network flow theory and its generalizations.
    1. Statical maximal flow: Networks. Flows in networks. Cuts. Maximal flow. Multiple sources and sinks. The labelling method for solving maximal flow problems. Dinitz–Tarjan’s and Karzanov’s algorithms for maximal flow problems. Flows in undirected and mixed networks. Node capacities and other extensions.
    2. Feasibility theorems and combinatorial applications: Supply–demands theorems. Circulation theorem. The König–Egerváry and Menger graph theorems. Construction of a maximal independent set of admissible cells. A bottleneck assighnment problem. Unicursal graphs. Dilworth’s chain decomposition theorem for partially ordered sets. Minimal number of individuals to meet a fixed schedule of tasks. Set representatives. Matrices composed of 0’s and 1’s.
    3. Minimal cost flow problems: The Hitchcock problem. The optimal assignment problem. Equivalence of Hitchcock and minimal cost flow problems. The minimal cost supply–demand problem. Maximal dynamic flow. Minimal cost circulations.
    4. Multi–terminal maximal flows: Realization conditions. Equivalent networks. Network synthesis.
    5. Multi–commodity flows.
  3. Matching theory and its generalizations:
    1. Matchings in bipartite graphs: The theorems of Konig and P. Hall. A bipartite matching algorithm. Matchings, flows and measures.
    2. Size and structure of maximum matchings: Tutte’s and Berge’s min-max theorems. Edmonds–Gallai structure theorem.
    3. Bipartite graphs with perfect matchings: Elementary graphs and their ear structure. Minimal elementary bipartite graphs. Decomposition into elementary bipartite graphs.
    4. General graphs with perfect matchings: The canonical partition G. Saturated graphs. Ear structure of 1-extendable graphs. Factor-critical and bicritical graphs. Lovász theorem on ear–decompositions of factor–critical graphs.
    5. Some graph-theoretical problems related to matchings: 2–matchings and 2–covers. Matchings, 2-matchings and the König property. Hamiltonian cycles and 2-matchings. The Chinese postman problem. Optimum paths, cycles, joins and cuts.
    6. Matchings and linear programming: Linear programming and matchings in bigraphs. Matchings and fractional matchings. The matching and fractional matching polytopes. Chromatic index. The dimension of the perfect matching polytope.
    7. Matching algorithms: The Edmonds matching algorithm. Weighted matchings. An algorithm based upon the Edmonds–Gallai theorem. A linear programming algorithm for matchings.
    8. The f–factor problem: Reduction principles. A structure theory for f–factors. Realization of degree sequences.
    9. Vertex packing and covering: Critical graphs. Vertex packing polytopes. Hypergraph matching. Vertex packing in claw-free graphs.
    10. Some generalizations of matching problems: Optimal packing of special subgraphs of a graph. Kelmans’ min-max and structure theorems on induced stars in a graph. Packing paths, cycles, joins and cuts.

Text

  1. M. Plummer and L. Lovász, Matching Theory, North-Holland, 1986.
  2. L.R. Ford and D.R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962.

Bibliography

  1. E. L. Lawler, Combinatorial Optimization; Networks and Matroids, Holt Rinehart and Winston, New York, 1976.
  2. A. Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons, Chichester, New York, Brisbane, Toronto, Singapore, 1987.
  3. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, Chichester, 1988.
  4. T.C. Hu, Integer Programming and Network Flows, Reading, Addison–Wesley Publ. Co., London–Don Mills, Ont., 1970.
Alexander Kelmans San Juan 1995

MATH 8041. Matroid Theory I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 6150, MATH 8001.

Fundamental concepts and axioms of matroid theory. Duality in matroids and matroid operations. Vector representation of matroids. The matroid of a graph and graph planarity. Greedy algorithms on matroids. The union of matroids and its rank function. Efficient algorithms for some combinatorial optimization problems (packing, covering, intersection etc.) on matroids with applications to a variety of combinatorial objects (e.g. graphs, matrices, algebraic dependencies, transversals).

Justification

It is difficult to overestimate the importance of matroid theory in contemporary applied and theoretical mathematics. It provides a common basis for understanding and solving a variety of problems in a wide range of areas including graph theory, linear algebra, geometry, transversal theory, block design, combinatorial lattice theory and algebraic geometry. Matroid theory serves as a link between combinatorics and other mainstream areas of mathematics. It plays an extremely important role in combinatorial optimization where it can be used to find combinatorial structures for which the corresponding optimization problems can be solved in polynomial time. Moreover, it provides efficient procedures (described in rather general terms) for solving those problems and for designing the corresponding polynomial time algorithms. This course will be of particular interest to those students who are planning to pursue doctoral studies in either pure or applied mathematics.

This course will be of particular interest to those students who are planning to pursue doctoral studies in either pure or applied mathematics.

Syllabus

  1. Fundamental concepts and axioms of matroid theory.
  2. Independent sets and bases of a matroid.
  3. Circuits and the rank function of a matroid.
  4. Examples of matroids.
  5. Duality in matroids.
  6. Operations on matroids and submatroids (truncation, restriction, contraction, etc.).
  7. The closure operator, closed sets = flats = subspaces, and hyperplanes of a matroid.
  8. The lattice of a matroid.
  9. Vector representation of matroids, the matroid of a linear subspace, special matroids.
  10. Matroid connectivity. The matroid of circuits of a graph, circuit isomorphisms and semi-isomorphisms of graphs.
  11. Geometrical and matroid dualities of graphs, a planarity criterion of a graph in terms of its matroid.
  12. The greedy algorithm, the “greedy” characterization of matroids.
  13. Minimax and dynamic minimax problems for matroids.
  14. A description of the matroid of the minimum bases of a matroid.
  15. The union of matroids and its rank function.
  16. Efficient algorithms for finding a base of the union of matroids, and for covering, packing and intersection problems for matroids.

Text

  • D.J.A. Walsh, Matroid Theory, Academic Press, 1976.

Bibliography

  1. J. G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.
  2. E. L. Lawles, Combinatorial Optimization Networks and Matroids, Holt Rinehart and Winston, New York, 1976.
  3. W. T. Tutte, Introduction to the Theory of Matroids, Elsevier, New York, 1970.
  4. A. K. Kelmans, Matroids and Combinatorial Optimization Problems, Institute of Control Sciences, Moscow, 1989.
  5. P. D. Seymour, Decomposition of Regular Matroids, J. Combin. Theory B 28(1980) 305–359.
Alexander Kelmans
San Juan 1995
Mathematics, Pro-Life

Condom Roulette


In 2004 August more than 40 million condoms of the Engabu brand were found to be defective and were recalled to be destroyed. This was after a huge public outcry concerning condom failures which may have exposed many people to HIV/AIDS. Unfortunately, more reliable condoms are not a solution. Independent of the reliability p, repeated use of condoms with a p% failure rate is like unto a game of Russian Roulette with a 100/p chambered revolver —so, for example a 20% failure rate would correspond to Russian Roulette with a five chambered revolver. The outcome of such a game is determined by:

Theorem. The risk of contracting AIDS during so-called “protected sex”approaches 100 percent as the number of episodes of sexual intercourse with an infected person increases.

Proof: Consider a Bernoulli random variable with value 1 if condom fails and zero otherwise. Let X be the sum of n such variables. Assume the variables are independent and identically distributed. For any n, the sum has a binomial distribution and it is a simple exercise to show that the probability that X > 0 (i.e. of at least one failure) approaches 1 as n increases.

Condom promotion spreads HIV

Two important related and seemingly contradictory effects are possible when condoms are promoted:

  • E1. A reduction in virus transmission probability per coital act when condoms are used.
  • E2. An overall increase in transmission rate in the population due to increases in promiscuity encouraged by the promotion of condoms.

Since factors (E1) and (E2) work in opposite directions, much polemic has been generated by those who, for economic or ideological motives or simply because they fail to understand that both effects are simultaneously possible, focus only on E1 and ignore the above theorem. In reality, evidence indicates that when condoms are distributed, the alleged benefit due to factor E1 is more than nullified by E2. According to Dr. Edward C. Green, director of the AIDS Prevention Research Project at the Harvard Center for Population and Development Studies,

“There is a consistent association shown by our best studies, including the U.S.-funded ‘Demographic Health Surveys,’ between greater availability and use of condoms and higher (not lower) HIV-infection rates,” he said in an interview earlier this year.

“This may be due in part to a phenomenon known as risk compensation,” Green explained, “meaning that when one uses a risk-reduction ‘technology’ such as condoms, one often loses the benefit (reduction in risk) by ‘compensating’ or taking greater chances than one would take without the risk-reduction technology.”

If a group or individual is already maximally promiscuous and condom using, effect E2 will be negligible. However, in this case, the reduction in transmission probability per coital act achieved by condoms will be more than counterbalanced by the fact that, for HIV discordant couples, the asymptotic limit of repeated condom roulette is virus transmission with probability 1. As a result, the overall residual infection rate for such a group will remain high —despite condom promotion and use. Only behavioral shifts can reduce overall infection rates. This partly explains why, notwithstanding the promotion of condoms, transmission rates for certain populations, such blacks in many US inner city areas and gays have remained many times the average for the population as a whole. In the case of gays, reductions in average life spans exceeding 8 years have been observed and, in some studies as much 20 years. HIV infection rates for US blacks in 2003 were 650% higher than for the population as a whole.

For populations of intermediate promiscuity, effect E2 will tend to outweigh E1 and the promotion of condoms can be expected to increase the net infection rate, a fact in accordance with the studies cited by Green. It is notable that every year, for many years, the South African government has distributed hundreds of millions of condoms in a futile bid to control the AIDS epidemic. Despite this, the AIDS rate has risen to almost 30%. and millions are condemned to die in this futile and unethical attempt to refute the now empirically based null hypothesis that “condoms are ineffective in fighting the AIDS epidemic”.

In the case of a highly monogamous population, factor E1 is insignificant and promotion of condoms can only increase the virus transmission rate. This might be the case in some
poor countries, where promiscuity is kept low, precisely because the majority of the population can afford neither condoms nor the shame of children born out of wedlock. In such a situation the false sense of security caused by the distribution of free condoms can be especially significant in increasing disease transmission. Moreover, the very notion that unfaithful men will use condoms to protect their wives is absurd. In reality many prefer to hide their unfaithfulness and/or HIV status. And what of normal couples who want children?

In every case, we see that the promotion of condoms fails stop the AIDS epidemic and can actually increases the level of infection. Despite the annual use of over 10 billion condoms AIDS rates remain high. Halting the epidemic can only be done by promoting abstinence and monogamy. In this sense, the recent controversial claim by Pope Benedict that condoms cannot stop the AIDS epidemic and can even worsen it is good science and good mathematics. Those who proclaim otherwise may have blood on their hands.

Some Statistics

The following table based upon data from the 2003 World Factbook of the US Central Intelligence Agency shows HIV/AIDS rates as a function of Catholic population.

CountryReligion% Aids Infection
Burundi62% Catholic6%
Angola38% Catholic3.9%
Ghana63% Christian3.1%
Uganda33% Catholic (66%christian)4.1%
Botswana5% Catholic37.3%
South Africa6% Catholic21.5%

The available statistics show that countries with a large Catholic percentage population, show significantly lower rates of HIV/AIDS infections than countries with mostly non-Catholic populations.

References

  1. EPIDEMIOLOGIST: POPE IS RIGHT ABOUT CONDOMS —Says Issue Is a “Prisoner of Ideology” Zenit 2009-09-15
  2. Will Condoms Really Stop AIDS In Africa?