Feeding a Family of Four

A statistics student, some time back, posted on Facebook a joke about (1) a large pizza, (2) statisticians, (3) applied mathematicians and (4) theoretical mathematicians.  The punch line was that the first three could each "feed a family of four." 

At the time, the joke seemed to be aimed at “the other half” of our department program, at our students in theoretical (pure) mathematics. As  graduate coordinator in our pure math program, I took the post a little personally.  My frustration with the joke was not just that it seemed to say, “We [stat students] are better than you — we will get jobs and you won’t!” but that it was simply wrong.  

There seems to be a strong demand for students in a theoretical (or “pure”) math program, but a popular belief in our cultural is that all mathematicians ever do is teach.  

Why hire theoretical mathematicians?

A mathematician learns to solve a vague, fuzzy problem by organizing the problem into a coherent form and then using various tools to attack this coherent problem.  Since every problem begins with a vague, poorly defined stage, these problem-solving tools are valuable in industry and in applied mathematics, even if the original training is theoretical.  

Higher education often trains people to be specialists, to be excellent in a narrow field. This can be very good.  We need chemical engineers, actuaries, statisticians, mathematical biologists, petroleum engineers … and nurses and doctors.  But training in theoretical mathematics tends to avoid this specialization, concentrating instead of deep understand of general mathematical principles.  This creates a certain tension in the job market — do companies prefer a specialist, assigned to a particular task, or a generalist who is good at solving problems of all types?  It depends….

From my experience, both specialists and generalists have their place, but it is foolish to require education to focus on a single small specialty.

An undergraduate student timidly knocked on my office door one afternoon, several years ago.  I invited her in and she began to discuss her “problem.”  She liked math but didn’t want to teach.  Her dad wanted her to be a chemist because he wanted her to have a real job (like he did.)  He was convinced that if she pursued her desire to major in math then she would have to be a teacher if she wanted to have a paycheck.  After we chatted a bit, I wrote her a long email (meant to be read by dad) that laid out all the various job opportunities available in mathematics.  Eventually she majored in math, did an undergraduate research project in statistics (yes, statistics!) and received a large fellowship to pursue doctoral studies at a major university.  Yes, you can love mathematics and get paid a lot of money.  (And no, you won’t be teaching.  Obviously if you are making a lot of money, you are not teaching....)

One of our graduate students had a similar problem.  Her father worked for a major international corporation which builds agricultural machinery.  He wasn’t very eager for his daughter to get a masters degree in mathematics because he wanted her to get a job after school.  The delightful part of this story is that after her masters degree, a certain company interviewed her and, due to her mathematical training, offered her a job with a salary higher than her father’s.  What company was interested in her mathematical training? The same company that her dad worked for!   (It was just a different branch.)

Around 1990, I spent a year at the National Security Agency (NSA) as part of a mathematical sabbatical.  The National Security Agency has literally thousands of mathematicians working there (probably over ten thousand -- but the exact number is classified.)  Outside the NSA there are more thousands of mathematicians working for the various defense contractors such as Westinghouse.  (There are also defense contractors in other parts of the country, including Texas.)

Our cell phone technology would not exist without the mathematicians who design the codes to carry the digital signals.  Our internet commerce would not exist were it not for the mathematicians who designed the public key encryption schemes that allow us to securely exchange information through computer servers.

How is this related to undergraduate research?

Underneath the belief that "all you can do with math is teach it", is a belief that mathematics is a dead subject.  Vibrant, growing fields require that people engage in that field; dead, stagnant subjects only have room for teachers.

There are a variety of ways to emphasize the explorative processes in the growing field of mathematics.  Certainly one of the best ways to communicate the living nature of mathematics is to get students engaged in research in the subject!

Some resources

Here I've tried to collect some online sources that talk about the importance of mathematics and its value is science and society.


A recent NPR article describes the search for mathematicians to analyze big data.

A Wall Street Journal article describes the career of mathematician as one of the top, most desired jobs.

One of my favorite blogs to read is FutilityCloset; the blog has an interesting story, "Augury", on the connections between math and science.

Stanford mathematician, Keith Devlin, teaches a MOOC on mathematical thinking.

The Mathematical Association of America has some webpages devoted to the question, "What can I do with a math major?"  Here are some of the sample careers off of the MAA web page:

http://www.maa.org/careers/denbleyker.html  (Janet denBleyker -- actuary)

http://www.maa.org/careers/sford.html 

http://www.maa.org/careers/monticino.html

http://www.maa.org/careers/murray.html (Math major whose interests led him into computer science)

http://www.maa.org/careers/lentz.html  (Biostaticians whose interests led her on to a Ph.D. in animal science)

http://www.maa.org/careers/stabbe.html (Math major whose mathematical training eventually lead him to law school.)

