User talk:David Eppstein

From Wikipedia, the free encyclopedia

You have new messages (last change).

Hi, and welcome to my User Talk page! For new discussions, I prefer you add your comments at the very bottom and use a section heading (e.g., by using the "+" tab at the top of this page). I will respond on this page unless specifically requested otherwise.

Contents

[edit] Welcome

Hi there, and welcome to wikipedia! Its nice to see another anteater working on the project. As I see no one has officially welcomed you, I'll give you the official welcome message. Ready?


Welcome!

Hello, David Eppstein, and welcome to Wikipedia! Thank you for your contributions. I hope you like the place and decide to stay. Here are some pages that you might find helpful:

I hope you enjoy editing here and being a Wikipedian! Please sign your name on talk pages using four tildes (~~~~); this will automatically produce your name and the date. If you need help, check out Wikipedia:Questions, ask me on my talk page, or place {{helpme}} on your talk page and someone will show up shortly to answer your questions. Again, welcome! 

Wasn't that great? Anyway, if you need anything drop me a line! --best, kevin [kzollman][talk] 17:20, 22 August 2006 (UTC)

Thanks for the welcome, and thanks for the references – they look very helpful. I'm unsure of a point of etiquette, though: is responding here appropriate or am I expected to respond to user talk with a message back on your own page?
David Eppstein 17:58, 22 August 2006 (UTC)
Actually, there really isn't a generally accepted practice. I think the small majority does the later, responds on the other's talk page rather than their own. But a reasonable number of people do the former. Its really up to you. --best, kevin [kzollman][talk] 18:56, 22 August 2006 (UTC)
People do both, but the math people, I think, generally try to keep the discussion in one place, whether this be an article talk page, user talk page, or AFD discussion page. One common thing is to have a notice at the top of your talk page, stating what your preference is. That way people will know whether they need to watch your talk page or not. As an example, you can take a look at my talk page. --Chan-Ho (Talk) 03:34, 10 September 2006 (UTC)
Wikipedia is a maze of little twisting passages, all different. Hidden throughout are items both helpful and mysterious. One of these is the “+” tab at the top of this page. Clicking on it adds a new section with header at the bottom. Hovering over it should reveal a shortcut key. When editing, the row of tabs above the edit box contains one labelled with a scrawl. Clicking it inserts the automagical four tilde signature, preceeded by two dashes. Hovering should bring up a description of each button. Below the box are a large number of auto-insert characters, some of which are mathematical. For a larger repertoire, visit my user page, where you will find (among other things) a link to a table of many more mathematical characters to cut and paste. To see them all you will need suitable fonts, such as Code2000, or the eagerly-awaited STIX fonts.
Much as I hope Wikipedia turns out well, I think it only fair to warn you of hazards. The most serious of these for you may be that experts can find it rough going; see this critique, for example. However, the conversations at Wikipedia talk:WikiProject Mathematics are a cut above those on a typical talk page, at least for now.
If I can be of any help in matters political or procedural or technical, please don’t hesitate to ask. I’ve cited your Geometry Junkyard pages enough times elsewhere that it’s the least I can do in return. --KSmrqT 10:14, 14 September 2006 (UTC)

[edit] Redirecting Userpage

Redirecting your userpage to an article about you is highly frowned upon as it confuses people by blurring distinction between namespaces; it also makes it a tad harder for people to contact you. If you don't wish to write anything on your userpage, you can just create a link to the article. You may also want to add the template {{userpage}}.--Chan-Ho (Talk) 03:10, 2 September 2006 (UTC)

Ok, I'll unredirect and just leave a link instead. Thanks for letting me know.
David Eppstein 04:41, 2 September 2006 (UTC)

[edit] Incidence List

Hi, David. I referenced your site in Incidence list because I couldn't find any other ref; yet, in your Adjacency list edit summary you said "it's covered better elsewhere". Can you give me a pointer of where to look? (And a reference in the Adjacency List page would be great.) I'm kind of frustrated by the amout of publications describing "incidence lists" when they are really describing adjacency lists. (Just reply here.) — LazyEditor (talk|contribs) 06:41, 9 September 2006 (UTC)

