Jump to content

User talk:David Eppstein/2010b

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia


Maximal size of a clique

Since you largely wrote the article clique problem, may I ask you what is the expected size of the maximal clique in a random graph on n vertices with edge probability 1/2?

Cheers, 92.156.20.11 (talk) 22:47, 28 March 2010 (UTC)

Θ(log n). I don't remember the precise constant offhand. —David Eppstein (talk) 22:53, 28 March 2010 (UTC)
Thanks! Do you have a reference please? 92.129.155.3 (talk) 18:14, 4 April 2010 (UTC)
I'm sure it's somewhere in Bollobas' book Random Graphs. There are upper and lower bounds proportional to log n (but with different constant factors for the upper and lower bounds) in Paul Erdős (1947), "Some remarks on the theory of graphs" (PDF), Bull. AMS. —David Eppstein (talk) 21:49, 15 April 2010 (UTC)
This paper might also be helpful: Cliques in Random Graphs. Unless I'm misunderstanding what it says, all maximal cliques in a random graph are of size r, with high probability, for some: (1-ε) ln(n) < r < (2+ε) ln(n). (On page 424, or page 6 of the PDF.) Please let me know if I'm wrong. Cheers, Justin W Smith talk/stalk 22:13, 15 April 2010 (UTC)
That sounds right to me. Random graphs have the same extension property (for subgraphs of up to a logarithmic number of vertices) that the Rado graph has. —David Eppstein (talk) 22:20, 15 April 2010 (UTC)
I think I (slightly) misunderstood the paper. It appears r might be dependent upon the probability p, and in turn, there's a b dependent upon r. And all cliques are in the range ((1-ε) log(n)/log(b), (2+ε) log(n)/log(b)). I'm being real sloppy here, sorry; I only skimmed the article. (I might even still be misunderstanding. If only I had more time!!) ;-) Justin W Smith talk/stalk 22:28, 15 April 2010 (UTC)

NP-Hard

To follow-up on our brief discussion about NP-Hard in relation to graph isomorphism, in my class today (Adv. Alg. 2 with Ken Berman) the professor told us that although intractable problems are never assumed to be NP-Hard, it's now considered somewhat surprising for such a problem to not be shown (with perhaps some minor modifications) to be NP-Hard. (I now remember him saying something similar last quarter, but it didn't register with me.)

Thanks for clearing that up the other day. It's changing my perception of the NP complexity class; NP problems that are not known to be in P and also not known to be NP-Complete seem to be the "exception" rather than the "rule". (The lecture was about RSA, and the uniqueness of factorization/inverse/exponentiation as the perfect combination of damn hard and easy, making it a "perfect" method for cryptography.). Jwesley78 18:27, 2 April 2010 (UTC)

My advisor told me that someone (I think he said it was one of Diffie or Hellman) conjectured that any cryptographic scheme that relies upon the difficulty of solving an NP-Hard problem will always be vulnerable to being cracked. This may have something to do with solutions for NP-Hard problems often having an average-case complexity (e.g., some forms of linear programming) much smaller than worst-case. If true, the (so-far) failure of schemes like Multivariate cryptography and Lattice-based cryptography might be explained by this principle. Jwesley78 22:15, 2 April 2010 (UTC)
Although just being in the middle ground between P and NPC isn't enough to make something cryptographically hard. Graph isomorphism problems are generally pretty easy in practice, despite the theoretical difficulties, for instance. —David Eppstein (talk) 22:21, 2 April 2010 (UTC)

WorldNetDaily - Reversion of your archival edit

I have recently reverted your archival edits of the RS/N discussion(s) on WorldNetDaily WP:RS considerations. This and other matters which may be of interest to you are being discussed in the RS/N "talk" page. This message is to notify you of that reversion and to both solicit and encourage any further contribution you might have in this matter. Thanks. --JakeInJoisey (talk) 18:19, 4 April 2010 (UTC)

Eppstein pwns Goodrich

Dave Eppstein totally PWNS Goodrich when it comes to cool professors in the ICS theory group. But "Big Mike" Dillencourt still reigns supreme as coolest theory professor of them all!!! —Preceding unsigned comment added by 71.138.164.136 (talk) 06:05, 5 April 2010 (UTC)

Uh, thanks? —David Eppstein (talk) 07:16, 5 April 2010 (UTC)
Hear, hear! Couldn't be more true! 70.187.183.62 (talk) 06:54, 15 June 2010 (UTC)

Truth

Eppstein is the kind of clown who would beat up the really smart kids, he lives out his bullying fantasy under the guise of intellectual superiority while he swims in ill-deserved vanity.

