Math bracket 2016

It’s that time again — March Math Madness, where we fill out an NCAA men’s tournament bracket with the best math department winning every game.  As always, this bracket was filled out by a highly trained team consisting of myself and a group of procrastinating grad students, making decisions by voice vote, and if you disapprove of one of our choices, I’m sure it’s somebody else’s fault.  This is Berkeley’s first championship after falling to Harvard in 2012; meanwhile, Michigan sees its second final in three years but falls short again…

Screen Shot 2016-03-16 at 16 Mar 10.51.PM

Update: In the 34th percentile at ESPN after one day of play — thanks, Yale!

Update:  Down to the 5th percentile and only Duke and UVa are left out of my final 8 picks.  Not gonna be the math bracket’s finest year.

Tagged , ,

Those who leave and those who stay

Just finished the third of Ferrante’s Neapolitan novels.  Greco, the narrator, is constantly yearning for a quiet space, away from competition.  The sense is that you can only make art in such a quiet space.  But it seems there’s no interaction between people without one striving to fuck, thwart, or destroy the other.   So maybe no quiet space exists, though Greco again and again almost seems to find it.  Ferrante puts the football down in front of her, Ferrante pulls it away.  And you’re surprised every time.

New SIAM journal on applied algebra

As you know I’m a fan of “applied pure math.”  You can be an applied mathematician and not do PDEs or numerical analysis now!  And to reflect this new reality, there’s a new journal, SIAM Journal on Applied Algebra and Geometry (SIAGA).  They’re accepting submissions starting March 23; I actually have a little something that might be finished by then that would be perfect!

There are a bunch of cool pictures on the SIAGA flyer:  UC-Berkeley grad student Anna Seigal is explaining them on her blog, one by one.  The first entry depicts the algebraic variety you encounter when you try to find a point minimizing the summed distances to k other points in the plane.  Handsome!

Tagged ,

Home rule in Wisconsin: the or and the and

The Wisconsin Supreme Court is hearing arguments about a residency requirement for employees of the city of Milwaukee.  Milwaukee has a law requiring city employees to live within Milwaukee’s boundaries.  The state legislature passed a law forbidding cities from making or enforcing such laws.  Last summer, the 1st District Court of Appeals found that law in violation of the Home Rule Amendment to the Wisconsin Constitution.  The constitutional question is:  when can state lawmakers overrule the legislative decisions of cities and villages?

You might think this would be clear.  On November 4, 1924, voters in Wisconsin overwhelmingly approved the Home Rule Amendment, which added to the state Constitution:

Cities and villages organized pursuant to state law may determine their local affairs and government, subject only to this constitution and to such enactments of the legislature of statewide concern as with uniformity shall affect every city or every village. The method of such determination shall be prescribed by the legislature.

It turns out it hasn’t been so simple, in practice, to figure out what those 51 words mean.  In a recent high-profile case, the Wisconsin Supreme Court upheld Act 10, Governor Walker’s signature legislation; among other things, the law forbade Milwaukee from contributing to its employees’ pension funds.  The plaintiffs argued that this provision violated home rule.  Michael Gableman, writing for the court majority, said it was fine.

This raises questions.  First of all:  if a state law needs to affect every city uniformly in order to supersede local government, how can it be OK to specifically target Milwaukee’s pension fund?  Here the exact wording of 62.623 is critical.  The law doesn’t mention Milwaukee:  it applies to “any employee retirement system of a 1st class city.”   The “uniformity” requirement in the Home Rule amendment has generally been understood very liberally, allowing laws which affect cities in different size classes differently as long as the application within each class is uniform.

To construe the amendment as meaning that every act of the Legislature relating to cities is subject to a charter ordinance unless the act of the Legislature affected with uniformity every city from the smallest to the greatest, practically destroys legislative control over municipal affairs, assuming that laws could be drawn which would meet the requirements of the amendment so construed.

That’s from Van Gilder v. City of Madison (1936), one of the first Wisconsin Supreme Court cases to wrestle with the limits of home rule.  I will have more to say about Chief Justice Marvin Rosenberry’s decision in that case, some of it pretty salty.  But for now let’s stick to the point at hand.  The law can be argued to pass the “uniformity” test because it applies equally to all cities of the first class.  There is only one city of the first class in Wisconsin, and there has only ever been one city of the first class in Wisconsin, and it’s Milwaukee.

