Archive

Archive for the ‘Undergraduate education’ Category

The problem with combinatorics textbooks

Every now and then I think about writing a graduate textbook in Combinatorics, based on some topics courses I have taught. I scan my extensive lecture notes, think about how much time it would take, and whether there is even a demand for this kind of effort. Five minutes later I would always remember that YOLO, deeply exhale and won’t think about it for a while.

What’s wrong with Combinatorics?

To illustrate the difficulty, let me begin with two quotes which contradict each other in the most illuminating way. First, from the Foreword by Richard Stanley on (his former student) Miklós Bóna’s “A Walk Through Combinatorics” textbook:

The subject of combinatorics is so vast that the author of a textbook faces a difficult decision as to what topics to include. There is no more-or-less canonical corpus as in such other subjects as number theory and complex variable theory. [here]

Second, from the Preface by Kyle Petersen (and Stanley’s academic descendant) in his elegant “Inquiry-Based Enumerative Combinatorics” textbook:

Combinatorics is a very broad subject, so the difficulty in writing about the subject is not what to include, but rather what to exclude. Which hundred problems should we choose? [here]

Now that this is all clear, you can probably insert your own joke about importance of teaching inclusion-exclusion. But I think the issue is a bit deeper than that.

I’ve been thinking about this when updating my “What is Combinatorics” quotation page (see also my old blog post on this). You can see a complete divergence of points of view on how to answer this question. Some make the definition or description to be very broad (sometimes even ridiculously broad), some relatively narrow, some are overly positive, while others are revoltingly negative. And some basically give up and say, in effect “it is what it is”. This may seem puzzling, but if you concentrate on the narrow definitions and ignore the rest, a picture emerges.

Clearly, these people are not talking about the same area. They are talking about sub-areas of Combinatorics that they know well, that they happen to learn or work on, and that they happen to like or dislike. Somebody made a choice what part of Combinatorics to teach them. They made a choice what further parts of Combinatorics to learn. These choices are increasingly country or culture dependent, and became formative in people’s mind. And they project their views of these parts of Combinatorics on the whole field.

So my point is — there is no right answer to “What is Combinatorics?“, in a sense that all these opinions are biased to some degree by personal education and experience. Combinatorics is just too broad of a category to describe. It’s a bit like asking “what is good food?” — the answers would be either broad and bland, or interesting but very culture-specific.

Courses and textbooks

How should one resolve the issue raised above? I think the answer is simple. Stop claiming that Combinatorics, or worse, Discrete Mathematics, is one subject. That’s not true and hasn’t been true for a while. I talked about this in my “Unity of Combinatorics” book review. Combinatorics is comprised of many sub-areas, see the Wikipedia article I discussed here (long ago). Just accept it.

As a consequence, you should never teach a “Combinatorics” course. Never! Especially to graduate students, but to undergraduates as well. Teach courses in any and all of these subjects: Enumerative Combinatorics, Graph Theory, Probabilistic Combinatorics, Discrete Geometry, Algebraic Combinatorics, Arithmetic Combinatorics, etc. Whether introductory or advanced versions of these courses, there is plenty of material for each such course.

Stop using these broad “a little bit about everything” combinatorics textbooks which also tend to be bulky, expensive and shallow. It just doesn’t make sense to teach both the five color theorem and the Catalan numbers (see also here) in the same course. In fact, this is a disservice to both the students and the area. Different students want to know about different aspects of Combinatorics. Thus, if you are teaching the same numbered undergraduate course every semester you can just split it into two or three, and fix different syllabi in advance. The students will sort themselves out and chose courses they are most interested in.

My own teaching

At UCLA, with the help of the Department, we split one Combinatorics course into two titled “Graph Theory” and “Enumerative Combinatorics”. They are broader, in fact, than the titles suggest — see Math 180 and Math 184 here. The former turned out to be quite a bit more popular among many applied math and non-math majors, especially those interested in CS, engineering, data science, etc., but also from social sciences. Math majors tend to know a lot of this material and flock to the latter course. I am not saying you should do the same — this is just an example of what can be done.

I remember going through a long list of undergraduate combinatorics textbooks a few years ago, and found surprisingly little choice for the enumerative/algebraic courses. Of the ones I liked, let me single out Bóna’s “Introduction to Enumerative and Analytic Combinatorics and Stanley’s “Algebraic Combinatorics“. We now use both at UCLA. There are also many good Graph Theory course textbooks of all levels, of course.

Similarly, for graduate courses, make sure you make the subject relatively narrow and clearly defined. Like a topics class, except accessible to beginning graduate students. Low entry barrier is an advantage Combinatorics has over other areas, so use it. To give examples from my own teaching, see unedited notes from my graduate courses:

Combinatorics of posets (Fall 2020)

Combinatorics and Probability on groups (Spring 2020)

Algebraic Combinatorics (Winter 2019)

Discrete and Polyhedral Geometry (Fall 2018) This is based on my book. See also videos of selected topics (in Russian).

Combinatorics of Integer Sequences (Fall 2016)

Combinatorics of Words (Fall 2014)

Tilings (Winter 2013, lecture-by-lecture refs only)

In summary

In my experience, the more specific you make the combinatorics course the more interesting it is to the students. Don’t be afraid that the course would appear be too narrow or too advanced. That’s a stigma from the past. You create a good course and the students will quickly figure it out. They do have their own FB and other chat groups, and spread the news much faster than you could imagine…

Unfortunately, there is often no good textbook to cover what you want. So you might have to work a little harder harder to scout the material from papers, monographs, etc. In the internet era this is easier than ever. In fact, many extensive lecture notes are already available on the web. Eventually, all the appropriate textbooks will be written. As I mentioned before, this is one of the very few silver linings of the pandemic…

P.S. (July 8, 2021) I should have mentioned that in addition to “a little bit about everything” textbooks, there are also “a lot about everything” doorstopper size volumes. I sort of don’t think of them as textbooks at all, more like mixtures of a reference guide, encyclopedia and teacher’s manual. Since even the thought of teaching from such books overwhelms the senses, I don’t expect them to be widely adopted.

Having said that, these voluminous textbooks can be incredibly valuable to both the students and the instructor as a source of interesting supplementary material. Let me single out an excellent recent “Combinatorial Mathematics” by Doug West written in the same clear and concise style as his earlier “Introduction to Graph Theory“. Priced modestly (for 991 pages), I recommend it as “further reading” for all combinatorics courses, even though I strongly disagree with the second sentence of the Preface, per my earlier blog post.

What if math dies?

Over the years I’ve heard a lot about the apparent complete uselessness and inapplicability of modern mathematics, about how I should always look for applications since without them all I am doing is a pointless intellectual pursuit, blah, blah, blah.  I had strangers on the plane telling me this (without prompting), first dates (never to become second dates) wondering if “any formulas changed over the last 100 years, and if not what’s the point“, relatives asking me if I ever “invented a new theorem“, etc.

For whatever reason, everyone always has an opinion about math.  Having never been accused of excessive politeness I would always abruptly change the subject or punt by saying that the point is “money in my Wells Fargo account“.  I don’t even have a Wells Fargo account (and wouldn’t want one), but what’s a small lie when you are telling a big lie, right?

Eventually, you do develop a thicker skin, I suppose.  You learn to excuse your friends as well meaning but uneducated, journalists as maliciously ignorant, and strangers as bitter over some old math learning experience (which they also feel obliged to inform you about).  However, you do expect some understanding and respect from fellow academics. “Never compare fields” Gian-Carlo Rota teaches, and it’s a good advice you expect sensible people to adhere.  Which brings me to this:

The worst idea I’ve heard in a while

In a recent interview with Glenn Loury, a controversial UPenn law professor Amy Wax proposed to reduce current mathematics graduate programs to one tenth or one fifteenth of their current size (start at 54.30, see also partial transcript).  Now, I get it.  He is a proud member of the “intellectual dark web“, while she apparently hates liberal education establishment and wants to rant about it.  And for some reason math got lumped into this discussion.  To be precise, Loury provoked Wax without offering his views, but she was happy to opine in response.  I will not quote the discussion in full, but the following single sentence is revealing and worth addressing:

If we got rid of ninety percent of the math Ph.D. programs, would we really be worse off in any material respect?  I think that’s a serious question.

She followed this up with “I am not advocating of getting rid of a hundred percent of them.”  Uhm, thanks, I guess…

The inanity of it all

One is tempted to close ranks and ridicule this by appealing to authority or common sense.  In fact, just about everyone — from Hilbert to Gowers — commented on the importance of mathematics both as an intellectual endeavor and the source of applications.  In the US, we have about 1500-2000 new math Ph.D.’s every year, and according to the AMS survey, nearly all of them find jobs within a year (over 50% in academia, some in the industry, some abroad).

In fact, our math Ph.D. programs are the envy of the world.  For example, of the top 20 schools worldwide between 12 and 15 are occupied by leading US programs depending on the ranking (see e.g. here or there for recent examples, or more elsewhere).  Think about it: math requires no capital investment or infrastructure at all, so with the advent of personal computing, internet and the arXiv, there are little or no entry barriers to the field.  Any university in the world can compete with the US schools, yet we are still on the top of the rankings.  It is bewildering then, why would you even want to kill these super successful Ph.D. programs?