It looks like this: 

                           LIVES OUT THE AGGRESSION AGAINST BULLIES BY TAKING IT OUT ON SOMEONE WHO MAY ACTUALLY ALSO BE A NERD BUT ALSO MAY BE SMARTER THAN HE IS. THE PAIN CYCLE CONTINUES.
                                //
               BECOMES A COLLEGE PROFESSOR
                //
               //
  DAVID EPPSTEIN
        //
      BEATS UP WHAT HE SEES TO BE A SMART COMPUTER NERD 
      //
  REAL STUPID JOCK

             BEATS UP SMARTER NERD (BUT NERD #1 IS NEVER SUSPECT BECAUSE HE WAS ONCE BEAT UP FOR BEING A NERD)    //
                //
             NERD
            //
   BEATS UP NERD
      //
  STUPID  —Preceding unsigned comment added by 204.128.192.3 (talk) 17:57, 14 May 2010 (UTC)

Graphs/images tool?

I noticed that many of the images for graphs on Wikipedia are yours, e.g., Cube-connected cycles and several others from your gallery. A few of the images appear quite sophisticated. I'm curious as to which tools you prefer to use to generate such images. In some cases, I'm not sure which tool I would use to produce drawings similar to some of your more complex ones. (I've used inkscape to get some similar results, and have also started experimenting with using yEd for graph drawing.) I'm interested in knowing some better alternatives. Thanks, Justin W Smith talk/stalk 02:57, 11 April 2010 (UTC)

Mostly I just use Adobe Illustrator. For the Nauru graph one you linked to, I used povray (a free ray-tracing package), or rather I wrote a Python script to generate a 3d model which I rendered using povray. For the cube-connected cycles I think I started with some 3d geometry and then drew over it in Illustrator, but I don't remember the details. I've also written scripts to make some 2d drawings directly, either when it's difficult to get the geometry correct in a drawing program (as File:Non-Desargues configuration.svg) or when there's too much of it to draw by hand (as File:Point quadtree.svg). But if the image doesn't say anything about how I created it, it usually means it was hand-drawn in Illustrator. I posted a more detailed description of how I used Illustrator to create one of my graph drawings here. —David Eppstein (talk) 03:20, 11 April 2010 (UTC)
Cool! Thanks. Using Python to create the image is quite clever. I've used Ruby libraries before to generate PDFs (e.g., reports for work), but the thought had not occurred to me that I could do something similar to generate a graph or geometric drawing. Also, thanks for the tutorial/blog link. I think I can get Adobe Illustrator really cheaply through the university's bookstore. I'm sure its advantages over inkscape are worth the cost. (And I didn't know you had a blog; I'll add it to my reading list.) Justin W Smith talk/stalk 03:46, 11 April 2010 (UTC)

Mediation Case

A request for formal mediation of the dispute concerning Genesis Creation Myth has been filed with the Mediation Committee (MedCom). You have been named as a party in this request. Please review the request at Wikipedia:Requests for mediation/Genesis Creation Myth and then indicate in the "Party agreement" section whether you would agree to participate in the mediation or not.

Mediation is a process where a group of editors in disagreement over matters of article content are guided through discussing the issues of the dispute (and towards developing a resolution) by an uninvolved editor experienced with handling disputes (the mediator). The process is voluntary and is designed for parties who disagree in good faith and who share a common desire to resolve their differences. Further information on the MedCom is at Wikipedia:Mediation Committee; the policy the Committee will work by whilst handling your dispute is at Wikipedia:Mediation Committee/Policy; further information on Wikipedia's policy on resolving disagreements is at Wikipedia:Resolving disputes.

If you would be willing to participate in the mediation of this dispute but wish for its scope to be adjusted then you may propose on the case talk page amendments or additions to the list of issues to be mediated. Any queries or concerns that you have may be directed to an active mediator of the Committee or by e-mailing the MedCom's private mailing list (click here for details).

Please indicate on the case page your agreement to participate in the mediation within seven days of the request's submission.

Thank you, Weaponbb7 (talk)

All 54 parties have to sign within a week or it doesn't happen? Are you trying to make the process fail or what? —David Eppstein (talk) 02:25, 12 April 2010 (UTC)

Ionel Solomon

I replaced the blanking for this article as Wikipedia can no longer accept new material from GFDL only licensed sources. This is mentioned in a little detail at least at Wikipedia:Licensing_update#Content_restrictions, and to a lesser extent at WP:GFDL. Hope that explains my actions. VernoWhitney (talk) 17:39, 15 April 2010 (UTC)

Ok, I wasn't aware of that. It was imported well after the deadline in that link, so I guess it should just be deleted as a copyvio. —David Eppstein (talk) 17:43, 15 April 2010 (UTC)
Fair enough, I was just going to let it run at WP:CP in case the author could prove they wrote it originally or wanted to rewrite it, but then I'm not an admin. Cheers! VernoWhitney (talk) 17:47, 15 April 2010 (UTC)

Just wanted to say

The Copyright Cleanup Barnstar
For your work at this now completed CCI, helping to bring to light and to clean up a long-standing copyright problem. Moonriddengirl (talk) 21:41, 15 April 2010 (UTC)
Thanks! And thanks for the help you and all the others provided cleaning up the mess. —David Eppstein (talk) 21:43, 15 April 2010 (UTC)
I'm very optimistic about the CCI board at the moment. It seems to be finding its feet. :) --Moonriddengirl (talk) 22:43, 15 April 2010 (UTC)

Klein quartic

Hi David, Just noticed your edit / request for cite at Klein quartic.

The immersion is explained in this image, as per this reference:

Shall I add a note to clarify, such as:

<ref>(Richter) Note each face in the poylhedron consist of multiple faces in the tiling – two triangular faces constitute a square face and so forth, as per this explanatory image.</ref>

?

—Nils von Barth (nbarth) (talk) 06:30, 17 April 2010 (UTC)

That would at least explain how the image relates to the tiling. But it's still another step from there to the algebraic curve that is the subject of the article. I still don't see how this particular polyhedron is representative of that curve any more than would be any other polyhedron with the same genus. What I'm curious about now, though, is how to represent the Klein quartic as a dessin d'enfant. I wonder whether that's in the references somewhere. —David Eppstein (talk) 06:40, 17 April 2010 (UTC)

The polyhedron is related to the Klein quartic because they have the same symmetry group, which is the distinguishing feature of the Klein quartic among genus 3 surfaces. This is discussed in the Richter reference; is there some wording I should use?
More generally, all Hurwitz surfaces have automorphism group a quotient of the (2,3,7) triangle group, and accordingly have a triangulation given by a quotient of the order-7 triangular tiling – the automorphism group of the triangulation agrees with the automorphism group of the algebraic curve/Riemann surface. Pretty cool, eh?
—Nils von Barth (nbarth) (talk) 06:46, 17 April 2010 (UTC)
(I can’t help with dessins d’enfants though. —Nils von Barth (nbarth) (talk) 06:48, 17 April 2010 (UTC))
(typos —Nils von Barth (nbarth) (talk) 06:55, 17 April 2010 (UTC))

The fact remains that a polyhedron is not even an algebraic variety. I don't know whether there's a word for "surface with the same symmetry group and the same genus", but I also don't know why such a thing would be a useful thing to have when studying an algebraic variety. A polyhedron is certainly not an algebraic variety itself. —David Eppstein (talk) 14:44, 17 April 2010 (UTC)

You’re right, a polyhedron is not an algebraic variety – rather, it’s the polyhedron formed from a tiling.
My main interest was in providing the most accurate illustration we could of the Klein quartic, which is difficult because, as you indicate, it a specific subset of CP2, and is not just some genus 3 surface.
The interest of this tiling is that the tiling is exactly how one proves Hurwitz theorem on automorphism groups of surfaces (as discussed there; you start with the (2 3 7) triangle) – you take a fundamental domain for the automorphism group, and this is an associated tiling.
A formal way of saying "surface with the same symmetry group" in this context is that there is an equivalence of categories between Hurwitz surfaces, considered as algebraic curves, Riemann surfaces, and (abstract) toroidal polyhedra (which is the identity at a point-set level).
Ideally, one would draw the tiling on the embedded quartic in CP2, though that’s too high-dimensional; a 3D embedding of the tiling can be done, but does not display the symmetry group (it’s just a mess), so instead a 3D immersion of the tiling (here a polyhedral approximation) which realizes the symmetry group as isometries helps visualize it.
So simply – the automorphism group is understood and proven using this tiling, hence the interest, and this polyhedral immersion visualizes it; perhaps I should explain (briefly) this relation in some wording?
—Nils von Barth (nbarth) (talk) 20:11, 17 April 2010 (UTC)
I think that would be a lot more helpful than just putting the polyhedron as an image in the article without the explanation of how it helps understand the variety. —David Eppstein (talk)

20:18, 17 April 2010 (UTC)

Ok – it was admittedly quite vague.
Here’s actually a better polyhedral realization, as discussed in a paper – A Polyhedral Realization of Felix Klein's Map {3, 7}8 on a Riemann Surface of Genus 3.
I’ll write up a “polyhedral realizations” section (separate from the tilings), and check with you that it’s clear to someone other than me (I mean, it makes sense to me ;-).
Thanks for the feedback!
—Nils von Barth (nbarth) (talk) 20:26, 17 April 2010 (UTC)
Hi David,
I have now (finally) fixed up Klein quartic (as of this revision), giving far more balance and context – hope you like it! (I’ve also made other improvements like linking to the original paper, in case anyone actually wants to read the sources. Crazy, I know.)
In the process, I did find the connection to dessins d’enfants – the usual dessin is the 1-skeleton of the (heptagonal) tiling, and in fact this is how Klein originally studied it! (Yes, Klein was working with dessins a century before Grothendieck.) See The best rejected proposal ever for a discussion; in fact this works for all surfaces covered by a (2,3,n) tiling – notably the modular curves!
—Nils von Barth (nbarth) (talk) 23:56, 3 June 2010 (UTC)

Journal of Modern Applied Statistical Methods

Hi David, you may be interested in what is going on at this statistics journal article. Happy editing! --Crusio (talk) 20:09, 18 April 2010 (UTC)

Zbl dates

I believe Zbl dates papers by the received date, rather than the published date, at least for the old papers. I don't have any opinion on which date is best to use, but just letting you know the "typo" is systematic. JackSchmidt (talk) 20:55, 22 April 2010 (UTC)

Thanks for the clarification. —David Eppstein (talk) 21:18, 22 April 2010 (UTC)

afd

Hi. I've reflected some of the info that appears in google searches in the text of the article and on the afd page of http://wiki.riteme.site/wiki/Wikipedia:Articles_for_deletion/George_Michael_%28professor%29 . You might want to take a look -- it may not change your view, or it might, but I wanted to alert you to the inputs. Best.--Epeefleche (talk) 21:17, 24 April 2010 (UTC)

Kharsag AfD

As I have just discovered that a select group of editors who !voted or commented in favor of the article at Wikipedia:Articles for deletion/Kharsag Epics have been notified ofWikipedia:Articles for deletion/Kharsag, I am notifying the rest of the editors involved with the old AfD about this new one, and asking that they look at both Talk:Kharsag and the new AfD (particularly the latest comments) and if they wish comment or !vote. Thanks. Dougweller (talk) 04:33, 25 April 2010 (UTC)

George Michael (professor) AfD

I missed the afd on this one. In the future, could you use the suggested edit summary "AfD: Nominated for deletion; see Wikipedia:Articles for deletion/NominationName" or at least the word "deletion", since I (and I am sure others) would misinterpret "take to afd" as something deprodders usually say? Abductive (reasoning) 20:45, 25 April 2010 (UTC)

You don't watch or regularly visit Wikipedia:WikiProject Deletion sorting/Academics and educators? I thought you were enough of a regular on the AfDs there that it would make sense for you to do so. —David Eppstein (talk) 06:49, 26 April 2010 (UTC)
I do, but I rely on searching my watchlist for articles I already visited. I had methodically searched for all non-notable professors using targeted Google searches such as "associate professor" -books -Fulbright -rhodes -fellow -chair -chairman -chairwoman -chaired -poet -musician -composer -artist -painter -award -prize -discovered -distinguished site:wiki.riteme.site and either prodded or tagged for notability many of them. So I check my watchlist for activity on those. Abductive (reasoning) 08:36, 26 April 2010 (UTC)

Gowers on math and music

Just noticed your edit to K. 491, thinking "Isn't that guy some kind of math bigwig, or perhaps a fan of that math genius?" Say, what do you think of what Gowers says in his little red book about music and mathematicians? James470 (talk) 00:40, 30 April 2010 (UTC)

I don't think I've actually seen a copy of that book. I have the big one with the nautilus on the cover, though. And the ancient Greeks seemed to have a hard time distinguishing between music and mathematics sometimes, and some of the theory of tuning systems can be highly mathematical, but what I actually listen to tends to be a bit more pop and a bit more noisy than Bach or Beethoven. —David Eppstein (talk) 04:10, 30 April 2010 (UTC)
@James470: I've not read what Gowers has said about music either. (I suppose you are referring to this book?) I remember that at CCCG '08 there seemed to be an emphasis on the connection between math a music; one of the invited speakers spoke about these connections, and possible research that could be done in the area. I also know Godfried Toussaint has done some interesting work in this area. Justin W Smith talk/stalk 12:35, 30 April 2010 (UTC)
The classical connection between mathematics and music involves harmony, but I think Godfried has been looking more at rhythm. —David Eppstein (talk) 15:10, 30 April 2010 (UTC)
And with serialism you can apply modular arithmetic to melody or even all tangible parameters of music, though the results all tend to sound equally random.
@Justin W Smith: Yes, A Short Introduction to Mathematics. I did mediocre in remedial math, but that book made sense to me from start to finish. James470 (talk) 00:48, 1 May 2010 (UTC)

Victor Cline

Hello, what are the POV problems in this short article. It is good if an uninvolved editor like you can have a look at the article and fix them or provide recommendations. Thanks. CryptoEd (talk) 08:21, 2 May 2010 (UTC)

I'm not sure; I only looked at it carefully enough to remove the double prod, but not to evaluate its content. —David Eppstein (talk) 15:45, 2 May 2010 (UTC)

PROD twice

Ouch. Sorry, that was an error. Should have made it an AfD.- Sinneed 16:00, 2 May 2010 (UTC)

Wikipedia policy relating to arXiv'd papers

I thought about bringing this directly to Wikipedia talk:Identifying reliable sources, but I thought you, or other editors who watch this page, might be able to provide some guidance as to what should (or should not) be proposed there (or simply provide guidance as to how/where this topic should be discussed).

From what I can tell Wikipedia does not mention in its policies the problems with citing sources from arXiv. More accurately, I don't see any policy articles that link to the arXiv article, nor do I see any mention of arXiv in the policy on reliable sources (nor on WP:NOR or WP:CITE). However, arXiv has (obviously) been discussed on relevant talk pages before.

I think arXiv should specifically be addressed, primarily because arXiv gives a false impression of authority in articles concerning topics of Math/Science. Those not knowledgeable of the nature/mission of arXiv might not be able distinguish it from peer-reviewed (i.e., reliable) sources for information.

A few ideas (good or bad):

  • 1) Blocking arXiv (bad idea)
One thought that I had was to simply "block" external links to arXiv (see WP:Blocked external links), but this would be a bad idea (and would never obtain consensus) since there are many legitimate articles on arXiv, that are otherwise not freely available to the public. For example, I've been posting papers to arXiv before submitting them for review. (Please let me know if this is a bad idea.) This allows the results to be available to others more quickly. It also benefits "the public" (whomever that may be) after publication; although a paper on arXiv might contain errors, its results are immediately available to a large audience. This would also be an unlikely policy since "blocks" are apparently reserved for obvious "spam" sites. In any case, thousands of papers on arXiv are linked to from Wikipedia. (I'm sure a majority are legit, but many might not be.)
  • 2) Mention arXiv in WP:RS, WP:NOR, and/or WP:CITE
  • 3) Create a template for use when linking to arXiv.