CLRS (the main cite in Adjacency List) only does the adjacency list itself (making its coverage of flow algorithms problematic) but other algorithms texts do the incidence list version, I think. The one I use for my classes is Goodrich&Tamassia, and though they obscure it with a lot of object-orientation details I'm pretty sure the graph representation they use is essentially the same as the incidence list. I'd want to double check that before adding it as a reference here, though. —David Eppstein 06:49, 9 September 2006 (UTC)
I changed my mind, and added the reference back — my reasoning being that, whether or not I like Goodrich&Tamassia better, my lecture notes are online and their book isn't. I also added some other references, so I'd be interested in hearing whether you think it's better now. —David Eppstein 07:17, 11 September 2006 (UTC)

Thanks, it looks fine to me. I'm just a bit not sure about the definition. What if I have only one of these data structures:

  • struct { LinkedList<int> incidentEdges; } *vertices;
  • struct { int v1; int v2; } *edges;

Is it not an incidence list?

Oh, and a little nit: "One difficulty with the adjacency list structure is that it has no obvious place to store data associated with the edges of a graph". What about simply storing it in each node of the linked lists? — LazyEditor (talk|contribs) 18:14, 11 September 2006 (UTC)

I'm not sure whether to call that an incidence list, but it's a lot less useful to have only one half of the vertex-edge incidence relation. The second half (where you have an array of edge objects but no list of incident edges for each vertex) is essentially what's defined as the mathematical version of the adjacency list at the start of the entry, but then you have to scan the whole structure if you want to find the neighbors of some vertex. And the first half only is even more cumbersome as to find the identity of each neighbor of each vertex you have to scan all other vertices to see which ones link to the same edges.
Re the nit: if it's a directed graph, and you're storing the adjacency list using a linked list as in CLRS (rather than an array as in van Rossum) this works, but then the linked list elements are essentially edge objects so it's just a disguised form of incidence list. If it's an undirected graph it's more problematic because there are two linked list elements per edge and it's not obvious which one to use to store the information.
—David Eppstein 18:22, 11 September 2006 (UTC)

Okay, thanks. That seems to explain my encounters with incidence lists which I thought were adjacency lists. — LazyEditor (talk|contribs) 18:02, 14 September 2006 (UTC)

[edit] Wikipedia:WikiProject Mathematics

I neglected to mention before that there is an active group on Wikipedia dedicated to improving its mathematics coverage. You may want to add your name to the list of participants: Wikipedia:WikiProject_Mathematics/Participants. There is really no obligation to do this. But this is a way for someone to locate people who can offer their expertise on the different areas, and it also has the benefit of showing the rest of Wikipedia (and the world) that the WikiProject is active and growing.

Additionally, you may eventually find out that you may need help or have concerns about something, in which case Wikipedia_talk:WikiProject_Mathematics is a good place to voice these concerns. Some project members also keep this page updated (with the help of bots): Wikipedia:WikiProject_Mathematics/Current_activity. --Chan-Ho (Talk) 03:27, 10 September 2006 (UTC)

Thanks. I don't promise to check back on those pages regularly, but I did add myself. —David Eppstein 18:10, 10 September 2006 (UTC)

[edit] Welcome to WikiProject CS

Hi! Just noticed that you have signed on as a participant in WikiProject Computer science, and wanted to welcome you to the project. Please stop by the project talk page to see what the other participants have on their minds right now, and to add your own thoughts. --Allan McInnes (talk) 20:28, 14 September 2006 (UTC)

[edit] License tagging for Image:Turan-13-4.png

Thanks for uploading Image:Turan-13-4.png. Wikipedia gets thousands of images uploaded every day, and in order to verify that the images can be legally used on Wikipedia, the source and copyright status must be indicated. Images need to have an image tag applied to the image description page indicating the copyright status of the image. This uniform and easy-to-understand method of indicating the license status allows potential re-users of the images to know what they are allowed to do with the images.

For more information on using images, see the following pages:

This is an automated notice by OrphanBot. If you need help on selecting a tag to use, or in adding the tag to the image description, feel free to post a message at Wikipedia:Media copyright questions. 06:07, 2 October 2006 (UTC)

[edit] I agree with your view of math

"my view of math as a highly interlinked non-hierarchical graph of connections."

Hi, I agree with your view and was going to post something about graphs but decided not to after getting no reaction to my comments re file browsers.

I'm not a computer scientist, so I will put this as a fuzzy question:
If knowledge is represented as a graph,
what information would be needed at each node and edge to find a subgraph that is a tree (and therefore a hierarchy)?

BTW, I said "promising" as a way to promote further exploration.

--Jtir 21:48, 9 October 2006 (UTC)

Finding trees in graphs is easy: see spanning tree. But unless there's some information in the graph about directionality (is one concept a special case of another, or a generalization) and strength of connection, the trees you get won't necessarily correspond to any kind of logical hierarchy. For more on graph- and tree-based representation of knowledge, you might look at knowledge representation, ontology (computer science), and taxonomy. —David Eppstein 22:05, 9 October 2006 (UTC)
Thanks for the links. WP has a way to go to catch up with CS research. :-) --Jtir 22:22, 10 October 2006 (UTC)
Cyclic order
Enlarge
Cyclic order
Anyone writing a textbook encounters the dependency ordering problem. Ideally one finds a linear ordering, so that it is never necessary to draw on results not yet presented. In practice, topics don't naturally allow such a convenient sort. Some strategies that are adopted for that kind of writing may be of limited help in an encyclopedia. However, one possibility is to split a topic into basic and advanced discussions. Thus A ↔ B becomes A1 → B → A2. This is a fair approximation of how we learn, revisiting a topic as necessary for more advanced study. An example is integration in first-year calculus versus measure theory later. A more interesting case is foundations, where first we ignore the issue, then learn about classical logic and set theory, and later intuitionistic logic, and then perhaps topos theory. Bourbaki established a disastrous precedent for teaching by trying to start with the most general, least restricted concepts then narrowing, where historical discovery and effective learning work in the opposite direction.
Anyway, as David points out, hierarchy implies ordering, an ordered graph (directed graph) can include cycles, and cycles are incompatible with hierarchy (or linear ordering). --KSmrqT 04:58, 10 October 2006 (UTC)
I was referring specifically to trees, but your mention of cycles got me wondering if there is any example of knowledge that is represented by cycles — I can think of several: life cycles of organisms; morning, noon, and night; seasons; biochemical cycles. There is even a WP page called Cycle which lists these and others. --Jtir 22:22, 10 October 2006 (UTC)
That actually relates closely to an article I've been thinking of working on here, Antimatroid (currently merged with Greedoid but I think it has enough material to be a standalone). Antimatroids are usually axiomatized either as set systems or formal languages, but they can also be thought of as a kind of ordering of a system of elements, generalizing partial orders (both imply a set of possible linear orders but an antimatroid can represent a broader family of such sets). There's a local electronic learning company that's had some success in using such models to describe the connections between topics in elementary through secondary school mathematics... —David Eppstein 06:27, 10 October 2006 (UTC)

[edit] Dashes

Yes, that was an error on my part. Although, you'll notice that half of the conjectures listed on Erdős conjecture use hyphens instead of dashes. Yill577 22:01, 19 October 2006 (UTC)

Actually, quoting from Wikipedia's manual of style, "If hyphens and dashes are needed to write a page name correctly (e.g., Piano-Rag-Music, Jack-in-the-box, Nineteen Eighty-Four), prefer simple hyphens, and avoid hair spaces, even in the odd case of a range forming part of the title, e.g., History of the Soviet Union (1985-1991)." (Emphasis added.) That would seem to suggest the hyphen is in fact correct, not the dash. And in any case, my move was to add an acute accent to Paul Turán's name, not to change from dash to hyphen. Yill577 22:16, 19 October 2006 (UTC)

[edit] Replacing "\equiv" with "="