More infrastructurally, if there are drastic cuts to the Ph.D. programs in the US, who would be the people that can be hired to teach mathematics by the thousands of colleges whose students want to be math majors?  The number of the US math majors is already over 40,000 a year and keep growing at over 5% a year driven in part by the higher salary offerings and lifetime income (over that of other majors).  Don’t you think that the existing healthy supply and demand in the market for college math educators already determined the number of math Ph.D.’s we need to produce?

Well, apparently Wax doesn’t need convincing in the importance of math.  “I am the last person to denigrate pure mathematics.  It is a glory of mankind…”   She just doesn’t want people doing new research.  Or something.  As in “enough already.”  Think about it and transfer this thought to other areas.  Say — no new music is necessary — Bach and Drake said it all.  Or — no new art is necessary — Monet and Warhol were so prolific, museums don’t really have space for new works.  Right…

Economics matters

Let’s ask a different question: why would you want to close Ph.D. programs when they actually make money?  Take UCLA.  We are a service department, which makes a lot of money from teaching all kinds of undergraduate math courses + research grants both federal, state and industrial.  Annually, we graduate over 600 students with different types of math/stat majors, which constitutes about 1.6% of national output, the most of all universities.

Let’s say our budget is $25 mil (I don’t recall the figures), all paid for. That would be out of UCLA budget of$7.5 billion of which less than 7% are state contributions.  Now compare these with football stadiums costs which are heavily subsidized and run into hundreds of millions of dollars.  If you had to cut the budget, is math where you start?

Can’t we just ignore these people?

Well, yes we can.  I am super happy to dismiss hurried paid-by-the-word know-nothing journalists or some anonymous YouTube comments.  But Amy Wax is neither.  She is smart and very accomplished:  summa cum laude from Yale, M.D. cum laude from Harvard Medical School, J.D. from Columbia Law School where she was an editor of Columbia Law Review, argued 15 cases in the US Supreme Court, is a named professor at UPenn Law School, has dozens of published research papers in welfare, labor and family law and economics.  Yep.

One can then argue — she knows a lot of other stuff, but nothing about math.  She is clearly controversial, and others don’t say anything of that nature, so who cares.  That sounds right, but so what?  Being known as controversial is like license to tell “the truth”…  er… what they really think.  Which can include silly things based on no research into our word.  This means there are numerous other people who probably also think that way but are wise enough or polite enough not to say it.  We need to fight this perception!

And yes, sometimes these people get into positions of power and decide to implement the changes.  Two cases are worth mentioning: the University of Rochester failed attempt to close its math Ph.D. program, and the Brown University fiasco.  The latter is well explained in the “Mathematical Apocrypha Redux” (see the relevant section here) by the inimitable Steven Krantz.  Rating-wise, this was a disaster for Brown — just read the Krantz’s description.

The Rochester story is rather well documented and is a good case of study for those feeling too comfortable.  Start with this Notices article, proceed to NY Times, then to protest description, and this followup in the Notices again.  Good news, right?  Well, I know for a fact that other administrators are also making occasional (largely unsuccessful) moves to do this, but I can’t name them, I am afraid.

Predictable apocalypse

Let’s take Amy Wax’s proposal seriously, and play out what would happen if 90-93% of US graduate programs in mathematics are closed on January 1, 2020.  By law.  Say, the US Congress votes to deny all federal funds to universities if they maintain a math Ph.D. program, except for the top 15 out of about 180 graduate programs according to US News.  Let’s ignore the legal issues this poses.  Just note that there are various recent and older precedents of federal government interfering with state and private schools (sometimes for a good cause).

Let’s just try to quickly game out what would happen.  As with any post-apocalyptic fiction, I will not provide any proofs or reasoning.  But it’s all “reality based”, as two such events did happened to mathematicians in the last century, one of them deeply affecting me: the German “academic reforms” in late 1930s (see e.g. here or there), and the Russian exodus in early 1990s (see e.g. here or there, or there).  Another personally familiar story is an implosion of mathematics at Bell Labs in late 1990s.  Although notable, it’s on a much smaller scale and to my knowledge has not been written about (see the discussion here, part 6).

First, there will be huge exodus of distinguished mathematics faculty from school outside of the 15 schools.  These include members of the National Academy of Sciences, numerous ICM speakers, other award winners, etc.  Some will move overseas (Canada, Europe, Japan, China, etc.), some will retire, some leave academia.  Some will simply stop doing research given the lack of mathematical activity at the department and no reward for doing research.