Mathematicians are sought after in almost every area of industry.  The US government has been trying to fix the "crisis" in math and science for some time.  Earlier in this decade (about 2005) Congress had a committee look into the decline in American capabilities in science and technology.  The result was a report, "Rising Above the Gathering Storm: Energizing and Employing America For A Brighter Economic Future."  That report suggested some significant changes in the way the US prepares people for industry.  The top suggestion, coming from that investigation, addressing the country's greatest need, was:  "Action A-1: Annually recruit 10,000 science and mathematics teachers by awarding 4-year scholarships and thereby educating 10 million minds."

The reason for making STEM teaching a top priority is simply that we don't have enough people trained in science and math for the country's needs.  And to get good mathematicians, we need more math teachers!  Now, a lot of people have focused on the "teaching" part of this statement, but the reason the report mentions teachers is because the country desperately needs their students!  There are NOT enough math majors in this country for the jobs we have!

Next time: COURI & EURECA, promoting undergraduate research across campuses.

[Mathematical prerequisites: This article requires no mathematical background.]

Follow Ken W. Smith on Twitter @kenwsmith54

Randomly decomposable graphs, III (open questions in RDGs)

Some open questions in RDGs

In this third post on randomly decomposable graphs, we explore some open questions accessible to undergraduate students.  Partial results on these questions, for selected graphs, have just begun to appear in the mathematical literature and there are many, many trails to be explored in this area of the mathematical wilderness!

Fix a graph H and explore the poset RD(H) of all graphs G which are randomly decomposable with respect to H.  Recall that the height of a graph G in this poset is the number of edge-disjoint copies of H required to make G.  If the height of G is the integer a  and if H has q edges then G has e=aq edges.  A graph G is abundant with respect to H if there are more than a copies of H in G; G is trivial with respect to H if there are exactly a copies of H in G.  Thus the poset RD(H) partitions into two sets, the set,  RD_0(H), of trivial randomly decomposable graphs, and the set RD_A(H) of abundant randomly decomposable graphs.  Since H itself is a trivial member of RD(H), we can ask for minimal members of RD_A(H), that is, graphs which are abundantly RDG but have no subgraphs which are.

With this brief review, some basic mathematical questions jump out at us.

1. Given a fixed graph H, classify completely the members of RD(H).
2. Given a fixed graph H, list the minimally abundant members of RD(H).
3. Classify graphs H for which there are no abundant RDGs, that is, for which RD(H)=RD_0(H).
4. Are there graphs H for which RD(H) is finite?  Indeed, is it possible that RD(H)={H} for some graphs?

The first two questions invite experimentation with small graphs.  Choose a graph H with just 3 or 4 edges and first attempt to find the smallest abundant members of RD(H).  A helpful result in this area is the following lemma: 

"If G is minimally abundant with respect to H then the height of G 

is bounded above by the number of edges of H."  

Thus if H has only three edges, one need use at most three copies of H in building these smallest abundant RDGs.

If it is relatively easy to describe the minimal elements in RD_A(H), maybe it is possible to describe all of RD(H).  This has been done for graphs with two edges, and for the graphs H=P_3 and H=K_3 with three edges.  It has also been done for a few small paths and should be done for graphs with three or four edges.  Although describing RD(H) is somewhat easy for a few graphs (like H=K_3) this gets surprisingly difficult for other graphs (like H=C_4.)

Some graphs cannot create abundant RDGs.  This is true for the complete graphs, H=K_n, in which there are too many edges to allow one to build up RDGs that have "extra" copies of H.  Are there other graphs with this property?  Surely there are ... so can we classify, in some way, those graphs for which every RDG is trivial?

If H is connected then the graph aH, consisting of a components, each isomorphic to H, is in RD(H) and so the poset RD_0(H) is infinite.  But if H is not connected, then maybe RD(H) could be finite? When is RD(H) finite?  

I can argue that if H is the graph with three edges on five vertices, below,  formed from the path of length two and a disconnected edge, then RD(H)={H}!  (That graph, H = P_2 + K_1, is drawn below, using output from the Sage software program.)

For the student just beginning to explore RDGs: take a notebook and pen (or pencil) and draw a small graph H with three or four edges.  You might wish to choose one of the graphs drawn below.

Then begin constructing members of RD(H).  See if you can develop the first few members of RD(H) that involve 2, 3 or 4 copies of H.  Can you detect a pattern?  Can you make a statement about trivial or abundant graphs?  Drop me a line at kenwsmith54 (at) gmail (dot) com!

[Mathematical prerequisites: This article requires a basic introduction to randomly decomposable graphs (as seen in the previous  few blog posts).]

Follow Ken W. Smith on Twitter @kenwsmith54

Randomly decomposable graphs, II (concentrating on paths)

Abundant vs. trivial decompositions of a graph

In the previous post, we introduced randomly decomposable graphs, looking for the set, RD(H), of all graphs randomly decomposable with respect to a fixed graph H.