Hi David! Thanks a lot for helping on Wikipedia talk:WikiProject Mathematics/equivlist! I have one concern, though: Many people said that "it is particularly important for WP to highlight definitions on pages" and express this verbatim. From looking at some of your edits, it seems you are merely replacing "\equiv" with "=". In my edits, I always spent some thought about how to make it clear that the equations are definitions. Are you doing the same? — Sebastian (talk) 20:03, 24 October 2006 (UTC)

I was certainly looking at whether the text talked about defining notation versus stating equalities for existing notation. But perhaps I have different standards than you for how explicitly one should say "we define x to be..." versus "letting x = ..." etc. —David Eppstein 20:36, 24 October 2006 (UTC)
P.S. there was one page, Implementation of mathematics in set theory, where it may appear that my edits are a straight search and replace job. In that case, all the equivalence (and now equals) signs had a subscript "def", so I felt that the definitional nature of the notation was clear without any additional text. —David Eppstein 20:49, 24 October 2006 (UTC)
I see - thanks. Yes, our standards may be different; but this is only a secondary issue. My main interest was to eliminate the ambiguity between the different uses of "\equiv". I sincerely hope I did not discourage you from continuing this endeavour. — Sebastian (talk) 22:36, 24 October 2006 (UTC)

[edit] photo

Hi. Who is the copyright owner of spim.jpg, delicious.jpg, and limelena.jpg? If it's you, can I use all or any of them (specify which, I think I mostly want delicious.jpg) under GFDL 1.2 or any later version published by FSF? NerdyNSK 17:33, 5 November 2006 (UTC)

I took spim myself, delicious is by my father, and limelena is by Elena Mumford. I can send an email to my father asking whether he's willing to allow that use of the photo, if that's the one you prefer. Would "the copyright holder gave me permission to use this work in Wikipedia articles" be sufficient permission, or do you really need it to be more generally free? The former seems more likely to be granted. —David Eppstein 18:17, 5 November 2006 (UTC)
I wish to use a pic for the infobox I added to your Wikipedia entry. I prefer GFDL for philosophical reasons, but in practice any license will do (it would be good the licence to allow resizing). What permission terms can you give for spim.jpg (GFDL, CCL, only for Wikipedia, ...) ? NerdyNSK 18:51, 5 November 2006 (UTC)
Would CC attribution sharealike work for you? I could upload spim with that, or discuss the possibility of something like that for delicious. The other issue is what resolution would you want? I have spim at 2k x 3k, as a high quality jpg, but it's a 2Mb file. If I remember correctly delicious was cropped from something larger, though, so I'm not sure I have better than the 320x400 easily available on that one.
BTW, on a somewhat related subject, if you think my hobbies are really notable enough to include in the entry, you might consider my photography, e.g. on flickr.
—David Eppstein 19:19, 5 November 2006 (UTC)
PS another possibility: more of a formal portrait. This is from a set of portraits the school commissioned in 2003, I believe on a work-for-hire basis, so the copyright holder would be the university; I can inquire whether there's any issue with allowing it to be used here but I don't expect there to be. —David Eppstein 19:38, 5 November 2006 (UTC)
I think the portrait is perfect for inclusion in Wikipedia. Please ask the copyright owner whether we could have it under GFDL or another licence suitable for the encyclopedia (I believe even fair use would be ok). In the meantime, if you want you could upload spim with any licence you want (CC sharealike sounds great, and I recommend dual-licensing with GFDL too if you like), at a good resolution, but I think it shouldn't be more than 500KB in jpeg format (in fact one can get good quality even with 200K). NerdyNSK 20:55, 5 November 2006 (UTC)
Ok, the image is now uploaded at full resolution (roughly 800x1000 in this case) at Image:Eppstein-UC03.jpg. Our communications office tells me they are hoping to commission a set of new photos to be licenced under Creative Commons, but for now it seems we need more restrictive conditions for this one. —David Eppstein 23:43, 5 November 2006 (UTC)
It looks good, thanks. Note that free images are better suited for Wikipedia, though. Do you know other professors/scientists who contribute in Wikipedia? NerdyNSK 20:52, 6 November 2006 (UTC)
You mean other than the ones listed in Category:Notable_Wikipedians and Wikipedia:Wikipedians with articles? I don't see User:McKay on either list, probably there are plenty of others missing from there as well. —David Eppstein 21:28, 6 November 2006 (UTC)

