User joseph malkevitch - MathOverflow

Answer by Joseph Malkevitch for Probability of random permutation having certain cycles

2010-07-24T15:58:53Z

Perhaps this article might be of use?

http://www.jstor.org/pss/1994483

(Ordered cycle lengths in a random permutation)

Answer by Joseph Malkevitch for What is the first interesting theorem in (insert subject here)?

2010-07-23T23:04:04Z

Game Theory:

A zero-sum 2x2 (two person) matrix game which has no dominating strategy has an optimal mixed strategy, and the game is fair (0 expected value) if the determinant of the payoff matrix (say from the row player's point of view) is zero.

Answer by Joseph Malkevitch for Cycles of length 1(mod 3) in regular graphs

2010-07-22T13:13:31Z

This paper shows that such graphs may lack a cycle of a particular length:

Some 4-valent, 3-connected, planar, almost pancyclic graphs

S. A. Choudum

Discrete Mathematics, Volume 18, Issue 2, 1977, Pages 125-129

Abstract:

For each positive integer k (≠ 5,6), a 4-valent, 3-connected, planar graph, having cycles of all (possible) lengths except k is constructed.

Answer by Joseph Malkevitch for Planar sets where any line through the center of mass divides the set into two regions of equal area.

2010-07-21T00:08:38Z

For those who found this problem of interest there is a large literature dealing with area bisectors (and a separate literature for perimeter bisectors) of polygons, convex or otherwise (including the allowing of holes in the area case). For example for a triangle it makes a nice exercise to think through where the points in the interior of any triangle are which allow the drawing of exactly one, exactly two, and exactly three area bisecting lines. (Hint: Remember some of the basic properties of the conic sections.) There are also generalizations related to finding points which admit lines which divide the area of the regions cut off by the lines into parts of equal area.

Here are some references that take off from this circle of ideas but there are many more:

http://www.springerlink.com/index/AYY2HB2LQ7MG392F.pdf

http://www.springerlink.com/content/p555523k357464p8/

Answer by Joseph Malkevitch for Examples of self-centered graphs (with large radius)

2010-07-18T03:54:35Z

There is a discussion of self-centered graphs in:

Fred Buckley and Frank Harary, Distances in Graphs, Addison-Wesley, 1990.

The discussion of self-centered graphs is on pages 38-42 (and a few other pages), and Fred Buckley wrote some other papers on this subject but I don't have the references immediately available.

Answer by Joseph Malkevitch for Algorithms for maximum weighted spanning (connected) dag (directed acyclic graph)

2010-07-14T16:24:14Z

You might try:

Exact arborescences, matchings and cycles by Francisco Barahona and William R. Pulleyblank

Discrete Applied Mathematics Volume 16, Issue 2, February 1987, Pages 91-99

Answer by Joseph Malkevitch for Euclid with Birkhoff

2010-07-05T14:21:54Z

I am not sure this qualifies under short and elementary but I recommend:

Geometry: A Metric Approach with Models

Richard Millman and George Parker; Springer-Verlag, NY, 1981

(there may be a more recent edition, I did not check).

This book does treat hypberbolic geometry.

Answer by Joseph Malkevitch for determining k-edge-connectivity of a graph

2010-07-04T12:12:15Z

Try:

http://portal.acm.org/citation.cfm?id=122416

and the references there.

Answer by Joseph Malkevitch for Solving a system of linear inequalities -- what is the dimension of the solution set?

2010-07-04T02:31:58Z

Look into Fourier-Motzkin:

http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination

Answer by Joseph Malkevitch for When sticks fall, will they weave?

2010-06-27T12:47:58Z

There is work by Walter Whiteley

http://www.springerlink.com/content/l145617681626324/

and Robert Connelly

http://www.math.cornell.edu/~connelly/Tensegrity-Global.pdf

which though not dealing with probabilistic matters may be of interest or of use.

Answer by Joseph Malkevitch for Ways to "regularize" a graph

2010-06-17T22:53:47Z

While not dealing with regularization in general perhaps these observations may be of interest. Graphs with special properties often lend themselves to operations on the graph which lead to "nice" properties on the transformed graph.

If one starts with a planar 3-connected graph (which by Steinitz's Theorem is a 3-polytopal graph, the vertex-edge graph of some 3-dimensional convex polyhedron) then one can construct the dual of this graph and obtain another planar 3-connected graph. If one starts with a planar 3-connected graph, first construct from it the medial graph. This is done by having a vertex for each edge of the graph, and joining two of these vertices in the medial graph with an edge if the edges they represent share a vertex and lie in the same face of the original graph. The resulting graph has the nice property that it is planar, 3-connected and every vertex has valence 4. Thus, if one dualizes this graph one gets a graph which which is bipartite, planar, and 3-connected, which is "related" to the original graph. In fact, all of its faces will have 4 sides. There are similar transformations which start with a plane 3-connected graph and transform it via a chain of operations into a graph all of whose faces have 5 sides.

Answer by Joseph Malkevitch for Texts on the General History of Contemporary Combinatorics

2010-05-18T20:37:00Z

While not a history of the combinatorics involved there is a very nice biographical essay by L. Babai, In and Out of Hungary: Paul Erdös, His Friends and His Times that appears in the book honoring Erdös' 80th birthday, Combinatorics, Paul Erdös is Eighty, Vol. 2, Janos Bolyai Mathematical Society, Budapest, 1996, pp. 7-96.

Answer by Joseph Malkevitch for Reconstructing a fraction from its first digits

2010-05-17T18:48:53Z

Henry Pollak has written a nice series of articles about how given a positive decimal one can construct a rational fraction that is approximately equal to the given decimal number. The first of these articles appeared in COMAP's (Consortium for Mathematics and Its Applications) newsletter Consortium, and can be found at this link:

http://webmail.comap.com/www.comap.com/pdf/749/Cons92.pdf

while the second article is here:

http://webmail.comap.com/www.comap.com/pdf/1004/C95.pdf

and the last article:

http://ns.comap.com/www.comap.com/pdf/1028/Con96.pdf

Answer by Joseph Malkevitch for Fields of mathematics that were dormant for a long time until someone revitalized them

2010-05-11T21:03:08Z

This example may not be that of a whole field but I think it illustrates an important result that lay dormant for a very long time. A natural question in the theory of graphs is when is a graph the vertex-edge graph of a 3-dimensional convex polyhedron? It turns out that this question was in essence answered by Ernst Steinitz in 1922. However, Steinitz did not use a graph theory framework for his work. As a consequence, almost no one noticed what he had accomplished. Almost no references to Steinitz's work was made until 1962 and 1963 when Branko Grünbaum and Theodore Motzkin wrote two papers where they mentioned what Steinitz had done but reformulated it using graph theory terminology. The result in these terms, now known as Steinitz's Theorem states that a graph is the vertex-edge graph of a convex 3-dimensional polyhedron if and only if the graph is planar and 3-connected. A good place to read about this is in Grünbaum's book: Convex Polytopes (2nd edition). Grünbaum (and others) went on to produce many papers that exploited Steinitz's Theorem in many directions. One way to think of what was accomplished here was that to study the combinatorial properties of 3-dimensional convex polyhedra one does not have to think in 3-dimensions but only in 2 dimensions.

Answer by Joseph Malkevitch for Reference Request: Perspective Painting

2010-05-09T14:51:57Z

You might look at:

http://www.springer.com/mathematics/geometry/book/978-0-387-97486-6

which provides the contributions of Brook Taylor and places his contribution in historical pesrpective.

Answer by Joseph Malkevitch for What are trig classes like within a universe that's "noticeably" hyperbolic?

2010-05-06T01:03:23Z

Chapter V of Harold E. Wolfe's book: Introduction to Non-Euclidean Geometry (Holt, Rinehart, and Winston), 1945 (and reprinted, 1966) is entitled: Hyperbolic Plane Trigonometry, and has a systematic treatment of this topic.

Answer by Joseph Malkevitch for Frobenius number for three numbers

2010-05-04T16:07:05Z

Several expository papers about the Frobenius problem and its generalizations can be found on Jeffrey Shallit's web page:

http://www.cs.uwaterloo.ca/~shallit/talks.html

and a more technical journal article is linked here:

http://www.springerlink.com/content/655j4t10575052h7/

Answer by Joseph Malkevitch for Is there any geometry where the triangle inquality fails?

2010-04-30T15:39:30Z

In the Euclidean plane when equality holds in the triangle inequality the points lie along a line of the geometry (degenerate triangle). However, for the triangle inequality in the Taxicab Plane (distance given by sums of absolute values of the differences in the coordinates) points which do not lie along a line of the geometry can have the sum of two sides of a triangle with equal length to the third.

Answer by Joseph Malkevitch for Mathematicians who were late learners?-list

2010-04-29T18:34:42Z

Dennis Sullivan who won the 2010 Wolf Prize comments on this in his own words in the magazine published by the New York Academy of Sciences:

http://www.nyas.org/Publications/Detail.aspx?cid=14047af0-9f26-481c-9b50-9434130c89db

Answer by Joseph Malkevitch for Is the area of a polygonal linkage maximized by having all vertices on a circle?

2010-04-27T20:32:24Z

A theorem of Connelly, Demaine, and Rote shows that a variety of plane linkages can be convexified or straightened:

http://erikdemaine.org/papers/Linkage/

Ileana Streinu recently won the Robbins Prize for very innovative approach to solving problems of this kind.

Answer by Joseph Malkevitch for What is your favorite "strange" function?

2010-04-23T14:18:47Z

f(x) = sin (1/x): (x not 0); f(x) = 0 (x equals 0)

Answer by Joseph Malkevitch for The Symmetry of a Soccer Ball

2010-03-30T12:37:59Z

From a combinatorial point of view one can define a fullerene to be a 3-valent 3-connected graph with exactly 12 faces which are 5-gons (pentagons) and h 6-gons (hexagons). By Steinitz's Theorem fullerenes which exist as graphs can be realized by convex polyhedra. Branko Grunbaum and Theodore Motzkin showed, The number of hexagons and the simplicity of geodesics on certain polyhedra, Canadian J. Math., 15 (1963) 744-751, that the admissible values of h for such graphs are all non-negative integers h except h = 1. Other proofs of this, given by construction, show other features than what Grunbaum and Motzkin did. (For references see article listed below.)

What are the symmetry groups which can arise as the automorphism groups of fullerene graphs? There are only 28 such groups and they are listed on page 36 of the book: Geometry of Chemical Graphs: Polycylces and Two-Faced Maps, by Michel Deza, and Mathieu Dutour Sikiric, Cambridge U. Press, 2008. By a theorem of Peter Mani, these fullerene graphs can be realized by 3-dimensional polyhedra with the full automorphisms group of the graph as the group of isometries of the realizing polyhedron.

For further discussion of fullerenes and some open problems about fullerene graphs see:

Malkevitch, J., Geometrical and Combinatorial Questions about Fullerenes, in Discrete Mathematical Chemistry, (P. Hansen, P. Fowler, M. Zheng, eds.), Volume 51, DIMACS Series in Discrete Mathematics and Computer Science, AMS, Providence, 2000, pp. 261-266.

Answer by Joseph Malkevitch for Is every finite group a group of "symmetries"?

2010-03-27T18:27:44Z

I consulted Laszlo Babai (University of Chicago) who has written extensively on the subject of automorphism groups, on the following issue:

Given any group H is there always a planar 3-connected graph G (hence a 3-polytopal graph by Steinitz's Theorem) such that the automorphism group of G is H? (By a theorem of Peter Mani's if such a graph G existed for H then there would be a realization of the graph G as the vertex-edge graph of a 3-polytope P such that the isometries of P would be H.)

Professor Babai informed me that there is no universal theorem here. He offered the 8 element quaternion group as an example of a group H which does not arise as the automorphism group of a planar 3-connected graph.

Here are references to some of his papers that treat aspects of this and related issues:

L. Babai, and W. Imrich: On groups of polyhedral graphs, Discrete Math. 5 (1973), 101-103.

L. Babai: Automorphism groups of planar graphs I, Discrete Math. 2 (1972), 285-307.

L. Babai: Automorphism groups of planar graphs II, in, Infinite and finite sets (Proc. Conf. Keszthely, Hungary, 1973, A. Hajnal et al eds.) Bolyai - North-Holland (1975), 29-84.

L. Babai: Groups of graphs on given surfaces, Acta Math. Acad. Sci. Hung. 24 (1973), 215-221.

L. Babai: Automorphism groups of graphs and edge-contraction, Discrete Math. 8 (1974), 13-20.

L. Babai: Vertex-transitive graphs and vertex-transitive maps, J. Graph Theory 15 (1991), 587--627.

It also turns out there is a paper by: Jurgen Bokowski, G. Ewald, and P. Kleinschmidt, On the combinatorial and affine automorphisms of polytopes, Israel J. of Math., 47 (1984) 123-130 with the following abstract, which may be of interest to those thinking about this circle of ideas:

Abstract We disprove the longstanding conjecture that every combinatorial automorphism of the boundary complex of a convex polytope in euclidean space E d can be realized by an affine transformation of Ed.

Answer by Joseph Malkevitch for Finding all paths on undirected graph

2010-03-19T01:42:35Z

For shortest paths look at:

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

and also:

http://www.springerlink.com/content/t53j31t5012v6605/

Answer by Joseph Malkevitch for Given N points on a number line and m total distances between those points, are there efficent ways to optimize for particular values in m?

2010-03-17T03:50:40Z

You may want to look into what are called Golomb Rulers:

http://en.wikipedia.org/wiki/Golomb_ruler

Answer by Joseph Malkevitch for Strings and "co-subsequences"

2010-03-15T12:30:26Z

The combinatorics of words (strings) is a relatively new area of interest for mathematicians and computer scientists so perhaps it is not surprising that there is somewhat wide variation in terminology for this emerging field. However, there are already a wide variety of books that treat questions in this area:

Jewels of Stringology, Maxime Crochemore and Wojciech Rytter

Algorithms on strings, trees, and sequences, Dan Gusfield

Combinatorics on Words, M. Lothaire

Applied Combinatorics on Words, M. Lothaire

Sequence Comparison, Kun-Mao Chao and Louxin Zhang

Answer by Joseph Malkevitch for Tetrahedra with prescribed face angles

2010-03-13T22:35:04Z

There is an article by K. Wirth and A. Dreiding which you might find helpful:

Edge lengths determining tetrahedrons

Elmente der Mathematik, volume 64, (2009) 160-170.

The the title talks about edge lengths, but the approach taken involves taking a triangle drawn in the plane and placing three triangles along its edges to form a "net" with which to try to fold the result into a tetrahedron. The paper discuss circumstances under which this can be done.

Answer by Joseph Malkevitch for Suggest effective heuristic (not precise) graph colouring algorithm

2010-03-12T22:31:45Z

You might find this survey article of use:

http://www.springerlink.com/content/r66452u84130n423/

Answer by Joseph Malkevitch for Is every finite group a group of "symmetries"?

2010-02-16T02:51:28Z

Suppose one has a convex 4-gon in the plane. What symmetry groups can it have?

The graph of this convex 4-gon is a 4-cycle so as a graph its automorphism group is the dihedral group which I will denote D(4) which has 8 elements. Now there is a convex 2-dimensional polygon which has this as its group, namely a square. However, The group D(4) has a cyclic subgroup of order 4, yet there is NO convex 4-gon which has the cyclic group of order 4 as its set of isometries. There is a rectangle with unequal sides which has a group of order 4 as its symmetry group but this is the Klein group, not the cyclic group, of order 4.

For 3-dimensions, a similar thing can happen. It is known that the vertex-edge graph of any 3-dimensional convex polytope is a planar and 3-connected graph and the converse holds. This is Steinitz's Theorem. Suppose H is such a graph (e.g. planar and 3-connected) and the (full) automorphism group of H is G. There is a beautiful theorem of Peter Mani's which states H can be realized in 3-space by a metric polytope P which has group G as its group of isometries. However, it does not follow that for any subgroup I of G that there is a 3-dimensional convex polyhedron whose group of isometries is I. In fact, for the group with 48 elements which is the isometry group of the graph of the 3-cube there is a subgroup of order 24, the rotation group, but there is no 3-dimensional convex polyhedron which is combinatorially a 3-cube which has 24 isometries.

Here is the reference for Mani's paper:

P. Mani, Automorphismen von polyedrischen Graphen, Math. Ann. 192 (1971) 279–303.

This is a generalization of this theorem to complexes, as mentioned in this paper:

http://arxiv.org/abs/math/0310165

If you restrict your attention to graphs rather than polytopes there is a nice theorem of Roberto Frucht.

For any finite group H, there is a graph G(H) such that the automorphism group of G(H) is H.

There are extensions of Frucht's Theorem including to 3-valent graphs. If there was an extension of Frucht's theorem to planar 3-connected graphs than via Steinitz's Theorem the original question would be answered. I am not sure if this has been done or not.

A survey paper (about graphs with specified automorphism groups and related matters) of Babai's is available:

www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps

Answer by Joseph Malkevitch for Interesting applications of max-flow and linear programming

2010-02-17T19:47:36Z

Take a look in the book:

Network Flows: Theory, Algorithms, and Applications

by: R. Ahuja, T. Magnanti, and J. Orlin

Prentice-Hall, 1993.

There you will find many examples of the kind that you are asking for.

Comment by Joseph Malkevitch

2010-08-08T15:28:09Z

Have other variants of this type of problem been studied where instead of attaching a triangle to each side of the polygon one attaches some other shape?

Comment by Joseph Malkevitch

2010-08-06T16:49:39Z

Ideas in this paper might be of use: math.princeton.edu/mathlab/jr02fall/Periodicity/…

Comment by Joseph Malkevitch

2010-07-22T21:37:50Z

Gjergij: Yes, that is correct. While not noted above there is quite a large literature about the existence (or lack of existence) of cycles in graphs, in particular mod m. Perhaps things are easier in the case that interests you for planar graphs.

Comment by Joseph Malkevitch

2010-07-20T01:09:52Z

Comments about and samples of George Hart's fascinating work can be found here: richbugger.wordpress.com/2009/12/04/…

Comment by Joseph Malkevitch

2010-07-13T12:39:44Z

You might consider looking at this circle of ideas for planar graphs. David Barnette showed that for a planar 3-connected graph there is always a spanning tree of maximum valence 3. However, if I remember properly, he also showed that for d-polytopal graphs (d more than 3) that there is no uniform upper bound for the valence of a spanning tree. d-polytopal graphs are known to be d-connected. This paper might also be of interest: citeseerx.ist.psu.edu/viewdoc/…

Comment by Joseph Malkevitch

2010-07-05T14:59:10Z

If I have a pdf file on my computer (I use a MAC) and transfer it to an Ebook reader such as the Kindle, do I incur a financial charge for doing this?

Comment by Joseph Malkevitch

2010-07-05T14:37:09Z

This book does not treat the hyperbolic plane. Another advantage of Millman and Parker, Geometry: A Metric Approach with Models is that it has a much more modern flavor treating things like the taxicab plane, the Moulton plane, etc.

Comment by Joseph Malkevitch

2010-05-14T14:30:29Z

Such polyhedra are called unistable or monostatic, and there are some references here: en.wikipedia.org/wiki/Monostatic_polytope

Comment by Joseph Malkevitch

2010-05-12T14:03:41Z

Grünbaum has in two other publications shown the value of taking a "fresh look" at geometrical/combinatorial problems that had been considered by geometers/combinatorialists in the past (19th century), using the power of more recent ideas and methods. These are: Arrangements and Spreads (American Mathematical Society, 1972) and the very recent book: Configurations of Points and Lines (AMS, 2009). Arrangements and Spreads has stimulated many new results in geometry and computational geometry.

Comment by Joseph Malkevitch

2010-05-01T01:01:16Z

The way the Taxicab Plane is defined is that the points are ordered pairs of real numbers and lines are, as in the Euclidean plane, the linear equations. All the only axiom of Euclidean geometry that Taxicab Geometry fails to satisfy is the triangle congruence axiom.

Comment by Joseph Malkevitch

2010-04-29T23:38:06Z

Here is what Dennis said: "I was a late bloomer academically in the sense that I didn't have any pressure to study when I was growing up. In college I got back into academics again and made a fresh start. I was able to attend Rice University in Houston, which at the time was like a scaled-down Caltech. I rediscovered my academic self there after being a quasi juvenile delinquent, running around working on hotrods!" He has some additional remarks not pasted in here.

Comment by Joseph Malkevitch

2010-04-23T15:32:37Z

The functions one learns about early in studying mathematics are chosen to illustrate various "issues:' continuity, having a derivative, being periodic, etc. One of the functions one learns about in this way is y = sin(x). So while there are many functions that are "strange," the transition from y = sin (x) to y = sin (1/x) offers I feel lots of nice lessons about functions and their behavior. There are many web sites that use graphics to help one understand what is going on here. One such site is: math.washington.edu/~conroy/general/sin1overx

Comment by Joseph Malkevitch

2010-04-20T13:11:43Z

Some but not all have taken issue with some of Cajori's scholarship.

Comment by Joseph Malkevitch

2010-04-20T13:10:12Z

Perhaps this paper might be of use: springerlink.com/content/t011882045102k27

Comment by Joseph Malkevitch

2010-03-31T17:46:58Z

Usually symmetry issues are not discussed in discussions of being shellable but you may find the information on this web page, and the references given there of use: eg-models.de/models/Simplicial_Manifolds/…