For example, if H is the path P_3, with four vertices and three edges, then there are five graphs, each with six edges which are in RD(H).  These five graphs include one disconnected graph, the graph which is two disconnected copies of P_3.  The four connected graphs are drawn below, with two edge-disjoint paths of length three drawn in different colors, one path in blue and another in red.  In each case, the removal of any path of length 3 leaves a path of length 3.

Note that although each of the graphs drawn above is clearly decomposable into two copies of P_3 (as indicated by the two colors, blue and red), there are LOTS more copies of P_3 in these graphs.  Indeed, the graph, C_6, on the left, has six copies of P_3, while the "bowtie" (second from the left) has (I think) eight copies of P_3, the complete graph K_4, third from left has six paths of length 3 and the rightmost graph (K_{2,3}) has 12.

Since there are so many copies of H in these graphs, it is not easy to show that these graphs are randomly decomposable.  On the other hand, if a graph G is constructed from  a  edge-disjoint copies of H and there are only  a  copies of H in G then the decomposition of G into copies of H is trivial.  For example, let us change H and set H to be the triangle (3-cycle) K_3, with 3 vertices and 3 edges.  Then the "bowtie" graph, above (second from the left), is trivially decomposable into copies of K_3 since it is the edge-disjoint union of  a=2 copies of K_3 and there are only two copies of K_3 in the graph.

If H has q edges and a graph G with e=qa edges decomposes into  a  edge-disjoint copies of H then we say G is trivially randomly decomposable with respect to H if there are only a copies of H in G.  If, instead, G has more than  a  copies of H, then we say that H is abundant in G.

The four graphs in the figure at the top of this blog all have H=P_3 as an "abundant" subgraph since  a=2 but there are, in each case, more than two copies of P_3.  On the other hand, if H=K_3, the bowtie graph is trivially decomposable since the two copies of K_3 used to construct the bowtie are the only copies of K_3 in the graph.

We make the distinction between trivial decompositions and abundant decompositions simply because we are not really interested in trivial decompositions.  We want an interesting problem.  The randomly decomposable graphs which are trivially decomposable are not interesting but the abundant graphs are.

The poset of randomly decomposable graphs and its trivial/abundant pieces

The set of finite graphs form a partially ordered set ("poset") ordered by the concept of subgraph. So the set RD(H) will also be a poset, with one member, G1, being less than another, G2, if G1 is a subgraph of G2.  It should be clear that this poset can be arranged by the height  a; at the bottom of the poset is H, immediately above H are the graphs which can be constructed from two copies of H; above those are the graphs constructed from three copies of H and so on.

If G1 is below G2 in the poset of randomly decomposable graphs (RDGs), then if G2 is trivially decomposable, so is G1.  The concept of "trivially" randomly decomposable is preserved by going down in the poset and so it is natural to ask if there are any maximally trivial RDGs.  These would be graphs which are trivially randomly decomposable but no graph above them is.

In a similar way, the concept of "abundantly" decomposable is preserved by going up the poset of RDGs, adding copies of H to graphs on a lower level.  If G1 is below G2 in the poset of RDGs, then if G1 is "abundant", so is G2.  Now H is trivial, not abundant, so given an abundant graph, we can always work ourselves down the poset of RDGs, removing a copy of H each time, until we reach a minimally abundant RDG, one which has no abundant subgraphs.  Thus minimally abundant RDGs sit at the cusp of "trivial" (uninteresting) RDGs and "abundant" (and complicated) RDGs.

Paths

We might begin our study of RDGs by beginning with the simplest graphs, the paths.  If P_n is a path of length n (and so has n+1 vertices and n edges) then what does RD(P_n) look like?  Since P_n is a connected graph, then if G is in RD(P_n), each connected component of G is also in RD(P_n) and so we can just concentrate on the connected members of RD(P_n).  There are only five connected members of RD(P_3).  They are:

The set RD(P_3) is then just a union of a finite number of copies of graphs from the set above. The four graphs on the left are of height 2; the rightmost graph is just H=P_3.  The poset RD(P_3) is infinite; a graph in that set is "abundant" if at least one of its components is from the first four graphs drawn on the left.  (Stated another way, a graph in RD(P_3) is "trivial" only if it is a disconnected union of copies of P_3.)

Below, off the webpage of Robert Molina (Alma College), in collaboration with Myles McNally (also at Alma) is a summary of all connected members of RD(P_4):

Since the number of edges in P_4 is even, there is an infinite set of connected graphs in which the paths are all joined in the middle.  This infinite set is represented by the three dots.

Here, from work of McNally & Molina, are the connected members of RD(P_5).  Note that this set is finite.  The first three graphs are predictable (to me) but the last two are rather strange. 

And here the connected members of RD(P_6).  Since the number of edges is even, we have some infinite families

but then a few more strange objects towards the end.

If H=P_7 then we have one infinite family (involving paths pinched at two points); we have the cycle and a figure eight ... and then ten more strange objects that would be hard to find without a computer.

