Archives For combinatorics

On October 12th, I saw a post by Dan Christensen on Google+ about a list of five open problems posed by the mathematician John Conway that have monetary rewards associated with them. In particular, Conway is offering $\$1,000$ for solutions (either positive or negative) to any of the problems. Here are the five problems (as stated by Conway):

  • Problem 1. Sylver coinage game (named after Sylvester, who proved it terminates): The game in which the players alternately name positive integers that are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so ending the game) is the loser. The question is: If player 1 names 16, and both players play optimally thereafter, then who wins?
  • Problem 2. 99-Graph: Is there a graph with 99 vertices in which every edge (i.e., pair of joined vertices) belongs to a unique triangle and every nonedge (pair of unjoined vertices) to a unique quadrilateral?
  • Problem 3. The Thrackle Problem: A doodle on a piece of paper is called a thrackle if it consists of certain distinguished points called spots and some differentiable (i.e., smooth) curves called paths ending at distinct spots and so that any two paths hit once and only once, where hit means having a common point at which they have distinct tangents and which is either an endpoint of both or an interior point of both. The right hand figure shows a thrackle with six spots and six paths. But can a thrackle have more paths than spots?
  • Problem 4. Dead Fly Problem: If a set of points in the plane contains one point in each convex region of area 1, then must it have pairs of points at arbitrarily small distances?
  • Problem 5. Climb to a Prime: Let $n$ be a positive integer. Write the prime factorization in the usual way, e.g., $60 = 22 \cdot 3 \cdot 5$, in which the primes are written in increasing order, and exponents of 1 are omitted. Then bring exponents down to the line and omit all multiplication signs, obtaining a number $f(n)$. Now repeat.So, for example, $f(60) = f(22 \cdot 3 \cdot 5) = 2235$. Next, because $24235 = 3 \cdot 5 \cdot 149$, it maps, under $f$, to 35149, and since 35149 is prime, it maps to itself. Thus, $60 \to 2235 \to 35149
    \to 35149$, so we have climbed to a prime, and we stop there forever. The conjecture, in which I (Conway) seem to be the only believer, is that every number eventually climbs to a prime. The number 20 has not been verified to do so. Observe that $20 \to 225 \to 3252 \to 223271 \to \cdots$, eventually getting to more than one hundred digits without yet reaching a prime.

If you solve one of these, you can reach Conway by sending snail mail (only) in care of the Department of Mathematics at Princeton University.

Around the same time that I stumbled onto these problems, I was brainstorming ideas for a couple of upcoming talks that I was slated to give (one for undergraduates and one for high school students). I decided that discussing open problems with monetary rewards with an emphasis on Conway’s problems would likely make for a nice talk. Here is the abstract that I settled on for both talks.

There is a history of individuals and organizations offering monetary rewards for solutions, either in the affirmative or negative, to difficult mathematically-oriented problems. For example, the Millennium Prize Problems are seven problems in mathematics that were stated by the Clay Mathematics Institute in 2000. A correct solution to any of the problems results in a $\$1,000,000$ prize being awarded by the institute. To date, only one of the problems has been solved (the Poincaré Conjecture was solved by Grigori Perelman, but he declined the award in 2010). These are hard problems! The renowned mathematician John Conway (Princeton) maintains a list of open problems and for each problem on the list, he is offering $\$,1000$ to the first person that provides a correct solution. In this talk, we will explore a few of Conway’s problems, and in the unlikely event we come up with a solution, we’ll split the money.

On Friday, October 24, 2014, I gave a talk during the Friday Afternoon Mathematics Undergraduate Seminar (FAMUS) at NAU. Speaking at FAMUS is always fun and my talk seemed to be well-recieved.

After having a practice run during FAMUS, I was able to improve the slides I intended to use during my talk at the 2014 NAU High School Math Day, which took place a few days later on Tuesday, October 28, 2014. Here are my slides:

I had a blast presenting to the high school students. It cracked me up that there were a few students that immediately started obsessing over the Sylver coinage problem and likely didn’t hear a word I said after that. My goal was to give an engaging and high energy talk. I also slid in some humor and I was happy that everyone laughed when they were supposed to. Interestingly, the thing I said that the students thought was the funniest was something that I didn’t intend to be humorous. When I stated that “If you solve one of these, you can reach Conway by sending snail mail (only) in care of the Department of Mathematics at Princeton University,” the audience burst into laughter. Requiring snail mail seemed so ridiculous to them, they thought it was a joke.

As a side note, I used mtheme (available for free on GitHub) together with beamer/LaTeX to generate my slides. I’m really happy with the look of mtheme and thrilled to get away from the standard beamer themes.

A simplified structure diagramMy colleague Nandor Sieben and I recently submitted for publication a paper titled “Impartial achievement and avoidance games for generating finite groups.” The current arXiv version of the article is located here. My typical pure mathematics research interests are in the combinatorics of Coxeter groups and their associated algebras, so while I have a background in group theory and combinatorics, this was my first research experience in combinatorial game theory. In fact, prior to working on this project, I knew next to nothing about the subject. In the year and a half we worked on the project, I learned a tremendous amount of new material, which was a lot of fun. It was exciting to branch out and try something new.

Here is the abstract for the paper:

We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.

The fundamental problem in the theory of impartial combinatorial games is the determination of the nim-number of the game. This allows for the calculation of the nim-numbers of game sums and the determination of the outcome of the games. The major aim of this paper is the development of some theoretical tools that allow the calculation of the nim-numbers of the achievement and avoidance games for a variety of familiar groups. In the paper, we introduce the structure diagram of a game, which is an identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple but intuitive visualizations of these games that capture the complexity of the positions. By making further identifications, we obtain the simplified structure diagram of a game, which is our main computational and theoretical tool in the paper.

We developed a software package that computes the simplified structure digraph of the achievement and avoidance games. We used GAP to get the maximal subgroups and the rest of the computation is implemented in C++. The software is efficient enough to allow us to compute the nim-numbers for the smallest 100,000 groups, which includes all groups up to size 511. The result is available on our companion web page.

In April of 2013, I gave two talks at the University of Nebraska at Omaha that introduce the two games that this paper is about, but did not elaborate on the nim-number aspect. I summarized those talks in this blog post.

A couple months ago, my colleague Jeff Rushall and I co-applied for a Center for Undergraduate Research in Mathematics (CURM) mini-grant to fund a group of undergraduate students to work on an academic-year research project. Jeff and I had both individually applied in the past, but neither of us were successful in our proposals. If you are interested, you can take a look at my previous proposal by going here. Jeff and I are both passionate about undergraduate research and work well together. We decided that a joint application would likely be stronger than two individual proposals. I’m happy to report that we recently found out that our proposal was funded. We’re thrilled!

Here are a few more details. For the upcoming project, we recruited a diverse group of 7 talented undergraduates: Michael Hastings (one of my current research students), Emily White, Hanna Prawzinsky, Alyssa Whittemore, Levi Heath, Brianha Preston, and Nathan Diefenderfer. Students are expected to spend ten hours per week during the academic year working on the research project. In return, each student will earn a $\$3000$ stipend. Money from the grant will also be used to buyout a single course for both me and Jeff. In addition, Jeff and I will team-teach a topics course each semester that will include our research students but will also be open to other interested students. CURM will cover most of the travel expenses for Jeff and I to attend the Faculty Summer Workshop at Brigham Young University (BYU). CURM will also cover most of the travel expenses for the nine of us to attend the Student Research Conference at BYU.

A collaborative research program has many advantages over operating several disconnected projects, as Jeff and I have done in the past. One of our goals is to build a self-sustaining research group. Ideally, this group will consist of students at different stages of their education, each participating for multiple years. The opportunities afforded by a CURM mini-grant will provide a catalyst for our endeavor in several ways. First, the visibility of a student research group with a CURM mini-grant will help our department recruit mathematically inclined students. NAU has many such students, but some are enticed by existing research groups and grants in our science programs. Second, we would like to take advantage of the mentoring and training the CURM program provides for faculty. One weakness in my past projects is getting students to finish writing up their results for publication. I am hopeful that my involvement in CURM will help remedy this. Third, we believe that the stipend money will enable our students to forgo some of their part-time work and instead devote their time to mathematics. Lastly, we want to use the experience as a stepping stone towards obtaining an externally funded REU program.

Next year’s research project involves “prime labelings of graphs,” which is outside my typical research interests. Jeff and I believe that we have found a project that is accessible to undergraduates yet rich enough that we won’t even come close to running out of stuff to do. I’m really looking forward to branching out and exploring something new.

If you are interested, here is the project description that we submitted.

Project Description

This research project is motivated by a conjecture in graph theory, first stated in a 1999 paper by Seoud and Youssef [1], namely:

All unicyclic graphs have prime labelings.

This is a viable choice as a research problem for undergraduates because it is interesting yet accessible, in large part due to the minimal amount of background information required. To wit, a unicyclic graph is a simple graph containing exactly one cycle. An $n$-vertex simple graph $G$ with vertex set $V(G)$ is said to have a prime labeling if there exists a bijection $f: V(G) \to \{1, 2, 3, \ldots, n\}$ such that the labels assigned to adjacent vertices of $G$ are relatively prime.

As discussed in Gallian’s “A Dynamic Survey of Graph Labeling” [2], many families of graphs have prime labelings; the “simpler” types of unicyclic graphs that are known to have prime labelings include cycles, helms, crowns, and tadpoles. The goal of our project will be to discover additional classes of unicyclic graphs with prime labelings, in hopes of bringing the aforementioned conjecture on all unicyclic graphs within reach. The families of graphs we will investigate include, but are not limited to:

  1. double-tailed tadpoles, triple-tailed tadpoles, etc.;
  2. irregular crowns (crowns with paths of different lengths attached to each cycle vertex);
  3. unicyclic graphs with one or more trivalent trees attached to cycle vertices;
  4. unicyclic graphs with one or more complete ternary trees attached to cycle vertices; and
  5. unicyclic graphs with a specified number of non-cycle cubic vertices.

Seoud and Youssef have established necessary and sufficient conditions for some graphs to have prime labelings, but they are somewhat limited in scope. Seoud has also published an upper bound on the chromatic numbers of prime graphs. These and other results may be beneficial to our students as their research project progresses.

Ernst and Rushall have already made some progress on these specific cases. We will use these initial results as a starting point with our team of students. More precisely, the 7 students involved in this project will attend a 3-credit research seminar during both semesters of the 2014-2015 academic year. Ernst and Rushall will team-teach the seminar, but eventually the students will play an equal role in leading discussions, presenting research results, etc.

Our recent experience with Seoud’s Conjecture has indicated that this problem is ripe with potential and highly appropriate as an undergraduate research project. The students can begin productive work in a single afternoon, and yet we anticipate the students producing original results worthy of publication in refereed journals by the end of the academic year. Moreover, there appear to be a virtually unlimited number of families of graphs to investigate, which will hopefully lead to a sustainable research program for undergraduates in future years.

The 7 students we have recruited to work on this research project are mathematics majors in our department. In addition, they all have very good academic records, and have proven themselves to be hard-working, reliable and creative students in previous courses that we have taught, including vector calculus, linear algebra, abstract algebra, foundations, discrete mathematics and number theory. These students regularly attend our weekly departmental undergraduate seminar, so they are familiar with the rigors associated with research and are motivated to investigate deeper problems in mathematics.

It should be noted that several presentation venues (departmental, university-wide, as well as regional conferences) will be exploited to allow our students an opportunity to showcase their efforts during the 2014-2015 academic year.

References

[1] M.A. Seoud and M.Z. Youssef, “On Prime Labeling of Graphs,” Congressus Numerantium, Vol. 141, 1999, pp. 203-215.

[2] J.A. Gallian, “A Dynamic Survey of Graph Labeling,” The Electronic Journal of Combinatorics, Vol. 18, 2011. http://www.combinatorics.org/Surveys/ds6.pdf

On Tuesday, February 5 (my birthday!), I gave a talk titled “A diagrammatic representation of the Temperley-Lieb algebra” in the NAU Department of Mathematics and Statistics Colloquium. Here is the abstract.

One aspect of my research involves trying to prove that certain associative algebras can be faithfully represented using “diagrams.” These diagrammatic representations are not only nice to look at, but they also help us recognize things about the original algebra that we may not otherwise have noticed. In this talk, we will introduce the diagram calculus for the Temperley-Lieb algebra of type $A$. This algebra, invented by Temperley and Lieb in 1971, is a certain finite dimensional associative algebra that arose in the context of statistical mechanics in physics. We will show that this algebra has dimension equal to the nth Catalan number and discuss its relationship to the symmetric group. If time permits, we will also briefly discuss the diagrammatic representation of the Temperley-Lieb algebra of type affine $C$.

And here are the slides.

Despite the fact that this was a 50-minute talk, it was intended to be an overview of one aspect of a long and complex story. The subject matter is intimately related to my PhD thesis, as well as a series of papers that I have written.

  • Ernst, D. C. (2010). Non-cancellable elements in type affine $C$ Coxeter groups. Int. Electron. J. Algebra, 8, 191–218. [arXiv]
  • Ernst, D. C. (2012). Diagram calculus for a type affine $C$ Temperley-Lieb algebra, I. J. Pure Appl. Alg. (to appear). [arXiv]
  • Ernst, D. C. (2012). Diagram calculus for a type affine $C$ Temperley–Lieb algebra, II. [arXiv]

In addition, there is (at least) a part III that goes with the last two papers that is in progress.

On Friday, September 12, 2012, I gave a 25 minute talk titled “An open problem of the symmetric group” during NAU’s Friday Afternoon Mathematics Undergraduate Seminar (FAMUS). Here is the open problem that I discussed.

How many commutation classes does the longest element in the symmetric group have?

The main goal of the talk was to understand what this question is asking. The secondary goal was to illustrate that mathematics is a lively field with open questions and to provide an example of what research in mathematics looks like. Here’s the abstract.

Many people are often surprised to hear that mathematicians do research. What is mathematical research? Research in mathematics takes many forms, but one common theme is that the research seeks to answer an open question concerning some collection of mathematical objects. The goal of this talk will be to introduce you to one of the many open questions in mathematics: how many commutation classes does the longest element in the symmetric group have? This problem has been nicknamed “Heroin Hero” by my advisor in honor of a game from the TV show “South Park” in which the character Stan obsesses over chasing a dragon. We will review the basics of the symmetric group and introduce all of the necessary terminology, so that we can understand this problem.

Here are the slides.

This semester I am teaching a course for freshman mathematics majors.  The course is called Introduction to Formal Mathematics.  One purpose of the course is to develop a tight-knit cohort of mathematics majors and another purpose is show them that mathematics is about more than “solve for $x$.” We do some problem solving, a little proof writing, and introduce them to a few topics they may or may not see in future courses.  The course is a lot of fun. Feel free to check out the course webpage.

The last couple weeks we have been doing a little combinatorics and some graph theory. Today one of the students remarked something to the effect, “I liked math before, but this stuff is just so cool.”  I agree.  There is no reason why we couldn’t teach these topics to high school students or even middle school students.  Unfortunately, we are too obsessed with trying to make sure students pass standardized tests and can take calculus in high school.