That’s the argument the Walker administration made in defense of the law.  But the court’s upholding the law rejects that defense, and the uniformity clause as a whole, as irrelevant the question before it.

In sum, our home rule case law instructs us that, when reviewing a legislative enactment under the home rule amendment, we apply a two-step analysis.  First, as a threshold matter, the court determines whether the statute concerns a matter of primarily statewide or primarily local concern.  If the statute concerns a matter of primarily statewide interest, the home rule amendment is not implicated and our analysis ends.  If, however, the statute concerns a matter of primarily local affairs, the reviewing court then examines whether the statute satisfies the uniformity requirement.  If the statute does not, it violates the home rule amendment.

Thus:

no merit exists in the plaintiffs’ contention that the legislative enactment at issue in a home rule challenge must be a matter of statewide concern and uniformly applied statewide to withstand constitutional scrutiny.

Now this is weird, right?  Because what’s described and rejected as “the plaintiff’s contention” is what the constitution says.  Gableman replaces the Constitution’s and with an or:  in his analysis, a state law supersedes local powers if it’s either of statewide concern or applied uniformly to all cities.

Is this an act of wanton judicial activism?  Well, not exactly.  The phrase “as home rule case law instructs us” is important here.  The opinion marshals a long line of precedents showing that the Home Rule amendment has typically been read as an or, not an and.  It goes all the way back to Rosenberry’s opinion in Van Gilder v. City of Madison; and the reason there’s such a long list is that all those other cases rely on Van Gilder, which has become the foundation of Wisconsin’s theory of home rule.

Which brings us to the main point.  I’m not a legal scholar, but what the hell, this is blogging, I get to have an opinion, and here’s mine:  Van Gilder v. City of Madison was wrongly decided and has been screwing up home rule jurisprudence for 80 years.

Rosenberry’s first go at explaining home rule goes like this:

The home–rule amendment certainly confers upon cities plenary powers to deal with local affairs and government subject to the limitations contained in the amendment itself and other provisions of the Constitution. The powers of municipalities are subject to the limitation that the municipality cannot by its charter deal with matters which
are of state–wide concern and its power to enact an organic law dealing with local affairs and government is subject to such acts of the Legislature relating thereto as are of state–wide concern and affect with uniformity all cities.

The “and” between statewide concern and uniformity is clear here.  But Rosenberry also says that municipalities simply have no power to address matters of statewide concern:  its powers, he says, are restricted to “local affairs and government” as distinct from matters of statewide concern.  So what cases are the second clause (“its power to enact an organic law….”) referring to?  Only those matters which are not of statewide concern, but which are affected by state laws which are of statewide concern.  Rosenberry gives no examples of such a situation, nor can I really imagine one, so I don’t think that’s really the conclusion he means to draw.  Later in the opinion, he settles more clearly on the policy adopted by Gableman in Madison Teachers Inc. v. Walker:

when the Legislature deals with local affairs as distinguished from
matters which are primarily of state–wide concern, it can only do so effectually by an act which affects with uniformity every city. It is true that this leaves a rather narrow field in which the home–rule amendment operates freed from legislative restriction, but there is no middle ground.

and

the limitation contained in the section upon the power of the Legislature is a limitation upon its power to deal with the local affairs and government of a city or village. Care must be taken to distinguish between the power of the Legislature to deal with local affairs and its power to deal with matters primarily of state–wide concern. When the Legislature deals with local affairs and government of a city, if its act is not to be subordinate to a charter ordinance, the act must be one which affects with uniformity every city. If in dealing with the local affairs of a city the Legislature classifies cities so that the act does not apply with uniformity to every city, that act is subordinate to a charter ordinance relating to the same matter. A charter ordinance of a city is not subject to an act of the Legislature dealing with local affairs unless the act affects with uniformity every city. State ex rel. Sleeman v. Baxter, supra. When the Legislature deals with matters which are primarily matters of state–wide concern, it may deal with them free from any restriction contained in the home rule amendment.

Now the ground has shifted.  In Rosenberry’s reading, when the home rule amendment refers to “local affairs and government” it specifically intends to exclude any “matters of statewide concern.”  I can accept this as a reading of those four words, but not as a reading of the whole sentence. If Roseberry is correct, then the phrase “of statewide concern” is never active in the amendment:  a local affair is, by definition, not a matter of statewide concern.  I think when your interpretation of a constitutional passage means that part of the text never applies, you need to think twice about your interpretation.