H=P_8 is more of the same:

By the time our paths have 9 edges, the members of RD(P_9) are too many to draw here.  A few are given below.

All the members of RD(P_9) are available on the webpages maintained by McNally & Molina.  Picture of RD(P_9), RD(P_10) can be found at http://othello.alma.edu/~molina/rd(pk).html.  These graphs include collections of objects McNally & Molina call "braids", "twisted braids" and "branch growths."

And we have only begun looking at paths!!  What if H is more complicated?!

The Two-Path Conjecture

Along the way, as a number of us looked at RD(H) where H was a path, we began to believe that anytime we connected two copies of the path P_n, there were always additional copies of P_n created in that process.  No connected member of RD(P_n) of height two was trivial.  This eventually became a conjecture: 

The two-path conjecture.  Let G be the connected edge-disjoint union of two paths of length n. Then there are more than two copies of P_n in G.

With the help of Doug West and Herb Fleischner, we were able to prove that conjecture and publish the result.  (That paper is available here or here.)

and Erdos numbers

Many mathematicians encourage collaboration by keeping track of the "collaboration graph", in which two mathematicians are joined by an edge if they have collaborated on a published paper.  By tradition, the center of this collaboration graph is Paul Erdos.  It so happens that Doug West has Erdős number 1 so any other author of the paper on the Two-Path Conjecture has Erdos number 2. So I have Erdos number 2. (As it happens, I had earlier co-authored a paper with Allen Schwenk, who wrote a paper with Erdos, so I already had Erdos number 2.)

So ... if your Erdos number is higher than 3 (or does not yet exist!) you can get an Erdos number of 3 by publishing with me!  ;-)  Pick one of our open problems on one of these blogs, play with it a bit and write me an email.  Let's take a hike together in the mathematical wilderness!

Next time: RDGs, Part 3, some open questions in randomly decomposable graphs

[Mathematical prerequisites: This article requires a basic introduction to graph theory (as seen in the previous blog post).]

Follow Ken W. Smith on Twitter @kenwsmith54

Randomly decomposable graphs, I

The study of "randomly decomposable graphs" requires almost no mathematical background but can quickly lead to some interesting questions whose solutions require hard work and creativity.  I enjoy introducing this research area to students without a deep college math background.  Once the students become intrigued with this problem, they are ready to explore some other, deeper subjects!  (We will explore other, much deeper math topics in later blog posts.)

Edge decompositions of graphs

A graph, such as the cycle of 4 vertices, can be decomposed into two edge-disjoint copies of the path of length two.

This can be done is several different ways.

The bipartite graph K_{2,3} can be decomposed into three edge-disjoint copies of the path of length two.

But when we attempt to decompose this graph with six edges into three copies of the path of length two, we have to be careful how we do it.  If we start wrong, we may discover that we cannot finish the decomposition into three graphs all of which are paths.  For example, in the drawing below, we might remove the blue path of length two and then the black path of length two.  When we do that, we are left with the two reds edges which are not a path!

A general question in the decomposition of graphs begins with a fixed graph H and a larger graph G, where the edges of the graph G can be colored in such a way that each subgraph of a fixed color is isomorphic to H.  If H is the path of length two, all of the examples above give decompositions of a larger graph G into copies of H.

If the subgraph H has q edges then the number of edges in an H-decomposable graph G will be a multiple of q, say e=qa.  The integer a indicates the height of the graph G as a collection of copies of H.  The graph H, itself, has height 1; put together two copies of H to get a graph of height 2, and so on.  The cycle C_4 in the first drawing, above, has height 2 as a P_2-decomposable graph while K_{2,3} has height 3.

The theory of edge decompositions of graphs is a large field of mathematical research.  One may find it the subject of blog posts (here). There is at least one book (by ) published on the subject (which I found in my university library) and there is a study of infinite graphs and their simplicial decompositions (by Diestel).  A nice introduction to the subject is in this brief survey paper (pdf) by Fan Chung and Ron Graham.

Randomly decomposable graphs

If G is decomposable into edge-disjoints copies of a graph H then we say G is H-decomposable.  A partition of edges, each partition giving the subgraph H, is call an H-decomposition.

In 1985, the Chilean mathematician Sergio Ruiz dealt with questions about graphs decompositions which remain decompositions even when the target subgraph H is "randomly" (or "thoughtlessly") removed.  Given a fixed graph H, which graphs G are not just decomposable into copies of H but are decomposable in such a way that the decomposition cannot be "messed up".

For example, the cycle C_4 in the top picture is randomly decomposable into copies of H=P_2 while the bipartite graph K_{2,3} in the second and third pictures, is decomposable into copies of P_2, but is not "randomly" decomposable.  The third picture shows a decomposition which fails.