[edit] Probability-based strategy AfD

Just a note to let you know that I have nominated the article you have edited, or expressed interest in, for deletion. See Wikipedia:Articles for deletion/Probability-based strategy Pete.Hurd 05:29, 7 November 2006 (UTC)

[edit] Egyptian mathematics, especially the hekat

Hi David,

I see that you have removed the 1/320th discussion with the comment that it confuses the hekat topic. Well, let me stress that Ahmes and all other ancient scribes used ro = 1/320th as a hekat scaling factor in the remainder term whenever a divisor less than 64 was required to be used. I'd be happy to send by private email Hana Vymazalova's 2002 paper, one that corrects George Daressy's 1906 Akhmim Wooden Tablet paper (that indirectly corrects Peet's 1923 paper on the subject) that defines the turf in the ro arena. It is cited on the Egyptian math section of Wikipedia, so you should have no trouble in looking it up, if you choose not to request a copy.

Best Regards, Milo Gardner

Hi Milo. If you do have a copy, please email it to me — I suspect that would be easier than looking it up. Would a sentence like "For fractions of a hekat not expressible in multiples of 1/64, the Egyptians used the Horus Eye notation for as large a part of the fraction as possible, and then used their more general Egyptian fraction notation to express the remainder as a multiple of a ro, a unit equal to 1/320 of a hekat" be acceptable in this context? The point was that that paragraph is talking about the Horus Eye notation, so to suddenly switch to the other notation in the middle of the paragraph requires an explanation of how the switch relates to the subject of the paragraph. —David Eppstein 16:19, 7 November 2006 (UTC)

Hi David,

Thank you for the discussion. I'll be sending Hana's 2002 paper along with Daressy's 1906 paper, and even Peet's 1923 paper, if you desire. May I use your UCI email address?

Concerning Horus-Eye notation, it was introduced in Wikipedia's paragarph in terms of hekat sub-divisions. Hence to complete the hekat topic, as the ancient scribes wrote the subject, the rounded off data associated with Horus-Eye divisions, say by divisor three, where the remainder is one, the ro scaling factor 1/320 equals ro is required to be mentioned. Best Regards, Milo Gardner


Hi David,

Please excuse my implication that ancient Egyptian algebra was written exactly as modern algebra is written. Of course there is a major difference. Egyptians wrote unit fractions as a final notaitonal step. Today unit fraction memories from the Middle Ages, Greece and Egypt have been virtually erased from our memory. Hence scholars have poorly reported the unified aspects of Egyptian fraction arithmetic, a notation of writing rational numbers in short and concise unit fraction series, that lasted for about 3,600 years. To understand the final step in the ancient Egyptian algebra, the major diffference between today and yesterday, the RMP 2/nth table must be understood, via the Hultsch-Bruins 2/p method, and by another 2/pq method that was published in India in 2002 by myself. More on the H-B and 2/pq method, if you so desire. Best Regards, Milo Gardner

If you want to write more about it, please put it in the Egyptian mathematics or Egyptian numerals article. I want the main Egyptian fractions article to be only a short summary of each possible topic, with pointers to longer articles where more detail can be found. Egyptian mathematics has been marked as needing some revision, but I have no plans to work on it myself. —David Eppstein 16:04, 10 November 2006 (UTC)


Hi David,

I'd be happy to define ancient Egyptian fractions as you have define the modern algorithm form of Egyptian fractions. Given 80 years of mis-information on the ancient arithmetic it will be difficult to keep the discussion short, as you have requested. As a suggestion, I'd simply show how and why Egyptian arithmetic was the parent of Greek arithmetic. In that way, if there is not too much argument, I'll conclude that both Greek and Egyptian arithmetic used Egyptian fractions on the same abstract level, using minimal examples for addition, substraction, multiplication and division. Best Regards, Milo.

I have no problem with going into the subject at length. I just don't think the main Egyptian fraction article is the place for it. E.g., Znám's problem and Erdős–Graham conjecture are about Egyptian fractions, but both are separate articles and the description of them in the main article is very short and omits many important details about them. Anything significant lengthening of the sections of the Egyptian fraction article would unbalance the article and make it difficult to find the material in the other sections. So more details, example calculations, connections to other topics in mathematics, history of correct and incorrect analysis of the tablets and papyri by historians of mathematics, etc., are all good things to write about but not in Egyptian fraction, in the linked article instead. —David Eppstein 16:05, 15 November 2006 (UTC)

Hi David, The citation of Wolfram's web page where a short series of my summarized papers on the EMLR, and AWT appear is grossly incomplete. The main Wolfram author (Eric W.) of the Egyptian fraction subject, the author of the encyclopedia, stresses the modern aspects of the subject. This is a common position that you seem to take. I continue to work towards connecting the modern to the ancient, as medievals and Greeks knew the subject (of proto-number theory), as well as working in the reverse direction, connecting the ancient to the modern. Wolfram, Erik W. and modern number theorists often gets lost in the myopia of modern algorithmic trees. The ancient forest of proto-number and its use of prime numbers still grow algebraic identities like 2/pq = 2/A xA/pq, with A = (p + 1), as used 20 times in the RMP (a method that Brown missed) as do certain trees growing in our Sierra Mountains that took root in 4,000 BCE (awkward analogy?.). Best Regards, Milo Gardner

Concerning your 12/12/06 re-entry of a modern 'best' series, I see no justification for it, other than your 'sense' of the subject. Is Wikipedia not a discussion area that requires proof - by a previous academic source? Best Regards, Milo Gardner 12/12/06.

It requires proof for statements not supported directly by the texts. The Egyptians' missing the simplification 1/370+1/560=1/228 is a fact,

verifiable directly from translations of the RMP. Any speculation about why they missed it would require external citations to avoid being original research. But I don't think I included anything speculative. And I think including the fact itself is relevant as a counter to bizarre claims that the mystic wisdom of the ancients surpassed anything modern mathematics can do. —David Eppstein 17:19, 12 December 2006 (UTC)

[edit] "sentence no verb"

This sentence has no.Rich 05:24, 20 November 2006 (UTC)

[edit] Follow-up on new Template:MathSciNet

Hi David. I note that you only hope to provide MR numbers for those papers that actually have an MR abstract. Do you have an opinion on the value of those abstracts for more recent papers? I know that in the old days, people often didn't write abstracts (like the Alaoglu papers that have no abstract). For the recent papers that DO have an MR abstract, I often notice that it's no better than the one that comes with the paper. (There are amazing exceptions here and there). I'm guessing that perhaps papers that are *very* new (new enough to have a DOI, for example) may have less need of an MR abstract. I'm interested in how we could upgrade the referencing in the math articles generally, and so I'm taking advantage of your MathSciNet discussion to see what you think could be usefully done. EdJohnston 20:47, 2 December 2006 (UTC)

Answered over on WT:WPM#New MathSciNet template. —David Eppstein 20:57, 2 December 2006 (UTC)

[edit] Fictional curvature tensors

That was just a joke. On my last trip to France, I was eating at a restaurant, when I overheard some people from another table speaking English, and not only that, they were talking about math. Something about curvature tensors, Siegel disks, Johnson zeroes, left/right topologies, all kinds of very advanced stuff. But when the check came and there was some disagreement about what to tip the garcon, they were all at a complete loss about basic arithmetic! PrimeFan 18:45, 6 December 2006 (UTC)

[edit] Congratulations

And while I'm here, I wish to extend my congratulations for getting the article on Sylvester's sequence acknowledged as a good article. I think it is mainly because of your fine work on it these last few months that the nomination was accepted. The jury is still out on Znam's problem, but I'm sure that one will pass too. PrimeFan 18:48, 6 December 2006 (UTC)

Thanks! —David Eppstein 19:06, 6 December 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../d/a/v/User_talk%7EDavid_Eppstein_f8b2.html"