Sagetex: Random Bipartite Graphs

RandBiSummer's here and I've had the luxury to just play around. I try to put extra math into the curriculum through either warm up problems, extra credit problems, or examples in the  curriculum that I follow. Discrete math figures prominently in the extra math. In my opinion, discrete math deserves a prominent place in the high school curriculum; it certainly deserves a bigger share of the curriculum. But in a top down system you can't add extra material to the curriculum that the average math teacher has never seen and expect it to be implemented properly.

Graph theory is ideal because it requires little mathematical background to understand and solve problems yet it also provides a way to introduce theorems (many of a basic nature that high school students can understand) along with counterexamples thereby providing a basic primer into the sort of considerations that mathematicians are looking at. In the past, geometry had been the topic for introducing proofs but it's dry as dust and now common core has ripped out much of the proof content so that your typical student can go through math and with very limited exposure to theorems/proofs/counterexamples.

Graph theory would be a way to get that back in a way that is much more interesting than the dry "2 parallel lines are cut by a transversal" proofs that have bored generation after generation. You can even connect to matrices through the adjacency matrix of a graph. Topics like recurrence relations and generating functions complement the curriculum of calculus (power series) and probability. Unfortunately, common core has de-emphasized proofs and matrices and upped the exposure to statistics, so I think it's my duty to undue the damage of the curriculum.

Which brings us back to the current post. Bipartite graphs which have the same number of vertices in each partite set provide a way of determining whether a suitable job can be found for each person so that everyone has a job (see the "Matching" section for the link above). One partite set with vertices, say, A,B,C,D have edges to the other partite set of vertices (a,b,c,d) representing jobs based on whether the person is qualified to do the job. The question becomes, Is there an assignment of jobs so that everyone has a job they're qualified to do? If yes, then there is a (perfect) matching for the graph. If no then there needs to be an explanation as to why no such assignment is possible (Hall's Marriage Theorem).

As a teacher the problem I usually face is finding lots of examples that can be used in the classroom or on a test/quiz. Sage/sagetex is the tool that works best for me. The code generates bipartite graphs so that the number of vertices in each partite set is equal and the probability of an edge being selected for the picture is 1/2.  The code is posted on the Graphics page along with sample output (the PDF shown above). The number of vertices is a random number set between 4 and 8 here: N = Integer(randint(4,8)). The probability of the edge being chosen is set here: if Integer(randint(0,1))==1:

It would be relatively simple to choose a larger number than 1, such as 9, and draw the edge if the number chosen is between 0 and 7 but don't draw the edge if the number chosen is 8 or 9. That would make the probability of the edge appearing to be 80%.

Through setting the parameters to your liking and repeatedly compiling the code you can generate many examples that you can use. If you're particularly ambitious you can add extra code spit out example that have (or fail to have) a perfect matching. Of course, Sage can help with that.

Odds and Ends: July 1, 2014

FlowChartA few minor changes:

  1. I've added the flowchart/tree diagram (PDF and tex file) to the Graphics page. When talking about linear systems I've found students slow to pick up the vocabulary of consistent/inconsistent and dependent/independent. The flow chart helps students to remember the difference.
  2. The important graph from the last post, has been posed as a problem: Find the derivative of f(x)=x^2\sin(1/x^2) if x \neq 0 and f(0)=0 at 0. I think it would be well suited as a warm up problem at the beginning of class to motivate the subsequent discussion.
  3. The NY Times has a good article on the difficulties with Common Core.

A very important graph

SinIx2sinEveryone studying mathematics needs to know some typical functions and some important characteristics. At the lowest level you need to know the trig functions and their (as applicable) domain, asymptotes, midlines, periods, etc and for exponentials and logarithms you should know the domains and asymptotes. At a slightly more advanced level, students should be aware of the  function \frac{\sin(x)}{x} and how its limit exists at 0 (and is equal to 1) even though the function isn't defined there. Or that x\sin(1/x) is a function whose limit at 0 exists and can be determined using the Squeeze Theorem. The graph show above is also a function that needs to filed away but, surprisingly, it isn't well known. I say that because I have trouble finding it in a typical calculus text (or the lesson it teaches). That's a shame; the function is f(x)=x^2\sin(1/x^2) if x \neq 0 and f(0)=0.

Take the derivative and you'll get f'(x)=x\sin(1/x^2)-(2/x)\cos(1/x^2). And the derivative at 0? Chances are overwhelming that your students will say the derivative doesn't exist at 0 because f'(0) isn't defined. But that's wrong. That won't be apparent by looking at the graph of the derivative:DSinIx2sinFor the typical students who dive for a calculator so they can avoid thinking for themselves, they'll get to see that the calculator isn't going to help out here. They'll have to use the definition of the derivative (and the Squeeze Theorem). That's good practice. Ultimately this function shows that derivative can exist at a point even if the formula $f'(x)$ doesn't exist there. For all these reasons, this graph should appear in every calculus book.

The PDFs have been posted on the Graphics page.

Sagetex: Combinatorics/Probability (8/9)

Comb8I've added 2 more problems to the Sagetex: Combinatorics/Probability page. The problem above has the form:

A high school committee of 6 is to be made from 32 boys and 41 girls. Within this set of students there are 2 senior boys and 3 senior girls. How many committees of 3 boys and 3 girls are there that contain at least one senior boy and one senior girl?

It's worth noting an interesting aspect of this problem: in order to properly count, the various cases need to be listed and this means the output of the solution will be dynamic in the sense that the number of cases to be listed changes in the solution will change depending on our specific number of senior boys and girls. In the case of 2 senior boys and 3 senior girls we need to throw out committees with

  • no senior boy and no senior girl
  • no senior boy and 1 senior girl
  • no senior boy and 2 senior girls
  • no senior boy and 3 senior girls
  • no senior girl and 1 senior boy
  • no senior girl and 2 senior boy

Change the number of senior girls or senior boys and that list given in the solution changes.

The output of the various cases is handled in the sagesilent block. We need to avoid counting no senior boy and no senior girl twice, so no senior boy and no senior girl is calculated here:

NoSeniors = binomial(girls-Sgirls,3)*binomial(boys-Sboys,3)

and 2 FOR loops create the rest of the cases. Here the committees with 0 senior girls are all created

for i in range(1,Sboys+1):
output += r"$0$ senior girls and $%s$ senior boys: $C(%s, 3)\cdot C(%s,%s)\cdot C(%s,%s)$\\"%(i,girls-Sgirls,Sboys,i,boys-Sboys,3-i)
remove += binomial(girls-Sgirls,3)*binomial(Sboys,i)*binomial(boys-Sboys,3-i)

A similar loop handles 0 senior boys. Note that 3 is hard coded. That's the number of girls (and boys on the committee).  Increasing that number will make too many cases to enumerate for a test. Likewise

Sboys = Integer(randint(2,3))
Sgirls = Integer(randint(2,3))

keeps the problem size more reasonable as well; 6 cases is enough and, depending on the ability of your class, it might be more appropriate to decrease the number of cases; i.e., make the hard coded 3 a two.

Sagetex: Combinatorics problems (6/7)

Comb6I've added 2 more problems (along with the solution) to the collection of randomized problems on the Sagetex:  Combinatorics/Probability page. The two new problems have the following form:

Problem Type 6: A committee will be made from 5 English teachers, 3 math teachers, and 4 history teachers. If the committee must have 2 teachers from different disciplines then how many committees are there?

Problem Type 7: How many nonnegative integers less than 100000
contain the digit 5?

Handouts: Notes on Induction

InductionNotesI've added some notes on weak and strong induction; they're posted on the Handouts page. The notes are a stripped down version that you'll need to flesh out. While I've given a motivation, definitions, example problems, and then an assortment of problems, I've left out a lot that you'll probably want to fill in. A high school level induction to induction shouldn't be the clean sanitized version you'll find in the notes; it should include the process of getting to the answer. That is, rather than present the proof as given in the examples, I would explain the scratchwork that gets you to the answer which is then cleaned up into the final version given in the notes.

The notes are a hack of the LeGrand Orange book template to 1. Get an article version 2. change the color 3. add green and red boxes to highlight information.

The large assortment of problems contains problems of varying difficulty so you'll need to work them out to decide what level is best for your students.

Odds and Ends: June 1, 2014

Several items of interest to report:

  1. Stockfish has won the TCEC Unofficial world computer chess championship by 35.5 to 28.5
  2. Game 18 of from the TCEC match showed brilliant play by Stockfish. You can watch the video here. That's a world class game that any grandmaster would be proud of.
  3. An interview with Kasparov regarding his running for the president of FIDE.
  4. Wired reports that somebody trademarked \pi. and is filing cease and desist orders for people using \pi --- see the difference? Geeks of the world are up in arms.

Two "easy" problems

Another year is almost over and of all the memorable events 2 problems (which aren't particularly difficult) caused tremendous difficulties for far too many students. It's especially surprising because I have a class of (mostly) good students: some are highly gifted and others compete for (and win) various math contests.

Problem 1: Solve for x\pi^{1-x}=e^x

Problem 2: Find the domain of f(x)=\sqrt{4x-x^2}

Problem 1 is from a Thai entrance exam; the Thai version of an SAT test. I put it on a regular test expecting to challenge the bottom 25% of the class. Instead, it took down the "bottom" 75-80% of the class and some good students blanked on it. If you work it out, you'll see there are multiple ways to do it and none of them are particularly difficult. The exponent 1-x (as opposed to, say, x-1) combined with x on both side poses problems, even for "good" students. The second problem was actually part of a problem on finding the minima and maxima of the function. It was causing difficulties during the problem session in class so I tried to break the problem into pieces and have them get the domain. You could count the students who could get the correct answer on a mutilated right hand. And I even told them that inside the square root was a parabola....

As a result, I've added these two problems to the Problems page. Try them on your students!

LaTeX Templates

LeGrandBookChances are, if you use LaTeX, you were probably drawn to it by some of the many beautiful examples that have been created. Everything looks better with LaTeX.  Lately I've been looking at various templates  to make my work look a little more polished; whether it's a book template (such as LeGrand Orange shown above), CV, article, Beamer presentation, or thesis it's good to have some templates on hand. I've added information on the LaTeX page to get you started. In addition to several sites with a good variety of templates to look at, I've listed some of my personal favorites as well.

Understanding "The Prediction"

PredictionMath Awareness Month is over and if you haven't kept up with the website, you can check out the different videos that they posted throughout April here. My favorite video was posted on the April 5th: "The Prediction" by Richard Wiseman. In case there's a problem with the mathaware website being taken down, here's the link to the video on Wiseman's Quirkology site. I enjoyed the video enough that I've put together an explanation of the math behind it; it uses the fact that the graph of the moves is bipartite. You can read the details in the PDF (screenshot above). It's posted on the Other page.