The formal definition of randomly decomposable is the following.  A graph G which is decomposable into copies of H is said to be randomly decomposable if the removal of the edges from any disjoint collection of copies of H leaves a graph which is still H-decomposable.  We say that G is an RDG with respect to H.

For example, if H=P_2 is the path of length 2 then the graph G=K_{2,3} fails the "randomly" decomposable requirement since if we remove -- in the third picture -- the black path 3-2-4 and the blue path 3-1-5, we get a graph which does not even involve a copy of H.  So also C_4 is RDG with respect to P_2, the graph K_{2,3} is not.

We can create a recursive definition equivalent to the one given above.  (The first definition, above, is due to Ruiz.)  The recursive definition defines the graph H to be "randomly" decomposable (of course) and then defines a graph G to be randomly decomposable if the removal of any copy of H leaves a randomly decomposable graph.  This recursive definition suggests that we construct randomly decomposable graphs beginning with graphs of low height and adding copies of H, checking the "randomly" condition as we go.

Let us construct graphs which are randomly decomposable with respect to H=P_2, the path with just two edges.  Pick a copy of H and label the vertices 1, 2 and 3 and assume the edges are {1,2} and {2,3} (so that H is the path 1-2-3.) Now take a second copy of H and assume the vertices are labelled a1, a2, a3 with a1 adjacent to a2 which is adjacent to a3. We may construct various P_2-decomposable graphs of height 2 by identifying certain vertices from the two copies.

First, if the vertices 1, 2, 3, a1, a2, a3 are all distinct, then the graph G is just two disconnected copies of H and so is clearly randomly decomposable.

If we identify the vertex 2 with the vertex a2 then we get the "star" with center 2 and end vertices 1,3, a1, a3.  This graph, often written K_{1,4}, is randomly decomposable.

If we identify the vertex 1 with a1 and the vertex 3 with a3, we instead get the 4-cycle drawn in the first figure. This graph is randomly decomposable.

One can consider other ways to put together two copies of H=P_2, but all of those choices lead to graphs which although decompose into copies of P_2, do not decompose randomly!  For example, if we just identify the vertices 1 and a1, we get a path 3-2-1-a2-a3 of length 4.  This graph is not randomly decomposable since we could remove the path 2-1-a2 and be left with a graph which is not isomorphic to H.

Randomly decomposable graphs where H is a path

When I first heard Sergio Ruiz speak on this topic, I thought it should be fairly easy to find all randomly decomposable graphs in which the subgraph H is a path.  But that turned out to be more complicated than I believed.  For example, suppose H is a path of length 7.  Then the graphs in the figure below are all RDG with respect to H.  And this is just height 2!!

I offer a brief exercise to test these RDG ideas, prior to my next post:

Find all graphs which are RDG with respect to the path of length 3 and have height two.  (Feel free to stop at height two, using just two copies of P_3.)  

I will give the solution to that exercise next time.

Next time: Randomly decomposable graphs, 2 (paths and related subgraphs)

[Mathematical prerequisites: This article requires a basic introduction to graph theory (as seen in the previous blog post).]

Follow Ken W. Smith on Twitter @kenwsmith54

Finite graphs, an entry point for undergraduate research

Many undergraduate research projects delve into areas of graph theory.  Graph theory is a relatively recent area of mathematical research, driven by questions in computing and computer algorithms.

A simple graph consists of a finite set V of vertices, along with a set E of edges, where edges are unordered pairs of vertices.  A simple example might be a set of five people {Alexus, Bernard, Chloe, Dazi, Emily} on Facebook; the set of edges here would represent (Facebook) friendship, so that if Alexus and Bernard were friends, {Alexus, Bernard} would be an "edge."

Finite graphs are the building blocks of discrete structures and their study has applications to modern technology, computer algorithms, discrete systems, ... any finite structures in the modern computer age. Anyone working with computer algorithms must have some understanding of graph theory!

"Simple" graphs have undirected edges (there is no direction to "friendship", it is presumably a symmetric relations) and there are no multiple edges (one can't be "friends" twice on Facebook!) and there are no loops (one is a "friend" of someone else, not oneself.)  Since these simple graphs were first systematically studied and promoted by Frank Harary at the University of Michigan, they are sometimes called Michigan graphs.

Here are the four different graphs with three vertices:

And here are the graphs on four vertices.

What makes two graphs "the same"?  This is a mathematical question about functions.  A graph on vertex set V_1 with edge set E_1 is isomorphic to ("the same as") another graph on vertex set V_2 with edge set E_2 if there is a one-to-one onto function (bijection) from V_1 to V_2 which maps the edge set E_1 onto the edge set E_2.  

Given a single graph with vertex set V and edge set E, a one-to-one function from V onto V is a permutation.  If the permutation maps E onto E, is is an automorphism of the graph.  Given a fixed graph G(V,E), the collection of automorphisms of the graph form a group of permutations.

There are a large number of interesting questions which can be posed about graphs, many of them surprisingly difficult.  A very old problem, dating from the 1800's, is the four coloring problem for planar graphs solved only by exhaustive computer search in 1976.  A more difficult problem (involving lots of active research) asks for an algorithm which distinguishes between different (non-isomorphic) graphs.  At this time there is no known list of graph invariants that is guaranteed to always separate two non-isomorphic graphs.

A graph has a collection of symmetries, that is, a group of automorphisms, which permute the vertices of the graph without changing the collection of edges.  The structure of this automorphism group says a lot about the structure of the graph; in a similar way, every finite group may be viewed as the automorphism group of some graph.  Many questions in finite group theory can be phrased in terms of interesting combinatorial structures such as finite graphs.  And, conversely, many interesting questions in graph theory lead to interesting questions in algebra, in group theory, ring theory and linear algebra.

Since graphs are finite and since it is relatively easy to create a list of examples, this is a fertile area in which to engage undergraduates in mathematical exploration.  Future posts will attempt to lay out some interesting research problems.

Next time: A project in randomly decomposable graphs.

[Mathematical prerequisites: This article requires no mathematics beyond high school.]

Follow Ken W. Smith on Twitter @kenwsmith54

A hike in the Himalayas (& directing undergraduate research)

A hike in the Himalayas

In the previous post I suggested six attributes of a good undergraduate research problem. I claimed that a good research problem for undergraduates

1. should be accessible,
2. has "legs",
3. leads to higher math,
4. dreams of mathematical heights,
5. uses "magic",
6. offers alternatives.

In this post I review those characteristics using a common metaphor.

I have never been to the Himalayas.  My wife and I used to backpack in the Colorado Rockies and so I've dreamed about seeing the Himalayas someday.  (Is this a "bucket list" goal?  Possibly.)  Suppose instead of just visiting the Himalayas, one were to truly explore the Himalayas -- not just hike on well-worn trails, but really go into the backcountry and find new trails to build, new peaks to climb, new rivers to raft!

What would this involve?  It would be good to have a guide, a person with local experience, who can suggests areas to explore and who has some understanding of the paths into the wilderness.

Now let's turn the story around.  Suppose that you are the local guide.  What does it take to give your visitor, your client, a good wilderness experience?

I will offer six characteristics of a good guide to the Himalayas.  (If I were to ever get an opportunity to truly explore the Himalayas, here is what I would expect my guide to be able to do.)  These six characteristics deliberately parallel the six characteristics of a good problem from the previous post.

Frankly, I know a lot more about finding good math problems than I do about hiking in the Himalayas.  Still, this is my blog and the Himalayas are my dream so....  (If one prefers a slightly different metaphor, imagine hunting for new snowboarding routes in the Grand Tetons.  Now there is some exciting "research"!)

A good guide meets the trekker client where they are and helps them acclimate

As you (the good guide) meet your trekker customer, you want to assess their abilities and help them acclimate to the mountains.  Begin with some small hikes as your guests adjust to altitude and to the hiking experience.  A good guide knows of nice hikes that are safe and part of a larger experience.  Of course, these hikes are not themselves explorations -- they are just serious walks in the mountains.  Many people have traveled these trails before.  But these introductory hikes set the stage for future exploration.

Be prepared for a serious expedition

As your hiking customer gains experience, he/she will want to do some serious exploration.  Be prepared to lead that trip.  Know the equipment necessary; have access to good resources; be ready to take healthy, energetic explorers deep into the wilderness.

Sure, there are other guides who can take people on enjoyable walks.  But your customers want to explore new territory.  You should have ideas on where to go and how to begin the trip and you should be ready to take them as far as they are capable of going.

Take your clients to interesting places

As you, the expedition guide, adjust to your customers, you want to show them some interesting sights.  It is not enough to hike ten miles somewhere, set up a tent, walk around for a few days and then hike back.  You want them to enjoy their experience and return again to the mountains.  So you should be able to say, "Beyond that ridge is a range of high peaks.  Let's climb that ridge and then see what might be reachable on the other side."

If this is a genuine expedition, you may not know what is on the other side, but you have some ideas.  There are some big mountains out there and so there are lots of interesting smaller ones!

Plan your trip so that your customers ooh and ahh at the scenes they encounter.

Even if you can't climb the top peaks, can we get good views of them?

I don't plan on climbing Mt. Everest.  But if I were hiking in the Himalayas, I would like one day to come around a corner and hear my guide say, "See, there, on the left, that faraway mountain with the plume?  That's Everest."

I've hiked in Colorado and I enjoyed the high peaks there.  So why go to the Himalayas?  Because of Everest.  I don't need to climb Everest myself, but that highest of all peaks draws thousands of visitors to Nepal every year, just so they can see it!

A good guide uses all available resources

Sherpa guides on Everest sometimes climb the mountain without access to fixed ropes or manmade bridges.  But if I have a guide in the Himalayas, I want him (her) to be able to guide me to bridges across ravines, bolted ladders up steep faces, any type of equipment that will help me get further into the wilderness.  As a visitor and guest, I need these manmade (magical?) aids and I hope my guide will not be shy about offering them.  (Indeed, I will surely need an occasional gasp from an oxygen tank, long before we reach even 20,000 feet in elevation!)

A good guide suggests offers alternatives

So I'm not climbing Everest.  But I'd like to climb some ridges and hills, maybe a smaller, gentler peak.  A good guide will have an idea where those are and how to get there.  As the hike goes on, the good guide will recognize the customers' abilities and limits and will be prepared to suggest alternate goals for the expedition.

Find a photo opportunity, a place where all of us can stand together, squeezed into a single frame and later say, "See, I was there!  [I didn't climb Everest but] I climbed this peak!"

"Climbing" the (a,b,c) order-of-products problem

Let's apply the last two posts (on good research problems and good hiking experiences) to the (a,b,c) order-of-products problem (posted Aug 26 & 29.)

The order-of-products problem begins with a simple question from geometrical symmetry or modular arithmetic.  These are ideas often taught in high school and certainly accessible to high school students.  So this problem has some nice entrypoints; there are good ways for undergraduate students to access this problem and acclimate to the mathematics needed.

The order-of-products problem leads fairly quickly to some elementary group theory and then seems to eventually require an understanding of group homomorphisms and subgroup structure, including Sylow Theorems.  It connects with Coxeter groups and groups of Lie type.  So it seems to lead to some interesting higher level problems.  In a search of the literature, I have not yet found any place where this problem is attacked in this generality, although there are places where versions of the problem have been solved.  So this problem seems to lead to some "high peaks" of mathematics and so should take researchers some distance.

I'm not aware of any big conjectures associated with the order-of-products problem.  I do not see an "Everest" on the horizon.   But this may be due to the fact that this problem is not directly in my area of research.  If I am to direct this problem further, I am uncomfortable with the fact that I don't personally know the tools used in creating finite groups.  Maybe I am not the best "guide" for this problem?  A better guide would probably know more about reflection groups, finite Coxeter groups and similar topics in group theory with a "geometric" flavor.

But I do see some smaller peaks; just the existence of triangle groups in hyperbolic geometry seems like an interesting "mountain range" to explore.  So, until better guides come along, I can take students for a good long walk in the mountains!

As students adjust to the order-of-products problem, they can use computer software (like GAP or Sage, which are free) and I am quite willing to give students "magical" results about simple groups and Sylow theorems.

All in all, the order-of-product problem seems like a good, but not great, problem for students.  This problem might be a good B level undergraduate research problem; if I am the director of this exploration, my lack of experience in the finite group theory probably puts the potential of this problem as a B- or C+.

Summary

Imagine breaking new trails across a secluded mountain valley, rafting an unexplored section of a river, or taking your snowboard down a virgin mountain slope.  That is exciting!  Every explorer, every wilderness guide, began as a novice enjoying smaller, safer trips.  Let's get our undergraduate students into short (mathematical) wilderness trips and see if they will catch on to the excitement of the mathematical quest.

Next time: Graph theory as one source for good undergraduate math problems.

[Mathematical prerequisites: This article requires no mathematics beyond high school.]

Follow Ken W. Smith on Twitter @kenwsmith54

Characteristics of good undergraduate research problems

Characteristics of good problems for undergraduates in mathematics

Directing research with undergraduate students in mathematics requires a good programmatic environment such as 

1. quality time with students, 
2. strong faculty mentors, 
3. institutional support,

etc.  But the foremost requirement is good research problems that undergraduate students can attack. 

Below I give six qualities of a good undergraduate research problem.  (Future posts will attempt to describe how to find these problems.)

I have directed mathematical research at the undergraduate level, at the masters level and at the doctoral level (supervising four doctoral students.)  Directing research with undergraduates is enjoyable but has a unique set of challenges.

A good research problem for undergraduates should be accessible

This is obvious.  Any research problem should be accessible to the researcher.  But mathematicians often underestimate the variety of good undergraduate research problems in their discipline.  A good research problem involves several good entrypoints, places where someone can begin their exploration and have some chance of early elementary success.  

It is an art to finding these good problems; after twenty years of directing research with undergraduate math students, I still struggle to gauge a good entrypoint and I often misjudge the difficulties students have getting into the problem.

In looking for good entrypoints, I often look for "toy" problems, smaller problems (possibly extended exercises) which are solvable and have a good chance of providing the intuition necessary for looking at deeper problems.  Questions about 2x2 matrices can provide intuition for questions in linear algebra or operator theory; questions about modular arithmetic or symmetries of polygons may provide intuition about questions in modern algebra or group theory; questions about finite graphs can lead to more sophisticated problems in combinatorics.

Students who use a computer software program to attack a good math problem will feel more comfortable exploring and making conjectures.  If there is a place for computers and mathematical software in your project, use them!

The difficulties of finding "toy" problems varies by discipline, but if one can explain the problem to an undergraduate audience (you can, can't you?) then one can probably find a small problem that generalizes to deeper questions in higher mathematics.  If the right problem is found, students will achieve success with the early toy problem and will then be hooked on the drug of mathematics by the time the problems get hard.  (By that point, in order to continue the mathematical high, the student will have no choice but to move on to the higher mathematics!)

A good research problems for undergraduates has "legs"

A good research problem is not a mere exercise or merely a reading project, but it has "legs", it runs ahead of the researchers, unraveling more and more mathematics.  It is the nature of mathematics that many questions have that effect; once begun, their solutions reveal a larger realm of inquiry.  Questions about the quadratic formula led into cubic polynomials and complex numbers; questions about Euclid's fifth postulate led into nonEuclidean geometry and eventually relativity; questions about constructible numbers led to field extensions; Fermat's Last Theorem led on to algebraic number theory and elliptic curves.

It is probably clear -- but should be stated -- that it will be easier to find problems with "legs" if the supervising professor already works in the research area and has considerable experience with related problems.  (It is hard to direct research if one is not already active in research!)

Good research problems for undergraduates lead to higher math

This remark parallels the last one.  Along with a good problem that runs ahead of the researchers, leading to more open questions, a good research problem for undergraduates should begin to provide a glimpse of previously unknown realms of mathematics.  The bright undergraduate who says, "Yeah, I know all about matrices!" should get a glimpse of operators on infinite dimensional vector spaces or be given the opportunity to play with linear algebra over finite fields or p-adic rings.  

A major goal of undergraduate research should be to open the students' minds to the truly wild nature of higher mathematics.  If done well, the undergraduate will respond by wanting to go a little further and explore one small piece of that wilderness.

Good research problems for undergraduates dream of mathematical heights

I find it useful to have a "dream" result or open conjecture that I want the students to see.  It may be faraway, off on the horizon, but maybe we could get close to that result?  Probably not... but ... the students should realize that there are some BIG problems nearby that no one has solved.  

If you are hiking in the Himalayas, don't you want to at least see Mt. Everest on the horizon?  

Students working in posets of graphs might ask, "How does my work relate to the famous Graph Reconstruction Conjecture?"  Students working in difference sets or circulant matrices should understand the statement of the Circulant Hadamard Conjecture.

By getting a chance to dream about proving a BIG result, students glimpse a large profession devoted to exactly these ideas; they see a profession reaching out for hard problems and attacking them.

It is good for my students to see themselves following in the tradition of Euler, Gauss, Hilbert, von Neumann...

A good research problem for undergraduates uses "magic"

I use "magic" here to mean a result given to a student without proof or defense.  

Most mathematicians visualize mathematics as developed linearly, an edifice of axioms, lemmas, theorems, proofs.  This is true.  But in this philosophy, we sometimes forget that we can discuss a field of mathematics without uncovering every prerequisite concept.  A colleague may shake his head and say, "You cannot discuss finite fields until students have had at least one higher algebra class."  Or "operator theory cannot be taught to undergrads."    I disagree.

I understand (and I teach) the axiomatic development of mathematics but it is OK if occasionally one says, "We will use the following result whose proof is beyond the scope of this course."  Skip some of the prerequisite concepts; provide some results as "magic" and move on!

When directing projects in difference sets, I briefly describe group representations (to a student who has had higher algebra) but I claim Maschke's theorem as a piece of magic ("Trust me!")  I make similar statements about the sums of squares of degrees of irreducible representations.  I provide some computational tools, without defense, and my students use them successfully.

Feel free to provide "magical" useful results to your students, without defense.

One advantage of "magical" results (besides its practical aspects directing undergrads) is that a curious student may eventually ask you to "backfill", to go back and prove parts of the magic.  If done at the appropriate later moment, this can be a good experience since the student is now highly motivated to understand that piece of magic.

A good research problem offers alternatives

So your students won't climb Mt. Everest -- or prove the Graph Reconstruction Conjecture. But are there some other smaller summits they might be able to reach?  If so, hold that out in front of them, as motivation when the going gets rough.  "Yes, Mt. Everest is still 100 miles away. But that ridge over there, across the valley, looks very interesting and I bet if we got to that ridge, we would have an awesome view!"  Tired hikers in the mathematical mountains might be willing to go just a little further if they can see a nearby ridge to top, a nice small result to solve.  Find some good partial results that you can direct your students towards, as the project winds down.

Next time: Friday's post will compare tackling a good research problem with a walk in the woods (or a hike in the Himalayas.)

[Mathematical prerequisites: This article requires no mathematics beyond high school.]

Follow Ken W. Smith on Twitter @kenwsmith54