What’s more, Rosenberry holds that the state has the power to override local officials on purely local matters, of no statewide concern whatsoever, as long as it does so uniformly.  If that is so, what does he think the words “of statewide concern” are doing in the Home Rule amendment at all?

To me, the amendment has a pretty plain meaning.  Something like a residency requirement for city employees or a fiscal decision about a city pension plan is plainly a local affair.  It may also be a matter of statewide concern.  The state legislature can enact a law overriding local legislation if the matter is of statewide concern and the law in question applies uniformly to all cities.  I think Rosenberry just plain got this wrong in Van Gilder and it’s been wrong ever since.

 

 

 

 

 

 

Tagged , , , , ,

Ferrante and juxtaposition

Most of the way through the third of Ferrante’s Neapolitan novels, Those Who Leave And Those Who Stay.  A central figure is the juxtaposition.  The special power that an artist has, in Ferrante, is to put things beside each other which are not ordinarily beside each other; or, to put it another way, to place distant entities into contact.  But it’s inevitable that the ability to do so also makes natural boundaries more permeable.  It becomes more difficult to keep what’s inside separate from what’s outside.  This creates problems.

Tagged , ,

Voices from Chernobyl

Voices from Chernobyl is an oral history of the atomic disaster and its aftermath, by Svetlana Alexievich,the first journalist to win the Nobel Prize for Literature.  (Steinbeck maybe?  But he didn’t win on his journalism.)

Nina Konstantinovnva, a literature teacher:

I teach Russian literature to kids who are not like the kids I taught ten years ago.  They are constantly seeing someone or something get buried, get placed underground.  Houses and trees, everything gets buried.  If they stand in line for fifteen, twenty minutes, some of them start fainting, their noses bleed.  You can’t surprise them with anything and you can’t make them happy.  They’re always tired and sleepy.  Their faces are pale and gray.  They don’t play and they don’t fool around.  If they fight or accidentally break a window, the teachers are pleased.  We don’t yell at them, because they’re not like kids.  And they’re growing so slowly.  You ask them to repeat something during a lesson, and the child can’t, it gets to the point where you simply ask him to repeat a sentence, and he can’t.  You want to ask him, “Where are you?  Where?”

Major Oleg Pavlov, a helicopter pilot:

Every April 26 we get together, the guys who were there.  We remember how it was.  You were a soldier, at war, you were necessary.  We forget the bad parts and remember that.  We remember that they couldn’t have made it without us.  Our system, it’s a military system, essentially, and it works great in emergencies.  You’re finally free there, and necessary.  Freedom!  And in those times the Russian shows how great he is.  How unique.  We’ll never be Dutch or German.  And we’ll never have proper asphalt or manicured lawns.  But there’ll always be plenty of heroes.

Translated by Keith Gessen.

Tagged , ,

Clearly, evidently, unambiguously

Katie Roiphe is getting paid less than her male colleagues.

I simmer and stew over the almost cliched inequity of it. It would be soothing to blame some sort of institutional sexism, to take refuge in that. But the fault is so clearly, evidently, unambiguously my own.

She then goes on to explain why it’s clearly, evidently, unambiguously her own fault that

I also suspect there is something deep in childhood being communicated to most boys that is not communicated to most girls. Do boys grow up steeped in these negotiations, prepped for them? I glance over at my six-year-old on an iPad, busily slaying zombies and creepers on Minecraft, and blasting open treasure chests. Is he somehow absorbing the lesson that you should wrench the gold you need from a largely hostile and bewildering world?

and

I am also attuned to all the ways niceness is constructed for women, the pressure to smile for photographs, the urge to apologise for breathing, the whole elaborate social construction of female likability; and yet, when it comes to asking for more money, I have a horror of being disliked, or of the particular kind of dislike that sort of assertion provokes.

and

This strikes me as a very female problem: spending huge amounts of energy warding off the perception that you are somehow entitled, stuck up. There is a strong instinct towards diffusing competition, deflecting envy, towards not having people resent you. All the rampant female self-deprecation, the constant apologising, is part of this same maddening, consuming phenomenon.

and