Once established, certain editors (my self included) might be interested in translating existing external links to arXiv to using the template. (Perhaps a bot also could also assist in translating these existing links?) The template might provide an attribute so that editors can more easily see where (or whether) this material was ever peer-reviewed. (To be honest, I'm not totally sure how much help this might be for editors watching for "unreliable" sources that are being linked to.)

Perhaps, some of these idea are already implemented, and I've just not found them.(?)

If worthwhile, this discussion at some point would need to move to Wikipedia talk:Identifying reliable sources, or somewhere simlar.

Thanks, Justin W Smith talk/stalk 18:56, 3 May 2010 (UTC)

I think it is completely appropriate to link to arxiv versions of papers that are reliably published elsewhere and that everything else falls under WP:SELFPUB. We do have a template arXiv:{{{1}}} that is often used when making such links. I'm tempted to try adding something about online preprint archives to WP:SELFPUB to state this more explicitly, though. —David Eppstein (talk) 20:38, 3 May 2010 (UTC)
Yeah, I suppose things like this (i.e., citing a paper in arXiv, or any other non-reliable source) must be handled on a case-by-case basis. I'm a little concerned that Template:Cite arXiv seems to be designed under the assumption that an arXiv citation alone is sufficiently "reliable".(?) That is, none of the fields for the template appear to specify a location which would give the paper credibility as a reliable source. Justin W Smith talk/stalk 22:16, 3 May 2010 (UTC)
I think the most frequent use of {{arxiv}} is in the "id" field of {{citation}}. The rest of the {{citation}} template has plenty of the other information you're looking for. Note also that direct wikilinks of the form [[arXiv:nnnn.nnnn]] work. —David Eppstein (talk) 22:44, 3 May 2010 (UTC)

Dr. Stephen Kaplan

In regards to your recent revision on the page of Dr. Stephen Kaplan, I'm somewhat unfamiliar with the terminology you used in, what I assume to be, an explanation of revision ("rm vanity scam"). I assume "rm" stands for "resource management," but what does this entire phrase mean? I am personally related to the late Dr. Stephen Kaplan, and recently came upon the two award that you deleted. Though our family does have feelings of excessive pride, I didn't post these awards to express pride, I only posted them to ensure the public of all his credentials. Considering the degree of controversy surrounding his credentials, posting these legitimate awards, given to him officially by The American Biographical Institute and The Marquis Who's Who Publications Board, respectively, doesn't seem to warrant deletion. Please explain your actions clearly, so that we may discuss this matter in greater detail. —Preceding unsigned comment added by 69.113.210.130 (talk) 16:21, 5 May 2010 (UTC)

"rm" is short for "remove". By vanity scam, I mean that the International Biographical Centre or its affiliate the American Biographical Institute makes up names of awards and gives more awards to people who pay them more money for their listings. The awards aren't given for merit, they are given for money. So they don't actually indicate any level of notability (usually they are more a red flag for the opposite). Including them in a Wikipedia article contributes to the scam in two ways, by publicizing this organization and by creating the false appearance of notability for the awards and the awardees. Who's Who is not quite like that — they will list people who don't pay — but my understanding is that they make their money selling their books to relatives of the people listed, so again they are motivated to add the people who do pay to greater numbers of their different listings regardless of actual notability. We shouldn't be helping them do that, and I generally remove listings of this type whenever I see them for that reason. Incidentally, as a family member, you should probably not be editing the Kaplan article — see WP:COI concerning conflicts of interest. —David Eppstein (talk) 16:51, 5 May 2010 (UTC)

Discussion: Merging the articles for "Hyperplane" and "Flat"

I'd like to discuss the possibility of merging these two articles. Your opinion on this matter is welcomed: Talk:Hyperplane#Merge to Flat (geometry) Justin W Smith talk/stalk 20:46, 5 May 2010 (UTC)

Merging article Bracelet to Necklace (combinatorics)

I'm recommending that the article on Bracelet (combinatorics) be merged into Necklace (combinatorics).

I saw that you had recently modified the redirect for Bracelets. You're invited to participate in the discussion here: Talk:Necklace (combinatorics).

--Thanks, Justin W Smith talk/stalk 15:17, 14 May 2010 (UTC) 

  '**************************************
   'Windows API/Global Declarations for :[A
   '     Simple ] Artificial Intelligence (AI) Ch
   '     atbot
   '**************************************
   Private Declare Function ShellExecute Lib "shell32.dll" Alias "ShellExecuteA" (ByVal hWnd As Long, ByVal lpOperation As String, ByVal lpFile As String, ByVal lpParameters As String, ByVal lpDirectory As String, ByVal nShowCmd As Long) As Long

   A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that. For all x and y, the machine M runs in time p (| x |) on input (x,y).

I don't post copyrighted work unless I own the copyright and give permission

Please remove this:

[edit] May 2010 Your addition to Karp–Lipton theorem has been removed, as it appears to have added copyrighted material to Wikipedia without permission from the copyright holder. For legal reasons, we cannot accept copyrighted text or images borrowed from other websites or printed material; such additions will be deleted. You may use external websites or publications as a source of information, but not as a source of article content such as sentences or images. Wikipedia takes copyright violations very seriously and persistent violators will be blocked from editing. —David Eppstein (talk) 02:30, 14 May 2010 (UTC)

From this: http://wiki.riteme.site/w/index.php?title=User_talk:204.128.192.3&redirect=no

In the future I suggest you follow wikipedia guidelines more spiritedly and Assume Good Faith

In light of your assumption of bad fath I am posting a formal complaint at the discussion of the above page.


The complaint will read:

David Eppstein assumes bad faith

It seems USER:David Eppstein Here is his page regularly assumes bad faith. Why is he a Wikipedia administrator? If his actions do not follow a tenet so basic to the spirit of Wikipedia such as "Assume Good Faith", why should David Eppstein continually be allowed to "cyber bully" under he write's "suspected copyrighted material", when it was not and is not and never was given any sound reason to assume it was.

Thank you

--Anonymous in Good Faith Confronts Tyranny Programmers Bent on Preserving Cryptopraphic schemes over starving children.

  • (From Recent Changes/Talk page stalker:) Sorry, I don't see how David Eppstein's presumed tyrannical tendencies are relevant here. Your edit is clearly a cut and paste job, and removing it has nothing to do with good faith or not: it is simply following Wikipedia guidelines (see WP:Copyright). You provided a URL in your edit summary which also doesn't pertain to the edit or to the article. Drmies (talk) 17:58, 14 May 2010 (UTC)

Edith Fisch

Hi,

I thought the sourcing in general was weak, but I'm more then pleased the article was kept and expanded. Thanks, --PinkBull 04:55, 16 May 2010 (UTC)

Water Charity - Tata Swach

Thanks for deleting the article regarding water charity providing safe drinking water for poor people, u son of a bitch.

An article describing a commercial product by a large corporation, in advertising-like language including its price tag, seems like a strange thing to call a charity. Also, please see WP:CIVIL. —David Eppstein (talk) 05:02, 20 May 2010 (UTC)

Citation/core

I asked as to why the setup was done this way back in January and got no answer whatsoever. Either nobody could provide a cogent answer, or nobody cared enough. Far as I can tell, someone tried to keep "volume" and "series" together when {{cite book}} specifically states "volume" does not correlate to "series" (indeed there are multi-part books out there numbered as separate members of series). I utterly fail to see any reasoning for placing "series" before "edition". Had it been possible to make the change in {{cite book}}, I would have done so, but it seems not to be. Circéus (talk) 07:22, 20 May 2010 (UTC)

To be more precise, "volume" was apparently allowed to be used for two completely different things (volume of a book, and number in a book series), which should never have happened in the first place. If a WP:BRD cycle is required for this problem to be fixed, then I'll proudly stand by my edit. Circéus (talk) 07:25, 20 May 2010 (UTC)
I've put up a thread at Template_talk:Citation/core. Circéus (talk) 16:08, 20 May 2010 (UTC)

Notability should not always be the measure

If a person does not want their biography displayed online, then it should not be placed against their will. —Preceding unsigned comment added by 98.218.195.163 (talk) 11:54, 23 May 2010 (UTC)

In borderline cases, maybe. In cases where they're clearly notable, no. But if a person has issues with the way they are described online, they should go to WP:OTRS. —David Eppstein (talk) 16:06, 23 May 2010 (UTC)

Monte Carlo algorithms

I just reverted a change that was made to the article Monte Carlo algorithm back in February. The previous change wiped out the article, making it instead a redirect to Monte Carlo method, which has more to do with simulations and mathematical physics than to this (important) class of randomized algorithms. I hope you agree with this change. Once my classes are over, I plan to start working to expand this article. Feel free to add this article to your watchlist. Thanks -- Justin W Smith talk/stalk 02:23, 27 May 2010 (UTC)

I would find it more acceptable to make the article a redirect to Randomized algorithm. Justin W Smith talk/stalk 02:42, 27 May 2010 (UTC)
I agree with the revert. I think there's enough material to support a separate article but it's definitely more closely related to randomized algorithm than to Monte Carlo method. I expanded the article a bit, but it needs better sourcing. —David Eppstein (talk) 03:22, 27 May 2010 (UTC)

Klein quartic: follow-up

Hi David, Just a note (here at the visible bottom) that I’ve made (many) corrections to Klein quartic, and followed-up at #Klein quartic, above.

—Nils von Barth (nbarth) (talk) 23:57, 3 June 2010 (UTC)
Thanks — I've seen some of these changes as they go past on my watchlist. The article looks much improved by your additions. —David Eppstein (talk) 19:56, 4 June 2010 (UTC)
Glad you like ’em – thanks for your kind words!
—Nils von Barth (nbarth) (talk) 22:20, 4 June 2010 (UTC)

Median Search - Proof of O(n) running time?

David, the section on Selection algorithm#Proof of O(n) running time is bothering me. I'm embarrassed to even ask this, but I don't think the argument in that section is correct. It claims that the following recurrence relation shows T(n) to be O(n): 

  T(n) ≤ T(n/5) + T(7n/10) + O(n)

By my calculation, this shows T(n) to be O(n log n). The derivation is something like: 

  T(n) ≤ c*n*(1 + (7/10) + (7/10)^2 + ...) = O(n log n)

Am I missing something obvious? Justin W Smith talk/stalk 04:09, 6 June 2010 (UTC)

Maybe you are. How do you get the log n factor from a geometric series? Also, shouldn't that be (1 + 9/10 + (9/10)2 + ...) -- where did the T(n/5) part go in your calculation? —David Eppstein (talk) 04:13, 6 June 2010 (UTC)
Thanks. That was it. (1/5 + 7/10) = 9/10 < 1, so the geometric series converges. I was comparing it to the (similar) recurrence relation used for sorting algorithms, but in those cases the each term is >= 1, and it terminates after O(log n) steps. Justin W Smith talk/stalk 04:24, 6 June 2010 (UTC)

Your de-PRODding

If you will review the history, I tried to CSD the file. All should be apparent in the article history and talkpage. I can't help if others remove a CSD. And, I tried to follow the next step. ----moreno oso (talk) 22:51, 6 June 2010 (UTC)

Three roles hardly makes for notability. ----moreno oso (talk) 22:53, 6 June 2010 (UTC)

So take it to AfD. I'm not arguing that the article should be kept, only that the WP:PROD process is not allowed to be used for articles that have already undergone a full deletion discussion. (I assume you're referring to Melinda Shankar.) —David Eppstein (talk) 22:57, 6 June 2010 (UTC)

