mm-397 === Subject: : Paper published by Geometry and TopologyOriginator: bergv@math.uiuc.edu (Maarten Bergvelt)The following paper has been published:URL:http://www.maths.warwick.ac.uk/gt/GTVol8/paper13 .abs.htmlTitle:The metric space of geodesic laminations on a surface: IAuthor(s):Xiaodong Zhu, Francis BonahonAbstract:We consider the space of geodesic laminations on a surface, endowedwith the Hausdorff metric d_H and with a variation of this metriccalled the d_log metric. We compute and/or estimate the Hausdorffdimensions of these two metrics. We also relate these two metrics toanother metric which is combinatorially defined in terms of traintracks.Secondary: 37E35Keywords:Geodesic lamination, simple closed curveProposed: Jean-Pierre OtalSeconded: David Gabai, Martin BridsonAuthor(s) address(es):NetScreen Technologies, 805 11-th Avenue Building 3, Sunnyvale, CA 94089, USA and Department of Mathematics, University of Southern CaliforniaLos Angeles, CA 90089-1113, USAEmail: xzhu@netscreen.com, fbonahon@math.usc.eduURL: http://math.usc.edu/~fbonahon=== === Subject: : Spring Pacific NW Geometry SeminarOriginator: bergv@math.uiuc.edu (Maarten Bergvelt) First announcement: PACIFIC NORTHWEST GEOMETRY SEMINAR University of Utah Salt Lake City, UTSPEAKERS:Ian Agol (Illinois/Chicago)Ben Chow (UCSD)iel Pollack (University of Washington)Brian White (Stanford)Michael Wolf (Rice)The titles and schedule will be announced soon.--------------------------------------------------------- --TRAVEL SUPPORT:PNGS meetings are supported by funds from the National ScienceFoundation and the Pacific Institute for the MathematicalSciences. Limited travel support is available for participants inthis meeting. First priority goes to graduate students and facultyfrom the participating universities (Portland State, Oregon State,Stanford, U. of Oregon, UBC, U. of Washington). If you areaffiliated with one of these universities and are interested intravel support, please contact one of the PNGS organizers at youruniversity NO LATER THAN APRIL 2:PSU Serge Preston as soon as possible.----------------------------------------------------- ------For general information about the PNGS, visit the PNGS web site: http://www.math.washington.edu/~lee/PNGSIt contains up-to-date information about this meeting, travelinformation, general information about the PNGS, and a historicalrecord of all PNGS meetings and speakers.----------------------------------------------------- ------For more information about this meeting, contact theorganizer: Jesse Ratzkin (ratzkin@math.utah.edu)=== === Subject: : The distribution of the minimum of several normal distributed r.v's?Originator: bergv@math.uiuc.edu (Maarten Bergvelt)hi, everyoneSuppose now we have N normal distributed r.v's X1, X2, ..., Xnwith mean ui and variance v2i. Is there an analytical approximationof Prob[X1 <= min(X2, ..., Xn)] ?Fan=== === Subject: : Re: The distribution of the minimum of several normal distributed r.v's?Originator: bergv@math.uiuc.edu (Maarten Bergvelt)>hi, everyone>Suppose now we have N normal distributed r.v's X1, X2, ..., Xn>with mean ui and variance v2i. Is there an analytical approximation>of Prob[X1 <= min(X2, ..., Xn)] ?The function is clearly an analytic function of theu's and v2's.But I do not know of any easy computational method, evenasuming the X's are independent, for n > 2. In theindependent case, it can be done by one integration of aproduct of normal probabilities with respect to a normaldensity.This address is for information only. I do not claim that these viewsare those of the Statistics Department or of Purdue University.Herman Rubin, Department of Statistics, Purdue Universityhrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558=== === Subject: : Re: Graph IsomorphismOriginator: bergv@math.uiuc.edu (Maarten Bergvelt) > I said you try all column permutations, but you still have to write the > rows in the same order the columns appear as well. (i.e. apply the same > permutation to both column and row.)certain size n? It would become impractical to iterate over allpossible adjacency matrices trying to detect whether they areisomorphic to any previously generated matrices. For instance if n=7,then there are 2^49 possible matrices. Is there a way to do thisefficiently?=== === Subject: : Re: Graph Isomorphism I said you try all column permutations, but you still have to write the > rows in the same order the columns appear as well. (i.e. apply the same > permutation to both column and row.)> certain size n? It would become impractical to iterate over all> possible adjacency matrices trying to detect whether they are> isomorphic to any previously generated matrices. For instance if n=7,> then there are 2^49 possible matrices. Is there a way to do this> efficiently? That's correct, a brute-force method to generate all distinct (with respect to isomorphism) graphs can get very costly. There are many ways to prune-out information and save time along the way. There is a program that will generate all 7-vertex graphs, I think, in the blink of an eye. It is called 'geng' and is part of the NAUTY package that is freely available over the web. You can throw options into geng to create only (say) bipartite graphs, or triangle-free graphs, or graphs with n vertices and m edges, or any combination of the above and more. It's quite nifty. Here is the main page for NAUTY: http://cs.anu.edu.au/~bdm/nauty/ and there are associated discussion mailing lists you can join if you want to be asking specific questions about these types of concepts. I do not really know how geng works, but I'm always impressed with its speed.J (I think the general idea is this: For every graph, there is somenormal-form representation of it, such that for any two graphs, theirnormal-form representations are equivalent if and only if the graphs areisomorphic. [Obviously, this is not done in wosrt-case polynomial time,but note that over random graphs isomorphism is solvable in expectedpolytime, so there are many good heuristics used in helping to find thesenormal forms.] I think to generate all distinct graphs on 7 vertices, itgenerates the normal forms for 6-vertex graphs and tries all distinct1-vertex-extensions from those... and, of course, to get all 6-vertexgraphs, the process is done on smaller graphs. I'm not positive that itworks this way, but that's my guess.)=== === Subject: : Re: Graph IsomorphismOriginator: bergv@math.uiuc.edu (Maarten Bergvelt)> certain size n? It would become impractical to iterate over all> possible adjacency matrices trying to detect whether they are> isomorphic to any previously generated matrices. For instance if n=7,> then there are 2^49 possible matrices. Is there a way to do this> efficiently?1) asymptotically, the number of labeled graphs has the same growth rate as unlabeled (nonisomorphic w.r.t. node labeling). So If you are generating -all- unlabeled graphs, it will take (rouhgly) as much time as generating all labeled ones. so the appropriate way to compare generationmethods is how long it takes to find a new, previously ungenerated graph.This is just to point out that in your statement it would be better to emphasize trying to detect whether... as opposed to iterate over all adjacency matrices (which you will practically hacve to do anyway).2) One way to check if a new labeled graph is a new unlabeled one (without having to maintain a list of all the previously generated unlabeled graphs) is tocome up with a canonical representation/comparison algorithm; that is, an algorithm that converts a labeled graph to a canonical unlabeled form (such that two isomorphic graphs have the same canonical representation).Then you can compare canonical forms lexicographically to see which one is bigger. So all you need to do is keep the canonical form for the last generated graph, then compute the canonical form for the next (labeled) graph. If the latter is bigger than than the former, you have a new unlabeled graph. If not, throw it out.3) which is a very broad poorly worded description of what nauty does: http://cs.anu.edu.au/people/bdm/nauty/which has a method for doing exactly what you request, generating all unlabeled graphs. Harris(remove q to reply)=== === Subject: : Re: Graph Isomorphism 1) asymptotically, the number of labeled graphs has the same growth > rate as unlabeled (nonisomorphic w.r.t. node labeling). So If you are > generating -all- unlabeled graphs, it will take (rouhgly) as much time as > generating all labeled ones.Theoretically speaking, and for large n, yes this is true. But for relatively small vertex sets, the difference can be quite significant:vertices labeled graphs unlabeled graphs0 1 11 1 12 2 23 8 44 64 115 1024 346 32768 1567 2097125 10448 268435456 12346 And for the poster's example of 7 vertices, one thousand is quite small in comparison to two million. I forgot to mention in my last post that the geng program can also return all connected graphs as well as all those other properties I mentioned, and that's something I've found pretty useful in my work.J=== === Subject: : Re: Finite simple groupsOriginator: bergv@math.uiuc.edu (Maarten Bergvelt)>Does there exist a finite simple group G, for which the exact sequence>1 -> G -> Aut(G) -> Out(G) -> 1>is not split?Yes - A6 is the smallest such example, with |Out(G)| = 4.Aut(G) has a subgroup of index 2 often known as M_10, because it isthe point stabilizer in the Mathieu group M_11. The group M_10 has noinvolution outside of its derived group, which is A_6.More generally, G = PSL(2,p^2) has this property for any odd prime p.Derek Holt.===Originator: bergv@math.uiuc.edu (Maarten Bergvelt)****************** SUMMER SCHOOL ON IMPRECISE PROBABILITIES University of Lugano, Lugano, Switzerland******************ABSTRACTImprecise probability is a generic term for the many mathematical orstatistical models which measure chance or uncertainty without sharpnumerical probabilities. Imprecise probability models are needed ininference problems where the relevant information is scarce, vague orconflicting, and in decision problems where preferences may also beincomplete.The school on imprecise probabilities will offer a wide and deepintroduction to imprecise probability topics, both theoretical and applied.In particular, the school will focus on coherent lower previsions and theirbehavioral interpretation, decision theory, robust statistics, riskanalysis, imprecise probability methods for artificial intelligence andknowledge discovery.The school is organized by the Society for Imprecise Probability Theoriesand Applications (SIPTA).------------------------------------------------------ ------------INTENDED AUDIENCEThe school is mainly intended for advanced master or Ph.D. students,postdoctoral fellows, and junior researchers.-------------------------------------------------- ----------------The school is divided in 5 courses, one per day, of 8 hours each:July 27. Introduction to using imprecise probability in risk analysis. Scott Ferson (Applied Biomathematics, USA)July 28. Imprecise probability models and their behavioral interpretation. Gert de Cooman (Gent University, Belgium)July 29. Some decision theory with imprecise and indeterminate probabilityand utility. Teddy Seidenfeld (Carnegie Mellon University, USA)July 30. Independence, graphical models, knowledge discovery from data setsunder weak assumptions, applications to classification. Seraf?Moral (Granada University, Spain) & Marco Zaffalon (IDSIA,Switzerland)July 31. Robust Neyman Pearson theory & summary view on impreciseprobabilities. Augustin (Munich University, Germany)------------------------------------------------------ ------------REGISTRATION FEE AND DEADLINERegistration cost will be about 50 Swiss Francs (~39 USD, ~32 EUR),including lectures and coffee breaks.For all details please visit:-------------------------------------------------------- ----------LOCAL CONTACTMarco Zaffalon (school organizer)Senior ResearcherIDSIAGalleria 2CH-6928 Manno (Lugano)Switzerlandphone +41 91 610 8665fax +41 91 610 8661email mailto:zaffalon@idsia.chweb http://www.idsia.ch/~zaffalon=== === Subject: : Re: Cohomology of manifoldsOriginator: bergv@math.uiuc.edu (Maarten Bergvelt)I asked whether the following statement is true or false:For every paracompact connected n-dimensional manifold M which is not > compact, the nth singular cohomology group with integer coefficients, > H^n(M;Z), is trivial.David Farris replied:> It's in Spivak volume 1 (I think it's in the final chapter, which is on> the cohomology of manifolds). You do a big Mayer-Vietoris argument> involving a sequence of contractible neighborhoods that intersect their> neighbors in the sequence which eventually leaves every compact set.Now I have looked up Spivak's book. You probably meant Theorem 11 in Chapter 8, which says that H^n(M;R) is trivial. (Actually, the theorem deals with de Rham cohomology, but this is isomorphic to singular cohomology with R coefficients.)Unfortunately, that's not enough to answer my problem. In fact, that H^n(M;R) is trivial can also be seen by Boudewijn Moonen's argument: By the universal coefficient theorem, H^n(M;R) is isomorphic to the direct sum of Ext(H_{n-1}(M;Z),R) and Hom(H_n(M;Z),R). The latter is trivial since H_n(M;Z) = 0. And Ext(G,R) = 0 for every abelian group G because R is divisible.So my question still stands. I suspect that the statement is false, and that one can construct a counterexample M as the union of a suitable exhaustion by compact manifolds-with-boundary. But I might be wrong. Anyway, this is such a basic question that the answer should be known already!-- Marc Nardmann(To reply, remove every occurrence of a certain letter from my e-mail address.)=== === Subject: : Re: Cohomology of manifoldsOriginator: bergv@math.uiuc.edu (Maarten Bergvelt)> Yes, but unfortunately this solves the problem only if H_{n-1}(M;Z) is > finitely generated (which might not be the case). Then torsion-free > implies free, so the Ext group vanishes and we get H^n(M;Z) = 0.> The general case has to be more complicated. I'll check out the proof in > Spivak's book that David Farris pointed out.Unfortunately, this will give you only cohomology with *real* coefficients, since it uses de Rham cohomology. But maybe some kind of similar construction may give an exhaustion of M by an increasing sequence of open connected submanifolds of finite type, and then a limit argument may suffice.Boudewijn=== === Subject: : Re: Cohomology of manifoldsOriginator: bergv@math.uiuc.edu (Maarten Bergvelt)> But maybe some kind of> similar construction may give an exhaustion of M by an increasing> sequence of open connected submanifolds of finite type, and then a limit> argument may suffice.I think I have another argument now. (So forget my skepticism from another post on this thread.) I received an e-mail from someone whose > I dont know a reference but I believe that a manifold M of dimension n > with your conditions has the homotopy type of a CW complex of > dimension n-1.This is clearly highly relevant since it would imply that H^n(M;Z) = 0. Does anyone else here know a reference for this statement?Anyway, here's my own rough idea of a proof. I assume that the manifold M is a smooth or PL manifold. (Probably one could also handle arbitrary topological manifolds.)If we (smoothly or piecewise linearly) imbed a disjoint union of countably many rays (i.e. half-open intervals) w_i properly into M (properly means: preimages of compact sets are compact), then M is diffeomorphic to M minus the image of the rays.If M is noncompact and connected, we can find a triangulation of M and such a proper imbedding of countably many rays in such a way that for each n-simplex sigma, there is precisely one ray which meets sigma, and this ray either starts in sigma and then leaves it forever, or enters sigma precisely once and then leaves it forever.The complement of the rays can then be retracted to a subcomplex of the (n-1)-skeleton of the triangulation, and we are done.-- Marc Nardmann(To reply, remove every occurrence of a certain letter from my e-mail address.)=== === Subject: : Re: Cohomology of manifoldsOriginator: bergv@math.uiuc.edu (Maarten Bergvelt)>The general case has to be more complicated. I'll check out the proof in>Spivak's book that David Farris pointed out.> Unfortunately, this will give you only cohomology with *real*> coefficients, since it uses de Rham cohomology. But maybe some kind of> similar construction may give an exhaustion of M by an increasing> sequence of open connected submanifolds of finite type, and then a limit> argument may suffice.You might be right, but I have become skeptic in the meantime. The inverse limit of the cohomology groups H^n of the sequence members is in general smaller than the cohomology group H^n of M. The direct limit of the the groups H_{n-1} of the sequence members *is* H_{n-1} of M, but this doesn't seem to help. (Probably the only information about the direct limit of a countable system of finitely generated free abelian groups is that it is countable and torsion-free. For instance Q has this property, but Ext(Q,Z) is not trivial.) There are also some duality isomorphisms between singular H^n and the H_0 of certain other homology theories which I do not understand well enough to conclude that H_0 is trivial in the case under consideration.-- Marc Nardmann(To reply, remove every occurrence of a certain letter from my e-mail address.)