One has to wonder where this responsibility to make strangers feel warm and happy comes from. Did women inherit the responsibility to erase all the awkward moments in the world?

Doesn’t it kind of seem like part of what’s keeping her salary down is clearly, evidently, unambiguously sexism?  Is it really that soothing to think otherwise?  I mean, it’s soothing for me to believe it’s all Katie Roiphe’s fault, because it means I don’t have to change what I’m doing in any way.  But why is it soothing for her?

Tagged ,

Metric chromatic numbers and Lovasz numbers

In the first post of this series I asked whether there was a way to see the Lovasz number of a graph as a chromatic number.  Yes!  I learned it from these notes, written by Big L himself.

Let M be a metric space, and let’s assume for simplicity that M has a transitive group of isometries.  Now write r_M(n) for the radius of the smallest ball containing n points whose pairwise distances are all at least 1.  (So this function is controlling how sphere-packing works in M.)

Let Γ be a graph.  By an M-coloring of Γ we now mean a map from v(Γ) to M such that adjacent vertices are at distance at least 1.  Write χ_Γ(M) for the radius of the smallest disc containing an M-coloring of Γ.  Then we can think of r^{-1}(χ_Γ(M)) as a kind of “M-chromatic number of Γ.”  Scare quotes are because r isn’t necessarily going to be an analytic function or anything; if I wanted to say something literally correct I guess I would say the smallest integer n such that r_M(n) >= χ_Γ(M).

The M-chromatic number is less than the usual chromatic number χ_Γ;  more precisely,

χ_Γ(M) <= r_M(χ_Γ)

Easy:  if there’s an n-coloring of Γ, just compose it with the map from [n] to M of radius r_M(n).  Similary, if ω_Γ is the clique number of Γ, we have

r_M(ω_Γ) <= χ_Γ(M)

because a k-clique can’t be embedded in a ball of radius smaller than r_M(k).

So this M-chromatic number gives a lower bound for the chromatic number and an upper bound for the clique number, just as the Lovasz number does, and just as the fractional chromatic number does.

Example 1:  Lovasz number.  Let M be the sphere in infinite-dimensional Euclidean space.  (Or |Γ|-dimensional Euclidean space, doesn’t matter.)  For our metric use (1/sqrt(2)) Euclidean distance, so that orthogonal vectors are at distance 1 from each other.  If n points are required at pairwise distance at least 1, the closest way to pack them is to make them orthonormal (I didn’t check this, surely easy) and in this case they sit in a ball of radius 1-sqrt(1/2n) around their center of mass.  So r_M(n) = 1 – sqrt(1/2n).  Define t(Γ) to be the real number such that

1 - \sqrt{1/2t(\Gamma)} = \chi_\Gamma(M).

Now I was going to say that t(Γ) is the Lovasz theta number of Γ, but that’s not exactly the definition; that would be the definition if I required the embedding to send adjacent vertices to points at distance exactly 1.  The answer to this MO question suggests that an example of Schrijver might actually separate these invariants, but I haven’t checked.

So I guess let’s say t(Γ) is a “Lovasz-like number” which is between the clique number and the chromatic number.  And like the Lovasz number, but unlike clique and chromatic numbers, it’s super-easy to compute.  An embedding of v(Γ) in the sphere, up to rotation, is specified by the pairwise distance matrix, which can be an arbitrary postive definite symmetric nxn matrix A with 1’s on the diagonal.  Each edge of Γ now gives an inequality a_{ij} > 1.  When you’re optimizing over a space cut out by linear inequalities in the space of psd matrices, you’re just doing semidefinite programming.  (I am punting a little about how to optimize “radius” but hopefully maximum distance of any vector from center of mass is good enough?)

(Note:  you know what, I’ll bet you can take an embedding like this, subtract a small multiple of the center of mass from all the vectors, and get an embedding of v(Γ) in n-space with all angles between adjacent vectors slightly obtuse, and probably this ends up being exactly the same thing as the vector chromatic number defined in the paper I linked to earlier.)

Where is example 2?  It was supposed to be about the fractional chromatic number but then I realized the way I was setting this up wasn’t correct.  The idea is to let M_b be the space of infinite bit strings with exactly b 1’s and use (1/2b) Hamming distance, so that the distance-1 requirement becomes a requirement that two b-element subsets be disjoint.  But I don’t think this quite fits into the framework I adopted at the top of the post.  I’ll circle back to this if I end up having what to say.

 

 

 