Second, outside of top 15, graduate programs in other subjects notice falling applications resulting in their sliding in world ranking.  These include other physical sciences, economics and computer science.  Then biological and social sciences start suffering.  These programs start having their own exodus to top 15 school and abroad.

Third, given the sliding of graduate programs across the board, the undergraduate education goes into decline across the country.  Top US high school students start applying to school abroad. Many eventually choose to stay in these countries who welcome their stem excellence.

Fourth, the hitech, fintech and other science heavy industries move abroad closer to educated employees.  United States loses its labor market dominance and starts bleeding jobs across all industries.   The stocks and housing market dip down.

Fifth, under strong public pressure the apocalyptic law is repealed and all 180 Ph.D. programs are reinstated with both state and federal financial support.  To everyone’s surprise, nobody is moving back.  Turns out, destroying is much faster and easier than rebuilding, as both Germany and Russia discovered back in the 20th century.  From that point on, January 1, 2020 became known as the day the math died.

Final message:

Dear Amy Wax and Glenn Loury!  Please admit that you are wrong.  Or at least plead ignorance and ask for forgiveness.  I don’t know if you will ever see this post or have any interest in debating the proposition I quoted, but I am happy to do this with you.  Any time, any place, any style.  Because the future of academia is important to all of us.

Fibonacci times Euler

Recall the Fibonacci numbers $F_n$ given by 1,1,2,3,5,8,13,21… There is no need to define them. You all know. Now take the Euler numbers (OEIS) $E_n$ 1,1,1,2,5,16,61,272… This is the number of alternating permutations in $S_n$ with the exponential generating function $\sum_{n=0}^\infty E_n t^n/n! = \tan(t)+\sec(t)$.  Both sequences are incredibly famous. Less known are connection between them.

(1) Define the Fibonacci polytope $\Phi_n$ to be a convex hull of  0/1 points in $\Bbb R^n$ with no two 1 in a row. Then  $\Phi_n$ has $F_{n+1}$ vertices and vol$(\Phi_n)=E_n/n!$ This is a nice exercise.

(2) $F_n \cdot E_n \ge n!$ (by just a little). For example, $F_4 \cdot E_4 = 5 \cdot 5 = 25 > 4!$. This follows from the fact that

$F_n \sim \frac{1}{\sqrt{5}} \, \phi^{n+1}$ and $E_n\sim \frac{4}{\pi}\left(\frac{2}{\pi}\right)^{n} n!$, where $\phi=(1+\sqrt{5})/2$ is the golden ratio. Thus, the product $F_n \cdot E_n \sim c n! \left(\frac{2\phi}{\pi}\right)^n$. Since $\pi = 3.14$ and $2\phi = 3.24$, the inequality $F_n \cdot E_n \ge n!$ is easy to see, but still a bit surprising that the numbers are so close.

Together with Greta Panova and Alejandro Morales we wrote a little note “Why is π < 2φ?” which gives a combinatorial proof of (2) via a direct surjection. Thus we obtain an indirect proof of the inequality in the title.  The note is not a research article; rather, it is aimed at a general audience of college students.  We will not be posting it on the arXiv, so I figure this blog is a good place to advertise it.

The note also explains that the inequality (2) also follows from Sidorenko’s theorem on complementary posets. Let me briefly mention a connection between (1) and (2) which is not mentioned in the note.  I will assume you just spent 5 min and read the note at this point.  Following Stanley, the volume of $\Phi_n$ is equal to the volume of the chain polytope (=stable set polytope), see Two Poset Polytopes.  But the latter is exactly the polytope that Bollobás, Brightwell and Sidorenko used in their proof of the upper bound via polar duality.

Academia is nothing like a drug cartel

It’s been awhile since I wanted to rant. Since the last post, really. Well, I was busy. But the time has come to write several posts.

This post is about a number of recent articles lamenting the prevalence of low paid adjuncts in many universities. To sensationalize the matter, comparisons were made with drug cartels and Ponzi schemes. Allegedly, this inequality is causing poverty and even homelessness and death. I imagine reading these articles can be depressing, but it’s all a sham. Knowingly or not, the journalists are perpetuating false stereotypes of what professors really do. These journalists seem to be doing their usual lazy work and preying on reader’s compassion and profound misunderstanding of the matter.

Now, if you are reading this blog, I am assuming you know exactly what professors do (Hint: not just teaching). But if you don’t, start with this outline by my old friend Daniel Liberzon, and proceed to review any or all of these links: one, two, three, four. When you are done, we can begin to answer our main semi-serious question:

What is academia, really, if it’s not a drug cartel or a Ponzi scheme?

I can’t believe this trivial question is difficult to some people, and needs a lengthy answer, but here it is anyway.

This might seem obvious – of course it does!  These are the main qualities needed to achieve success doing research. But reading the above news reports it might seem that Ph.D. is like a lottery ticket – the winnings are rare and random. What I am trying to say is that academia can be compared with other professions which involve both qualities. To make a point, take sculpture.

There are thousands of professional sculptors in the United States. The figures vary greatly, but same also holds for the number of mathematicians, so we leave it aside. The average salary of sculptors seems to be within reach from average salary in the US, definitely below that of an average person with bachelor degree. On the other hand, top sculptors are all multimillionaires. For example, recently a sculpture by Jeff Koons sold for $58.4 million. But at least it looked nice. I will never understand the success of Richard Serra, whose work is just dreadful. You can see some of his work at UCLA (picture), or at LACMA (picture). Or take a celebrated and much despised 10 million dollar man Dale Chihuly, who shows what he calls “art” just about everywhere… But reasonable people can disagree on this, and who am I to judge anyway? My opinion does not matter, nor is that of almost anyone. What’s important, is that some people with expertise value these creative works enough to pay a lot of money for them. These sculptors’ talent is clearly recognized. Now, should we believe on the basis of the salary disparity that the sculpture is a Ponzi scheme, with top earners basically robbing all the other sculptors of good living? That would be preposterous, of course. Same with most professors. Just because the general public cannot understand and evaluate their research work and creativity, does not mean it’s not there and should not be valued accordingly. Academia is a large apprenticeship program Think of graduate students who are traditionally overworked and underpaid. Some make it to graduate with a Ph.D. and eventually become tenured professors. Many, perhaps most, do not. Sounds like a drug cartel to you? Nonsense! This is exactly how apprenticeships works, and how it’s been working for centuries in every guild. In fact, some modern day guilds don’t pay anything at all. Students enter the apprenticeship/graduate program in hopes to learn from the teacher/professor and succeed in their studies. The very best do succeed. For example, this list of Rembrant‘s pupils/assistants reads somewhat similar to this list of Hilbert‘s students. Unsurprisingly, some are world famous, while others are completely forgotten. So it’s not about cheap labor as in drug cartels – this is how apprenticeships normally work. Academia is a big business Think of any large corporation. The are many levels of management: low, mid, and top-level. Arguably, all tenured and tenure-track faculty are low level managers, chairs and other department officers (DGS, DUS, etc.) are mid-level, while deans, provosts and presidents/chancellors are top-level managers. In the US, there is also a legal precedent supporting qualifying professors as management (e.g. professors are not allowed to unionize, in contrast with the adjunct faculty). And deservingly so. Professors hire TA’s, graders, adjuncts, support stuff, choose curriculum, responsible for all grades, run research labs, serve as PI’s on federal grants, and elect mid-level management. So, why many levels? Take UCLA. According to 2012 annual report, we operate on 419 acres, have about 40 thousand students, 30 thousand full time employees (this includes UCLA hospitals), have$4.6 billion in operating revenue (of which tuition is only $580 million), but only about 2 thousand ladder (tenure and tenure-track) faculty. For comparison, a beloved but highly secretive Trader Joe’s company has about$8 billion in revenue, over 20 thousand employees, and about 370 stores, each with 50+ employees and its own mid and low-level management.

Now that you are conditioned to think of universities as businesses and professors as managers, is it really all that surprising that regular employees like adjuncts get paid much less?  This works the same way as for McDonalds store managers, who get paid about 3 times as much as regular employees.

Higher echelons of academia is a research factory with a side teaching business

Note that there is a reason students want to study at research universities rather than at community colleges.  It’s because these universities offer many other more advanced classes, research oriented labs, seminars, field works, etc.  In fact, research and research oriented teaching is really the main business rather than service teaching.

Think revenue.  For example, UCLA derives 50% more revenue from research grants than from tuition.  Places like MIT are giving out so many scholarships, they are loosing money on teaching (see this breakdown).  American universities cannot quit the undergraduate education, of course, but they are making a rational decision to outsource the low level service teaching to outsiders, who can do the same work but cheaper.  For example, I took English in Moscow, ESL at a community college in Brooklyn, French at Harvard, and Hebrew at University of Minnesota.  While some instructors were better than others, there was no clear winner as experience was about the same.

So not only the adjunct salaries are low for a reason, keeping them low is critical to avoid hiring more regular faculty and preventing further tuition inflation.  The next time you read about adjuncts barely making a living wage, compare this to notorious Bangalore call centers and how much people make over there (between $100 and$250 a month).