In my
last post
I gave and asked for examples of people who didn't know things
that they really ought to know.
A commenter named Josh said posted the following:
Bill's question seems to generate a lot of
nonpositive responses, e.g., embarrassing stories
of lack of knowledge.
How about a slightly more positive question: are there
examples where someone KNOWING something from slightly
outside their tiny area of expertise led to significant
results?
This is a great question! I give two example from my own
research that almost qualify--- I used knowledge from outside
of my tiny area, though I would not call the results
significant. Readers- do what I do, put aside the question
of significance (a topic for another post perhaps) and
just comment on when knowing stuff from a different area or
areas helped you in research.
-
Knowing omega-automata and Hilbert's tenth problem was the key to the paper
Learning via
Queries which was co-authored with Carl Smith and
appeared in FOCS 1988 and JACM 1992.
It was the first in a series of papers that added queries to
the Inductive Inference model.
-
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.
This is NOT a hard trick.
I used a variant of this trick to find better bounds for some
poly VDW numbers. This lead to, in turn,
a problem on the Maryland Math Competition, two
projects for High School Students, one project
for college students, and finally a paper (in progress)
by Gasarch-Kruskal-Kruskal.
But never mind me, I want to hear from YOU!
Knowing Shannon's (classical) Capacity Theorem greatly helped in analyzing the fundamental limits to quantum spin biomicroscopy.
ReplyDeleteWith respect to Mac Lane calls "Tricks versus Ideas" ... the Shannon Theorem provided a fresh approach to both ... this is what a really good outside idea does for you.
http://blog.computationalcomplexity.org/2009/10/proud-to-be-monomath.html
ReplyDeleteLance is proud to be a Monomath, while GASARCH suggests, inadvertently, the capabilities that being a Polymath lends you.
"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."
ReplyDeleteWhat's that trick? Can you explain it or give references please?
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.
ReplyDeleteVinayak: Here is the trick.
ReplyDeleteGOAL: construct a graph that has
two special vertices u and v such that
in ANY k-coloring of G u and v must
be the SAME color.
Let H be the complete graph on k-1 vertices. Connect u to EVERY vertex of H.
Connect v to EVERY vertex in H.
Call the resulting graph G.
In any k-coloring of G, the vertices of H
will use k-1 colors, so u and v must use the remaining color.
GASARCH
Thanks.
ReplyDeleteHere is an interesting modification of the question.
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?
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.
Does recursive graph theory have tricks to do such things?
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.
ReplyDeleteNote, 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.
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).
ReplyDeleteThe results were very interesting: "mathematics" preprints accounted for 86% of the net usage of the term "naturality" ... "physics" preprints 15% ... "computer science" 2% ...
All other disciplines were below one percent ... the usage of "naturality" in "quantitative biology", "quantitative finance", and "statistics" was identically zero.
Note: percentages sum to slightly more than 100% due to cross-listing of some preprints.
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.
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!
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. Jeff
ReplyDelete