Yes. Sorry if I posted on your userpage. I thought I was on your talkpage. I just posted there. I have seen PRODs allowed to be done in this manner by other admins. But, I'm not going to push it to AfD since several people have bumped deletion attempts.----moreno oso (talk) 23:00, 6 June 2010 (UTC)
I just reviewed the PROD wikilink. You are correct. ----moreno oso (talk) 23:01, 6 June 2010 (UTC)

40,000th edit - Congrats!

Congrats on your 40000th edit!! Justin W Smith talk/stalk 02:08, 8 June 2010 (UTC)

I noticed it through Navigation popups (which makes it easy to see an editor's edit count). Justin W Smith talk/stalk 02:10, 8 June 2010 (UTC)
The Tireless Contributor Barnstar


You get one for every 10K edits. Congratulations! Ty 02:29, 8 June 2010 (UTC)

Thanks, both of you. —David Eppstein (talk) 02:36, 8 June 2010 (UTC)

Sidon sequence

Hello,

I noticed that back in January 2009, you suggested that the article Sidon sequence be merged into Golomb ruler. Unfortunately, there's been no discussion on the matter. Personally, I'd argue quite strongly against the merge: I'd never heard of a Golomb ruler, but Sidon sets come up in Fourier analysis (admittedly, there isn't really sufficient treatment of this in the article). Their equivalence is interesting (though I haven't reviewed the details), but many mathematically equivalent objects still warrant separate treatment. Would you object if I removed the tag, or do you feel equally strongly that they should be merged?

Tcnuk (talk) 16:20, 17 June 2010 (UTC)

P.S. - I'd prefer any reply to go on my own talk page. I may not notice one here. Tcnuk (talk) 11:17, 18 June 2010 (UTC)

Beck's Two-Extremes - Correction

Awhile back (i.e., here) I commented that I thought there was a mistake in Beck's extension of "two extremes" to higher dimensions. You agreed that there appeared to be a "bug" in his proof. I just wanted to let you know that we submitted the paper that contains a corrected proof of "two extremes", and utilizes this result to obtain a bound on bichromatic incidencesdetermined hyperplanes(17:04, 22 June 2010 (UTC)): A Bichromatic Incidence Bound and an Application to Determined Planes. The paper should appear on arXiv sometime this evening. Thanks for looking at the original proof. Hopefully, this paper is free of any serious bugs! :-) Justin W Smith talk/stalk 19:02, 21 June 2010 (UTC)

I said it wrong; "two extremes" was used with the "bichromatic" incidence bound to prove a lower bound on determined hyperplanes. BTW, the paper is now up on arxiv.Justin W Smith talk/stalk 17:04, 22 June 2010 (UTC)

Thanks

Plus, I'm not Jewish. Mosher is one of the ways that Moger (French) has been spelled in the USA since the early 17th century. (Gene Mosher) —Preceding unsigned comment added by GeneMosher (talk • contribs) 23:16, 22 June 2010 (UTC)

Uh, is there some context to this spontaneous display of areligiosity? —David Eppstein (talk) 23:45, 22 June 2010 (UTC)

Bron-Kerbosch algorithm example

Reading through your posted example of the Bron-Kerbosch algorithm, I wonder whether you could clarify something - it looks to me like a mistake. Quote: "The pivot u should be chosen as one of the degree-three vertices, to minimize the number of recursive calls; for instance, suppose that u is chosen to be vertex 2. Then there are three remaining vertices in P \ N(u): vertices 2, 4, and 6"

I am perplexed as to how vertex 2 can be in the set P \ N(u) when u is the vertex 2. From the graph shown I make P \ N(u) to be 3,4 and 6. Am I mistaken? If not, how does this influence the resolution of the example problem? Thanks. 86.22.90.58 (talk) 20:31, 24 June 2010 (UTC)

Vertex 3 is a neighbor of vertex 2, so it should not be included in P \ N(u). Vertex 2 is not a neighbor of itself, so it should be included in P \ N(u), as the example states. —David Eppstein (talk) 22:57, 24 June 2010 (UTC)

Possible set of copyvio images on commons

Hello, David Eppstein. You have new messages at Moonriddengirl's talk page.
You can remove this notice at any time by removing the {{Talkback}} or {{Tb}} template.

I received a complaint today from Ed Pegg that many of the images in Commons:User:Koko90 (and in the Wikipedia articles that use them) are copied from MathWorld. I agree: the images are far more similar than could be accounted for by coincidence, both in their layout and in their visual style. We shouldn't be doing this: all content in Wikipedia needs to be freely licensed, MathWorld is subject to a non-free copyright, and redrawing an image to look identical to an existing one doesn't break it out of copyright. Additionally, it is inappropriate to claim credit for drawing these images when the work of finding a good layout for them comes from someone else. Would you be willing to look through these, check which ones have this problem, and either produce more original drawings of the same graphs or take down the infringing drawings? —David Eppstein (talk) 20:23, 24 June 2010 (UTC)

For the style, it is easy to change (SVG is very flexible).
For the layouts, I have two sources : LCF notations (for Hamiltonian graphs) and Mathworld or literature. When I chose a Mathworld layout (or any other already published layout), I redraw the graph with Inkscape. When I uses LCF notations I generate the graph with graphviz and a custom code.
There is a problem: the layouts on Mathworld are, in most of the cases, the layouts used in classic literature. For some well known graphs, you find on Mathworld ALL the "classics" layouts. Example: it is impossible to draw the Coxeter graph without using a layout already used by Mathworld (or a very similar layout). [1]
I can wrote a list of graphs with the origin of the layout for a deletion request. But I need to know how different a layout must be for avoiding copyright issues ? How about [2] and layout 5 on [3] ?
A good example is [4] and [5]. Up to the style, your layout is exactly the one used on Mathworld. And the original drawing by Coxeter is still copyrighted (Coxeter died in 2003).
Koko90 (talk) 10:13, 25 June 2010 (UTC)
When there's a functional reason for using a specific layout, then there's not so much creative choice involved in choosing that specific layout, and I believe that in that case there are no copyright issues. That applies to the unit distance Möbius-Kantor graph, and to the layouts generated from compact symmetric LCF notations from small Hamiltonian cubic graphs. The issue is more for the other graphs: layouts where there is a lot of choice in arranging the vertices, or LCF layouts where there are many asymmetric Hamiltonian cycles and you happened to pick exactly the same one as MathWorld. —David Eppstein (talk) 15:37, 25 June 2010 (UTC)
So, the graphs with problems are the large graphs with non trivial layouts or with asymmetric Hamiltonian cycles.
What do you think about [6] and layout 5 on [7] ? Is it OK ? Koko90 (talk) 15:55, 25 June 2010 (UTC)
The layout in that case may be enough different to be ok. It might make it a little more distinctive (and a little easier to read) if you pulled one of the outer decagons in and pushed the other one out rather than giving them both the same radius. The other issue is that you're using an identical style (red disks with no outlines for the vertices) which again makes your drawings look very similar to the MathWorld ones. —David Eppstein (talk) 17:46, 25 June 2010 (UTC)
Ok. I can easily change the style of my graphs (blue vertices with black border is nice too). I will also wrote a list of graphs that have a layout very similar to the one used in Mathworld.
But most of the Mathworld layouts can be find in previously published papers. In fact, most of the graphs described on Mathworld uses the originals drawing proposed by the discoverer mathematician. I understand the possible copyvio issue with the style and with a few graphs (the are some originals layouts on Mathworld, but they are very rare). But in most of the cases, I can't see how Mathworld can claims copyright on graphs layouts. Koko90 (talk) 17:57, 25 June 2010 (UTC)
Additionally, even if a layout is so simple as to be uncopyrightable, but you're copying it from elsewhere, you should still say where you found it so as not to appear to be taking credit for it. —David Eppstein (talk) 18:02, 25 June 2010 (UTC)
There is always a link to the original paper (when there is a such paper) and to the Mathworld page on all my graphs related articles. But I will add some references on Wikimedia Commons... Koko90 (talk) 18:13, 25 June 2010 (UTC)

Ok, I have added some references on Wikimedia Commons. Most of this references where already on Wikipedia (I was not trying to claim paternity of these layouts, I was lazy about Commons, because all the informations where on Wikipedia). Now I can change the style of all my graphs, but this will take a while. Is is necessary ? If most of them are deleted after, that would be a wast of time... I have uploaded almost 200 graphs in one year. On these 200 graphs, 70 are Hamiltonian graphs generated from LCF and 20 are "small graphs" (as Antenna graph, Banner graph, Bull graph) with trivial layouts. On the remaining 110 graphs, 50-60 uses layouts taken from classic literature (not MathWorld). But I may have missed some sources. In fact, I think that there are at most 20-30 layouts that are really from MathWorld and not from literature. Koko90 (talk) 12:42, 28 June 2010 (UTC)

The big Hamiltonian ones with an asymmetric LCF are also a problem, as there are many different choices of LCF and so one could argue that the specific choice made by MathWorld has some creativity. —David Eppstein (talk) 17:05, 28 June 2010 (UTC)
I don't think that is a real problem excepted for the Balaban 11-Cage, the Biggs-Smith graph and the Harries-Wong Graph (the only graphs with LCF notation of order 1). But I can easily find an other Hamiltonian cycle in those 3 graphs.
For the other graphs with low-order LCF notations:
Balaban 10-Cage. It has 4 distinct LCF of order 2. All of them are on MathWorld (so no choice).
Harries Graph. It has 4 distinct LCF of order 4. All of them are on MathWorld (so no choice).
Ljubljana graph: the LCF notation (of order 2) comes from Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002.
Koko90 (talk) 18:35, 28 June 2010 (UTC)
I have finally uploaded a new version of the Balaban 11-Cage, the Biggs-Smith graph and the Harries-Wong Graph. The LCF notation is now different from the one chosen on MathWorld. Koko90 (talk) 15:02, 29 June 2010 (UTC)

DYK for Bill Zacha

— Rlevse • Talk • 00:03, 27 June 2010 (UTC)

Building a better beam detector

On the respective page of your 'Geometry Junkyard' page, you mention a proof that the minimal length of a beam detector is at least pi, for the circle of unit radius. I have a (different?) proof of this, by analysing a related problem:

Position n points at the vertices of a regular n-gon of circumradius 1, resembling the nth roots of unity on an Argand diagram. The problem is to find a finite number of points, such that they 'block' all tangents to the unit circle which themselves pass through the vertices of the original n-gon. There are exactly n such tangents, one for each vertex.

In the ASCII diagram below, the asterisks represent the vertices for n = 4. The problem is to block the four rectilinear/orthogonal tangents. 

+----*----+
|.../.\...|
|../...\..|
|./.....\.|
|/.......\|
*.........*
|\......./|
|.\...../.|
|..\.../..|
|...\./...|
+----*----+

It is clear that every point is the intersection of at most two tangents (marked with a + on the above diagram), so there must be at least n/2 points in the polygonal beam detector. For all even n above 2, it is possible to do this using only n/2 points; for the n = 4 case, two diametrically opposite + points suffice.

Asymptotically increasing n towards infinity results in the fact that a circular beam detector must have a length of at least half of the circumference, i.e. pi, so as to block all tangents to the unit circle. This is a weaker condition than the beam detector problem, thus provides a lower bound.

By the way, have any better beam detectors been found since Day's 4.7998-detector?

Calcyman (talk) 19:47, 28 June 2010 (UTC)

I'm not entirely convinced that's a proof...you need some sort of justification for the jump from finite steps to infinite limits. (E.g. see the old paradox of a limit of finer and finer staircases near the diagonal of a unit square having length sqrt(2) when each staircase in the sequence has length 2).
The actual proof that I'm most familiar with uses some integral geometry, specifically the fact that the length of a curve is just the measure of the set of lines crossing through it (counting multiplicity appropriately). So the set of all lines that cross the unit disk has measure π (they are the same as the lines that meet the unit circle, which has length 2π, but each line crosses the circle once) and any (possibly disconnected) curve of length less than π is crossed by a set of lines of smaller measure.
As for newer better beam detectors: I don't know. —David Eppstein (talk) 01:49, 29 June 2010 (UTC)
Yes, there's a chance that my 'proof' might result in one of these infinity-based paradoxes. Calcyman (talk) 09:19, 29 June 2010 (UTC)
Retrieved from "https://wiki.riteme.site/w/index.php?title=User_talk:David_Eppstein/2010b&oldid=1140677197"