Tony’s Take November 2023

This month’s topics:

Combinatorics and Cocktail Parties.

A press release from UCSD about progress in Ramsey theory was picked up by Rebecca Dyer for with the title: “Mathematicians Crack a Century-Old Problem That’s Perfect For Your Next Party.” The mathematicians in question are Sam Mattheus (Vrije Universiteit Brussel) and Jacques Verstraete (University of California, San Diego). In their preprint, Mattheus and Verstraete write, “Ramsey Theory is an area of mathematics underpinned by the philosophy that in any large enough structure, there exists a relative large uniform substructure.” The simplest example is this question: Suppose you have $n$ points. Join every pair of 2 points by a line colored either red or blue. How large does $n$ have to be so that in any such configuration three of the points are the vertices of a red triangle or three are the vertices of a blue one? Here, the large structure is the randomly-colored $n$-vertex graph, and the uniform substructure is a monochromatic triangle.

r(3,3) illustrated
You can join five points two by two by red or blue colored lines without forming any single-color triangles. This is impossible for six points. Elementary proof here. Image by Tony Phillips.

More generally, the Ramsey number $r(s,t)$ is the smallest $n$ such that if $n$ points are joined two by two by red or blue lines, then there are at least $s$ which are joined two by two by red lines, or $t$ which are joined two by two by blue lines. In other words, $r(s,t)$ is the smallest $n$ such that a red/blue coloring of the complete graph on $n$ points must contain a complete red graph on $s$ points or a complete blue graph on $t$ points. The example we just saw was $r(3, 3)=6$. The British mathematician, philosopher and economist Frank Ramsey (some details of his short, intense life are on the University of St. Andrews website) proved in 1930 that for any $s$ and $t$ this number is finite. Finding its exact value, beyond $r(3,3)=6$, turned out to be difficult. The ones currently known are tabulated here, with their sources. They go up to $r(3,9)=36$ and $r(4,5)=25$.

Paul Erdös conjectured an asymptotic formula for a lower bound on $r(4,t)$ as $t$ goes to infinity and offered a \$250 prize for a proof. It remained unclaimed until Mattheus and Verstraete’s calculation this year: they proved that there exists a constant $c$ such that, for $t$ sufficiently large,
$$r(4,t) \geq c\frac {t^3}{\log^4t}.$$

This confirms Erdös’s intuition and nails the exponent in the denominator, which he had left unspecified. To give an idea of the complexity of the problem, Verstraete constructed this image of a red/blue coloring of the complete graph on 24 points which contains neither a complete red graph on 4 points nor a complete blue graph on 5. This image represents for $r(4,5)=25$ what the pentagonal colored graph at the start of this item does for $r(3,3)=6$.

example shows r(4,5)>24
A red and blue coloring of the complete graph on 24 points such that no 4 points are two by two joined by red lines, and no 5 points are two by two joined by blue ones. This shows that the Ramsey number $r(4,5)$ must be larger than 24 (it is in fact 25). Image courtesy of Jacques Verstraete.

The geometric viability assay.

Suppose you are working in a medical lab, and you want to test the efficacy of an antibiotic against some type of single-cell organism. Starting with a solution containing a known concentration of the target cells, you mix in some concentration of the drug, give it time to work, and then measure how many of the cells are still viable. The standard way to perform this measurement is the CFU assay: you culture a given volume of the post-treatment solution on some medium and count the number of distinct colonies, assuming that each colony grew from a single surviving viable cell, or colony-forming unit (CFU).

The problem with this technique is the counting. If there were too many CFUs in your sample the colonies will run together and be impossible to count; if there were too few, your count will be statistically unreliable. The problem is solved (as explained, for example, in this problem set from the UVM Microbiology and Molecular Genetics department) by diluting the antibiotic to 1/10, 1/100, etc. of the original concentration — a dilution series — and then growing samples each time, expecting that one of them will yield a “reasonable number” (in the range 30-300) of colonies.

A high-throughput and low-waste viability assay for microbes (Nature Microbiology, November 2, 2023) states that the CFU assay “has remained the gold standard” for measuring viability, but proposes another method that avoids some of its “time-intensive and resource-consuming” aspects. This new method is the Geometric Viability Assay (GVA). The authors, a University of Colorado, Boulder team led by Christian T. Meyer, Anushree Chatterjee and Joel M. Kralj, use the geometry of a cone and the easy availability of cones in the laboratory (polypropylene pipette tips) to replicate the effect of the dilution series at one shot.

The volume in a pipette between $x$ and $x+dx$ (blue disk) is proportional to $x^2$, and so varies significantly from one end to the other. Image by Tony Phillips.

The authors argue that the chance of finding a colony in the pipette at $x$ units from the tip is proportional to the volume of the infinitesimal slice between $x$ and $x+dx$ and therefore to $x^2$. This means the assayer can find a “reasonable number” to count by scanning along the pipette and choosing $x$ appropriately. If $N$ is the number of colonies counted in an interval around $x$, then the GVA estimate of the concentration of cells that survived is $N$ divided by the volume of the slice corresponding to that interval, which they calculate by integration as usual. (This is why they make Pre-Meds take Calc I.)

test run with E. coli
The authors demonstrate the GVA by applying the method to eight samples from a dilution series (in this case, of E. coli), where each sample, reading from right to left, is ten times more dilute than the previous one. The GVA-calculated estimates of the concentration, in colony-forming units per ml, are written under the corresponding pipette images. Image from the Open Access article Meyer, C.T., Lynch, G.K., Stamo, D.F. et al. A high-throughput and low-waste viability assay for microbes. Nat Microbiol 8, 2304–2314 (2023). Used under CC BY 4.0 DEED license.

Algebra in California, cont.

We visited this topic in May, but the mathematical unrest out there continues. The Wall Street Journal Editorial Board ran California’s New Old Math (subtitle, “Parents fight to restore eighth-grade algebra in San Francisco’s public schools”) on November 12, 2023. They give the background, going back to the decision in 2014 by the San Francisco Unified School District to stop offering Algebra I in the eighth grade. As they explain it, this was done “in the name of—what else?—equity.” The theory was that separating students into more or less advanced curricular levels would widen the gap between the performance of minority students and their more socio-economically advantaged peers. They cite a March 2023 report by three Stanford researchers (one professor and two graduate students) evaluating the actual results. The WSJ editorial does not mention one of the main findings of the report, which was a sharp decrease in AP Calculus enrollment especially for Asian students.

The editorial ran in anticipation of a rally supporting a ballot measure that would restore Algebra in grade 8. The editorial concludes by stating that the rally “is an example of parents no longer blindly accepting what school boards, administrators and teachers’ unions tell them,” and that the School Board, meeting again in February, will “face the wrath of the SF Guardians” (who organized the rally) if they don’t vote for the restoration.

A personal, nuanced view of the situation was given by Julie Lynem on the news-site CalMatters: “My son’s decision to retake algebra made me rethink California’s new approach to math” (November 8, 2023). Her son had taken and passed Algebra I in eighth grade, but was dissatisfied with his understanding of the subject and opted to repeat it, so he will likely have not taken calculus when he graduates from high school next year.

That’s the subtext in the discussions about Algebra I in grade 8: calculus. For many families, AP Calculus has become an indispensable item in their children’s struggle for admission to a prestigious college. (For Asian-American parents the pressure may be even higher, as documented in this November 26, 2023 article in the Los Angeles Times.) But students who take Algebra I in grade 9 have little chance of being able to complete AP Calculus before graduating from high school.

The pressure is not an illusion. The non-profit education news site The74 posted on November 6, 2023 Even as Caltech Drops Calculus Requirement, Other Competitive Colleges Continue to Expect Hard-to-Find Course. The website BestColleges has had a page up since March, 2022: Want to Get Into Harvard? Ace Calculus, while the non-profit JustEquations put out a September, 2022 report “Calculating the Odds: Counselor Views on Math Coursetaking and College Admissions.” The executive summary notes that even when colleges explicitly drop the calculus requirement, high school counselors “have concluded, based on their own experiences, that the course is at least strongly expected at highly selective schools.” The report quotes a high school counselor: “It is deeply problematic that college admission offices—many of which are entirely unaware of how actual math content, sequencing, programs work—use calculus as a benchmark for college admission.”

Lynem’s son, now an algebra tutor, doesn’t regret going for mastery instead of what Lynem calls “the race to take calculus”. Lynem’s story reviews the recent history of mathematics education in California, including the new state-wide Mathematics Framework adopted by the California State Board of Education last July. She spoke with the Board president, Linda Darling-Hammond, and quotes her: “Math has been taught as a set of rules and procedures, rather than helping kids use the math in real-world contexts so that students can say, ‘I deeply understand what I’m doing with this, and it’s giving me answers to things I care about.'”

The controversy about Algebra I in grade 8 has nothing to do with solving and graphing equations, etc. and their appropriateness for students at this level. It arises because “Algebra I in grade 8” is seen, correctly, by many parents as the first crucial step in the process that will get their children into a prestigious college and thereby preserve or improve their standing in society.