Tagged , ,

Coloring graphs with polynomials

More chromatic hoonja-doonja!

Suppose you have a bunch of tokens of different colors and weights.  X_1 colors of weight 1 tokens, X_2 colors of weight 2 tokens, etc.

Let Γ be a graph.  A (weighted) b-coloring of Γ is an assignment to each vertex of a set of tokens with total weight b, such that adjacent vertices have no tokens in common.  Let χ_Γ(X_1, … X_b) be the number of b-colorings of Γ.  I made up this definition but I assume it’s in the literature somewhere.

 

First of all, χ_Γ(X_1, … X_b) is a polynomial.

Is this multivariable “chromatic polynomial” of any interest?  Well, here’s one place it comes up.  By a degree-b polynomial coloring of Γ we mean an assignment of a monic squarefree degree d polynomial in R[x] to each vertex of Γ, so that adjacent vertices are labeled with coprime polynomials.   Now let U_b(Γ) be the manifold parametrizing degree-b colorings of Γ.

Then the Euler characteristic of U_b(Γ) is χ_Γ(-1,1,0,…0).

I worked this out via the same kind of Lefschetz computation as in the previous post, but once you get the answer, you can actually derive this as a corollary of Stanley’s theorem.  And it was presumably already known.

By the way:  let V_n be the free vector space spanned by the b-colorings of Γ where all the tokens have weight 1; these are called fractional colorings sometimes.  Then S_n acts on V_n by permutation of colors.  The character of this action is a class function on S_n.  More precisely, it is

χ_Γ(X_1, … X_b)

where X_i is now interpreted as a class function on S_n, sending a permutation to the number of i-cycles in its cycle decomposition.  Of course the real thing going on behind the scenes is that the V_n form a finitely generated FI-module.

Tagged , , ,

Counting acyclic orientations with topology

Still thinking about chromatic polynomials.   Recall: if Γ is a graph, the chromatic polynomial χ_Γ(n) is the number of ways to color the vertices of Γ in which no two adjacent vertices have the same color.

Fact:  χ_Γ(-1) is the number of acyclic orientations of Γ.

This is a theorem of Richard Stanley from 1973.

Here’s a sketch of a weird proof of that fact, which I think can be made into an actual weird proof.  Let U be the hyperplane complement

\mathbf{A}^|\Gamma| - \bigcup_{ij \in e(\Gamma)} (z_i = z_j)

Note that |U(F_q)| is just the number of colorings of Γ by elements of F_q; that is,  χ_Γ(q).  More importantly, the Poincare polynomial of the manifold U(C) is (up to powers of -1 and t) χ_Γ(-1/t).  The reason |U(F_q)| is  χ_Γ(q) is that Frobenius acts on H^i(U) by q^{-i}.  (OK, I switched to etale cohomology but for hyperplane complements everything’s fine.)  So what should  χ_Γ(-1) mean?  Well, the Lefschetz trace formula suggests you look for an operator on U(C) which acts as -1 on the H^1, whence as (-1)^i on the H^i.  Hey, I can think of one — complex conjugation!  Call that c.

Then Lefchetz says χ_Γ(-1) should be the number of fixed points of c, perhaps counted with some index.  But careful — the fixed point locus of c isn’t a bunch of isolated points, as it would be for a generic diffeo; it’s U(R), which has positive dimension!  But that’s OK; in cases like this we can just replace cardinality with Euler characteristic.  (This is the part that’s folkloric and sketchy.)  So

χ(U(R)) = χ_Γ(-1)

at least up to sign.  But U(R) is just a real hyperplane complement, which means all its components are contractible, so the Euler characteristic is just the number of components.  What’s more:  if (x_1, … x_|Γ|) is a point of U(R), then x_i – x_j is nonzero for every edge ij; that means that the sign of x_i – x_j is constant on every component of U(R).  That sign is equivalent to an orientation of the edge!  And this orientation is obviously acyclic.  Furthermore, every acyclic orientation can evidently be realized by a point of U(R).

To sum up:  acyclic orientations are in bijection with the connected components of U(R), which by Lefschetz are χ_Γ(-1) in number.

 

 

 

Tagged , , , , ,
Follow

Get every new post delivered to your Inbox.

Join 697 other followers

%d bloggers like this: