#MathStatMonth Day 30: Max-Flow Min-Cut

At the end of my post about snarks, I mentioned network flow problems. The most famous network flow theorem is the Max-Flow Min-Cut Theorem, which tells us about the maximum possible flow from a source to a sink. Continue reading

Advertisements

#MathStatMonth Day 29: Periodicity and Chaos

There is a famous paper in the field of dynamical systems titled “Period Three Implies Chaos.” The result in this paper by Li and Yorke is actually stronger than the statement in the title, but that’s the cleanest and flashiest part.

The systems the paper considers are difference equations. We can think of measuring some quantity x at discrete points in space or time. I’ll use time here for simplicity. This could track things like a population in an ecosystem, the position of an object, or the concentration of some part of a solution. Continue reading

#MathStatMonth Day 28: Snarks

You may seek it with thimbles — and seek it with care;
You may hunt it with forks and hope;
You may threaten its life with a railway share;
You may charm it with smiles and soap…
From Lewis Carroll’s “The Hunting of the Snark”

A snark (of the mathematical variety, at least) is a type of graph that comes up in a number of important questions in graph theory but about which we know relatively little. We don’t even know of many examples of snarks beyond a couple of infinite families. Continue reading

#MathStatMonth Day 25: 2-Factorable Graphs

In graph theory, we’re often interested in breaking graphs up into certain types of pieces. Maybe we’re thinking of a circuit as a graph, and we want to break the wires/graph edges up into layers so that edges within the same layer don’t cross. Maybe we want to use a graph to model matching applicants to jobs, so we want to find sets of edges that assign each applicant to exactly one job and each job to exactly one applicant.

One way to break up a graph that I used in graph labeling research is the 2-factorization. When we factor a graph, we split it into subgraphs such that in each subgraph every vertex is connected to some edge. This type of subgraph is called a spanning subgraph; it spans all the vertices. A 2-factorization of a graph is one in which all the spanning subgraphs, or factors, are sets of cycles. Continue reading

#MathStatMonth Day 24: How Many?

Happy book birthday to Christopher Danielson and How Many?: A Counting Book! I’m a big fan of Danielson’s previous book, Which One Doesn’t Belong?, and I’ve been looking forward to How Many? since it was announced.

I’ve loved all the #unitchat discussion on Twitter for the past couple of years, and that’s exactly what this book is about. In most images, there are many things you could count. Take the cover photo. I see one half-apple, five seeds, and six holes. Asking simply “How many?” leaves room for people to count what they want, to make decisions in their counting. It also highlights the importance of units in a natural way.

I’m particularly eager to read the teacher’s guide. The Which One Doesn’t Belong? teacher’s guide was full of great anecdotes, and it helped me to better understand the sense of the main book, why it was constructed as it was. I expect the How Many? guide to do the same. There’s also a story in the How Many? guide that Danielson mentioned in response to some thoughts I had about dance, math, and sensemaking, so I’m particularly excited for that.

#MathStatMonth Day 23: Minimally Marked Rulers

Last week, Simon Gregg tweeted a couple of images of Golomb rulers. A Golomb ruler is a ruler with marks at integer positions such that distances are measured uniquely. In other words, no two pairs of marks are the same distance apart.

Today, Christopher Danielson tweeted about a different kind of minimally marked ruler. He wanted to use the minimum number of marks possible to measure all the distances from 1 to n on an n-unit ruler. So here, duplication of distances is fine, but all possible distances must be measurable.

For most n, it’s not possible to make a Golomb ruler that also measures all possible integer distances. For example, Danielson was looking at 12-unit rulers. We were able to show that five marks wasn’t enough to measure all distances 1 to 12 because five marks only result in ten pairs of marks, so one could only measure ten distances. That meant he had to use six marks, but six marks create fifteen pairs of marks and thus fifteen distances. A 12-unit ruler with six marks will then necessarily duplicate some distances.

There are some n where a Golomb ruler that measures all the distances could be possible, though. In particular, if n is a triangular number, then the number of pairs of marks would be exactly equal to the number of desired distances. But that doesn’t mean that it’s actually possible to choose marks to make such a perfect Golomb ruler, though. I decided to investigate. Continue reading

#MathStatMonth Day 22: Recommended Reading

I’ve collected some of my favorite math-y or stats-y articles or posts from the past couple of years. Hope you enjoy!

538 wrote a feature on tornadoes and statistics; it’s also about separating real patterns from pareidolia (perceiving patterns when there really aren’t any). It’s also about the place where I grew up, so it’s a question that was relevant to my life for a long time.

This post talks about how some folks tracked down the cause of weird disruptions in Singapore’s railway system. I thought the authors did a good job showing how they worked with the data, what kinds of visualizations they made, and how they confirmed their suspicions.

Christian Lawson-Perfect wrote about investigations into times tables and a way in which 13 is particularly “bad.” It’s a cool problem and really accessible to high school students, especially if they can program a little.

Quanta had an article about the last edition of Proofs from THE BOOK. It has some interesting thoughts on what makes a beautiful proof and what the role of ugly mathematics is. At one point, Michael Pershan wondered on Twitter about the role of surprise in beautiful proofs, and this addresses that a little. It’s something I want to write about at some point.

“Math’s Beautiful Monsters” mashes together real analysis, chaos, stochastics, and fluids, all things that I love. It tells a mathematical story that I had never thought of as a single story. I wouldn’t have thought about it this way, but it’s pretty compelling.

This Stanford news story talks about a PhD student who studied mathematical diagrams in various copies and translations of Euclid’s Elements. As someone who at various points has been really interested in both visual representations in math and the role of the Elements in math history, I found this cool.

This SIAM News Blog post is a good introduction to the shallow water equations (which are a decent first model for a lot of geophysical applications) and the numerical methods you can use in solving them.

“Normal America” is an interesting look (with some well-described stats) at what “normal America” actually is. I think about this post a lot.

#MathStatMonth Day 21: Texas 42

This post is a little different from the others I’ve done this month. For the past couple of years, I’ve been putting together a set of counting/discrete math questions based on the domino game 42 (or Texas 42). I’ve integrated the questions with information about the setup and rules of the game. This is the main set of questions, and I’d love to know if you have thoughts or suggestions. I’ve also been working on a few extensions related to variations on the game (existing ones, like the game 80 or bidding Nell-O, and ones that ask for more creativity, like adjusting the game to play with double-nines instead of double-sixes). Continue reading