tag:blogger.com,1999:blog-3722233.post1949085321483313850..comments2020-10-29T13:56:19.634-05:00Comments on Computational Complexity: Knowledge is Power!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-86646329894933711552010-05-18T18:14:02.958-05:002010-05-18T18:14:02.958-05:00Having a broad range of knowledge is imperative to...Having a broad range of knowledge is imperative to every aspect of life. First, you never know when you'll have an opportunity to be on Jeopardy. More seriously, having analytical and critical thinking skills are neccessary for success in any field. These are only aquired by algebraic experience. The deeper your analytical skills run, the more algebraic knowledge you will have by default. Whether you need to use algebra or not is beside the point. Writing and communication skills are neccessary to share one's findings with the world. Without knowledge of proper parts of speech, grammer, vocabulary, and research formats (i.e. APA or MLA) one can not bring their ideas to fruition-again, regardless of whether or not you needed specific English skills for your research. Finally, as researchers, teachers, and leaders in our fields, we are role models-like it or not! A well educationally rounded person commands respect and sets the bar for future minds. Multi-based knowledge leads to intelligence. Single minded knowledge leads to narrow ideas, perspectives, and ignorant leaders. Thank you for allowing me to ramble. JeffJeffhttps://www.blogger.com/profile/16305384049164992925noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10318034036022240702010-05-16T13:17:12.238-05:002010-05-16T13:17:12.238-05:00Hmmm ... for a write-up on "natural algorithm...Hmmm ... for a write-up on "natural algorithms in quantum simulation", I had occasion to survey usage of the word "naturality" (using the arxiv's full-test search).<br /><br />The results were very interesting: "mathematics" preprints accounted for 86% of the net usage of the term "naturality" ... "physics" preprints 15% ... "computer science" 2% ...<br /><br />All other disciplines were below one percent ... the usage of "naturality" in "quantitative biology", "quantitative finance", and "statistics" was identically zero.<br /><br />Note: percentages sum to slightly more than 100% due to cross-listing of some preprints.<br /><br />If "knowledge is power", we can infer that introducing the (powerful IMHO) notion of naturality to disciplines beyond than mathematics is a trend that is just getting underway ... with physics and computer science in the vanguard.<br /><br />Of course, this begs the question "What is mathematical naturality?" ... and I wish that Lance/GASARCH or Bill Lipton would pose this question ... as I have not found a pithy definition (yet) in the mathematics literature!John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43504023848778660562010-05-16T11:11:22.445-05:002010-05-16T11:11:22.445-05:00Vinayak, just use Gasarch's given method to fo...Vinayak, just use Gasarch's given method to force u and v to be the same color, then add another vertex v' connected only to v. u and v' are now guaranteed to be different colors, but are not connected.<br /><br />Note, however, that this graph contains a complete k-graph (u together with the subgraph H), so its chromatic number of k is not especially interesting.FormerVDWUgradnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19424191805463037432010-05-16T10:53:03.519-05:002010-05-16T10:53:03.519-05:00Thanks.
Here is an interesting modification of th...Thanks.<br /><br />Here is an interesting modification of the question.<br /><br />Can you construct a graph G with two specified vertices u and v such that there is no edge between u and v but in any proper coloring of G, u and v must get different colors?<br /><br />Such theorems may be useful in finding lower bounds on the chromatic number of different classes of graphs. Let's say, for example, that we are trying to lower bound the chromatic number of graph class called class A. Let's say that with some hard work we have been able to find an A graph that has a chromatic number of k. We want to see if we can improve the lower bound. To do this, it will be useful to construct an A graph G in which one can identify k vertices that have the property that they must get different colors in any proper coloring of G, because then, we can just add one more vertex to G and connect it to those k vertices. If the new graph is also an A graph, then we have improved the lower bound.<br /><br />Does recursive graph theory have tricks to do such things?Vinayakhttps://www.blogger.com/profile/10879814454563618581noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90567102126480105912010-05-14T09:33:27.261-05:002010-05-14T09:33:27.261-05:00Vinayak: Here is the trick.
GOAL: construct a grap...Vinayak: Here is the trick.<br />GOAL: construct a graph that has<br />two special vertices u and v such that<br />in ANY k-coloring of G u and v must<br />be the SAME color.<br /><br />Let H be the complete graph on k-1 vertices. Connect u to EVERY vertex of H.<br />Connect v to EVERY vertex in H.<br />Call the resulting graph G.<br />In any k-coloring of G, the vertices of H<br />will use k-1 colors, so u and v must use the remaining color.<br /><br />GASARCHGASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12089224548618341472010-05-14T08:36:31.403-05:002010-05-14T08:36:31.403-05:00Also, can the trick be modified to construct graph...Also, can the trick be modified to construct graphs that when colored, must give different colors to u and v even though there's no edge between u and v? If yes, then this can be very useful in constructing graphs with high chromatic numbers.Vinayakhttps://www.blogger.com/profile/10879814454563618581noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67834857499840958562010-05-14T08:31:33.614-05:002010-05-14T08:31:33.614-05:00"There is a trick in recursive graph theory w..."There is a trick in recursive graph theory where you build a graph G with two special vertices u and v so that if G is properly k-colored then u and v are the same color."<br /><br /><br />What's that trick? Can you explain it or give references please?Vinayakhttps://www.blogger.com/profile/10879814454563618581noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8517520070964696802010-05-13T21:29:53.572-05:002010-05-13T21:29:53.572-05:00http://blog.computationalcomplexity.org/2009/10/pr...http://blog.computationalcomplexity.org/2009/10/proud-to-be-monomath.html<br /><br />Lance is proud to be a Monomath, while GASARCH suggests, inadvertently, the capabilities that being a Polymath lends you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46844368383548790112010-05-13T10:20:04.585-05:002010-05-13T10:20:04.585-05:00Knowing Shannon's (classical) Capacity Theorem...Knowing Shannon's (classical) Capacity Theorem greatly helped in analyzing the fundamental limits to <a href="http://www.pnas.org/content/106/8/2477.full" rel="nofollow">quantum spin biomicroscopy</a>.<br /><br />With respect to Mac Lane calls "Tricks versus Ideas" ... the Shannon Theorem provided a fresh approach to <i>both</i> ... this is what a really good outside idea does for you.John Sidleshttp://www.mrfm.orgnoreply@blogger.com