## Clearly, evidently, unambiguously

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.

## 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.

## 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.

## Metric chromatic numbers

Idle thought.  Let G be a (loopless) graph, let M be a metric space, and let b be a nonnegative real number.  Then let Conf(G,M,b) be the space of maps from the vertices of the graph to M such that no two adjacent vertices are within b of each other.

When b=0 and G is the complete graph K_n, this is the usual ordered configuration space of n points on M.  When G is the empty graph on n vertices, it’s just M^n.  When M is a set of N points with the discrete metric, Conf(G,M,b) is the same thing for every b;  a set of points whose cardinality is χ_G(N), the chromatic polynomial of G evaluated at N.  When M is a box, Conf(G,M,b) is the “discs in a box” space I blogged about here.  If M is (Z/2Z)^k with Hamming distance, you are asking about how many ways you can supply G with k 2-colorings so that no edge is monochromatic in more than k-b-1 of them.

Update:  Ian Agol links in the comments to this paper about Conf(G,M,0) by Eastwood and Huggett; the paper points out that the Euler characteristic of Conf(G,M,0) computes χ_G(N) whenever M has Euler characteristic N; so M being N points works, but so does M = CP^{N-1}, and that’s the case they study.

When b=0 and G is the complex plane, Conf(G,C,0) is the complement of the graphic arrangement of G; its Poincare polynomial is  t^-{|G|} χ_G(-1/t).  Lots of graphs have the same chromatic polynomial (e.g. all trees do) but do they have homeomorphic Conf(G,C,0)?

This is fun to think about!  Is Conf(G,M,0), for various manifolds other than discrete sets of points, an interesting invariant of a graph?

You can think of

vol(Conf(G,M,b)) vol(M)^{-n}

as a sort of analogue of the chromatic polynomial, especially when b is small; when M = C, for instance, Conf(G,M,b) is just the complement of tubular neighborhoods around the hyperplanes in the graphical arrangement, and its volume should be roughly b^|G|χ_G(1/b) I think.  When b gets big, this function deviates from the chromatic polynomial, and in particular you can ask when it hits 0.

In other words:  you could define an M-chromatic number χ(G,M) to be the smallest B such that Conf(G,M,1/B) is nonempty.  When M is a circle S^1 with circumference 1, you can check that χ(G,M) is at least the clique number of G and at most the chromatic number.  If G is a (2n+1)-cycle, the clique number is 2, the chromatic number is 3, and the S^1-chromatic number is 2+1/n, if I did this right.  Does it have anything to do with the Lovasz number, which is also wedged between clique number and chromatic number?  Relevant here:  the vector chromatic number, which is determined by χ(G,S^{v(G)-1}), and which is in fact a lower bound for the Lovasz number.

## Is a search a search?

(Continued from yesterday’s post.)

Scalia understood, when he needed to, that words changed their meaning, and stretched to accommodate cases that didn’t exist for the founders.  What, in the sense of the Fourth Amendment, counts as a “search”?  Scalia took up this lexical question in Kyllo vs. U.S, writing that infrared scanning of a house to detect excess heat (generated, the police correctly inferred, by a marijuana greenhouse within) did indeed constitute a search.  This is not the kind of search the Framers contemplated.  Nonetheless, says Scalia:

When the Fourth Amendment was adopted, as now, to “search” meant “[t]o look over or through for the purpose of finding something; to explore; to examine by inspection; as, to search the house for a book; to search the wood for a thief.” N. Webster, An American Dictionary of the English Language 66 (1828) (reprint 6th ed. 1989)

How to read this?  The written definition can be read to include viewing a house from the outside, and indeed, Scalia brings it up in this context:

One might think that the new validating rationale would be that examining the portion of a house that is in plain public view, while it is a “search”1 despite the absence of trespass, is not an “unreasonable” one under the Fourth Amendment.

But visual inspection of a house has not been classified as search by the Court — “perhaps,” Scalia says, “in order to preserve somewhat more intact our doctrine that warrantless searches are presumptively unconstitutional.”

In fact, it’s pretty clear from other Scalia opinions that he chooses a meaning for the word “search” which is simultaneously more restrictive than the dictionary definition —  it excludes visual inspection of a house — and more inclusive than the contemporary plain-language meaning.  To push a stereo away from the wall and look at its serial number, as in Arizona v. Hicks, is not to “search” the stereo; it’s not even clear whether, in standard English, a stereo can be searched, unless by pulling open the casing and digging through its insides.  But in Scalia’s majority opinion there, the moving of the stereo is what creates the search:

A truly cursory inspection – one that involves merely looking at what is already exposed to view, without disturbing it – is not a “search” for Fourth Amendment purposes, and therefore does not even require reasonable suspicion… [t]aking action, unrelated to the objectives of the authorized intrusion, which exposed to view concealed portions of the apartment or its contents, did produce a new invasion of respondent’s privacy unjustified by the exigent circumstance that validated the entry. This is why, contrary to JUSTICE POWELL’S suggestion, post, at 333, the “distinction between looking’ at a suspicious object in plain view and moving’ it even a few inches” is much more than trivial for purposes of the Fourth Amendment. It matters not that the search uncovered nothing of any great personal value to respondent – serial numbers rather than (what might conceivably have been hidden behind or under the equipment) letters or photographs. A search is a search, even if it happens to disclose nothing but the bottom of a turntable.”

So a “search,” for Scalia, requires observation of something that might reasonably be expected to be private, but doesn’t require looking inside of the thing searched.  I think that’s a pretty good definition; but it’s not what’s in the dictionary, it’s not the way we use the word in plain Enlglish, and Scalia makes no claim that it’s what was in the Framers’ minds.  It’s a definition you choose in order to achieve a goal, the goal of a workable evidential rule that suits our — or someone’s — sense of justice.

And that’s why it grates when Scalia says “[a] search is a search.”  So matter-of-fact, so direct; but so utterly opposite to what’s actually happening!  He should have said “A search is what we define a search to be.”

In light of Scalia’s take on statistical sampling, his rejection of Powell’s dissent is interesting:

As for the dissent’s extraordinary assertion that anything learned through “an inference” cannot be a search, see post, at 4-5, that would validate even the “through-the-wall” technologies that the dissent purports to disapprove. Surely the dissent does not believe that the through-the-wall radar or ultrasound technology produces an 8-by-10 Kodak glossy that needs no analysis (i.e., the making of inferences)

To measure radiation emanating from the outside of a house, and to infer by technological means something about the contents of the interior that can’t be directly observed:  this, for Scalia, is a search.  To count all the inhabitants of a city you can find, and to infer by technological means something about the people who couldn’t be directly observed:  that, Scalia says, isn’t counting.  In Kyllo, Scalia is happy to speculate about future technologies that will make his view more obviously correct, as soon as they exist (“The ability to “see” through walls and other opaque barriers is a clear, and scientifically feasible, goal of law enforcement research and development.”)  In Commerce, his vision of technological progress in statistics is decidedly more pessimistic.  Why?

## Midwestern deli heresy

Gave colloquium at Michigan yesterday and stopped at Zingerman’s at the way out of town to pick up some supplies I can’t get in Madison:  belly lox, pastrami, and tongue.

Zingerman’s is, of course, nationally famous as a deli outpost in the vast pastramiless reach of the Upper Midwest.  (Is there even a deli in Chicago that’s as famous?)  And the food there is indeed pretty great.  But here’s my Midwestern deli heresy:  I think the meat at non-nationally-famous Katzinger’s, in Columbus, Ohio, is better.

## Antonin Scalia thought jurisprudence was more like math than it really is

I didn’t mean for Antonin Scalia to be a major character in my book.  I was just going to write about an interesting math snafu that shows up in one of his capital punishment opinions.  But then that led quite naturally into talking about “formalism,” which many mathematicians use (or think of themselves as using) as their everyday philosophy of math, just as Scalia used it (or thought of himself as using it) as his everyday philosophy of jurisprudence.

Legal reasoning is not much like math.  But Scalia sometimes acts like he thinks it is.  That’s what makes him an interesting figure to me.  He writes down arguments which he presents as derivations axioms — as if the words of the Constitution determined the resolution of the legal question, so long as you were willing to apply them methodically and impartially in the correct sequence.

But surely that’s wrong!  The words of the Constitution underdetermine a lot of really interesting questions.  Richard Posner:

Most of the cases the Supreme Court agrees to decide are tossups, in the sense that they cannot be decided by conventional legal reasoning, with its heavy reliance on constitutional and statutory language and previous decisions. If they could be decided by those essentially semantic methods, they would be resolved uncontroversially at the level of a state supreme court or federal court of appeals and never get reviewed by the Supreme Court.

I have written before about the Court’s decision that statistical sampling in the Census is in conflict with the relevant Constitutional clause:

Representatives and direct taxes shall be apportioned among the several states which may be included within this union, according to their respective numbers, which shall be determined by adding to the whole number of free persons, including those bound to service for a term of years, and excluding Indians not taxed, three fifths of all other Persons. The actual Enumeration shall be made within three years after the first meeting of the Congress of the United States, and within every subsequent term of ten years, in such manner as they shall by law direct.

Scalia’s opinion concentrates on the word “enumeration,” which he argues does not mean “determining the number of,” but rather should be understood in the more restrictive sense of “counting one by one.”  And he has some good contemporary sources for this reading!  You get a nice satisfying no-nonsense feeling, reading this opinion.  Then you start to think about what it actually says. Is Scalia declaring that constitution requires that the census count people one by one?  Can’t be — for the last fifty years the census has been conducted mostly by mail.   Does he think the census has to enumerate something, but it doesn’t have to be people?  Could it be anything?  Could it be “all property owners?”  Could it be “all non-atheists?”

Note, too, that when you fill out the census form, you write down the number of people in your household, then you fill out information for each person.  When the numbers are compiled, the computer, surely, adds up the numbers from each form to get an answer.   In other words:  a mathematical process other than enumeration-in-the-narrow-sense whose output is an approximation to the total number of people in the United States.  Kind of like statistical sampling.  Except not as good an approximation.

I don’t think we should consider that process unconstitutional.  It seems reasonable to consider it an enumeration, despite the inconsistency with some dictionary definitions.  Because dictionary definitions aren’t mathematical definitions.  A mathematical object is exactly what it is, and nothing else.  But when we read a word, we make a choice.

Scalia makes one choice: we could also opt for a more expansive but equally common-sensical definition of “enumerate” as “determine, to the extent possible, the number of,” which permits statistical sampling aimed at counting the “whole number” of Americans.  That “whole” is a word in the Constitution too, with as much binding force as “enumeration.”  It doesn’t appear in Scalia’s opinion.

Am I saying Scalia’s opinion in Dept. of Commerce vs. U.S. House of Representatives was wrong?  No; I’m saying merely that it’s not the kind of opinion it presents itself as being.  It is not determined by the text before it.  It relies, elsewhere, on an argument from pragmatism:  if statistical sampling is constitutionally permissible, then legislatures might authorize it, and the resulting partisan wrangling over methodology would create hard cases for future courts.  These are fair arguments, but they’re not textual arguments.  The argument admits that we make choices when deciding what words mean, and we should let our choices be guided by their likely consequences.

But no, I don’t think those arguments are obviously wrong.  It is pretty rare to find Scalia being obviously wrong.  Except in the following higher-level sense.  Scalia seldom concedes that the questions he faces are authentically difficult.  He — or at least the character of “Scalia” he plays in the opinions — lacks the humbleness appropriate to the task.  His habit is to present his conclusion as if it’s obviously right, the way a mathematical proof, once you understand it, is obviously right.  That is obviously wrong.

Update:  Commeter aaaatos makes a really important point, one I meant to address directly in the post.  He writes:  “what makes the legal system so useful to mankind is the fact that therein law is treated in a formalistic way as much as possible, i.e. as if it were mathematics.”  This points to another plausible account of Scalia:  that he didn’t actually believe law was very much like math, but felt it was best practice for judges to pretend to believe that.  That’s what I was getting at with the distinction between Scalia the person and “Scalia,” the persona he adopts as a writer of opinions.

Why pretend?  Partly because it enhances the authority of the process; partly because pretending to believe it helps us be “as formalist as possible,” mildly constraining the inevitably biased choices we make when we read words and try to obey them.

Tagged , , , ,

## The furniture sentiment

Today’s Memorial Library find:  the magazine Advertising and Selling.  The September 1912 edition features “How Furniture Could Be Better Advertised,” by Arnold Joerns, of E.J. Thiele and Co.

Joerns complains that in 1911, the average American spend $81.22 on food,$26.02 on clothes, $19.23 on intoxicants,$9.08 on tobacco, and only $6.19 on furniture. “Do you think furniture should be on the bottom of this list?” he asks, implicitly shaking his head. “Wouldn’t you — dealer or manufacturer — rather see it nearer the top, — say at least ahead of tobacco and intoxicants?” Good news for furniture lovers: by 2012, US spending on “household furnishings and equipment” was at$1,506 per household, almost a quarter as much as we spent on food.  (To be fair, it looks like this includes computers, lawnmowers, and many other non-furniture items.)  Meanwhile, spending on alcohol is only $438. That’s pretty interesting: in 1911, liquor expenditures were a quarter of food expenditures; now it’s less than a tenth. Looks like a 1911 dollar is roughly 2012$25, so the real dollars spent on alcohol aren’t that different, but we spend a lot more now on food and on furniture.

Anyway, this piece takes a spendidly nuts turn at the end, as Joerns works up a head of steam about the moral peril of discount furniture:

I do not doubt but that fewer domestic troubles would exist if people were educated to a greater understanding of the furniture sentiment.  Our young people would find more pleasure in an evening at home — if we made that home more worth while and a source of personal pride; then, perhaps, they would cease joy-riding, card-playing, or drinking and smoking in environments unhealthful to their minds and bodies.

It would even seem reasonable to assume, that if the public mind were educated to appreciate more the sentiment in furniture and its relation to the Ideal Home, we would have fewer divorces.  Home would mean more to the boys and girls of today and the men and women of tomorrow.  Obviously, if the public is permitted to lose more and more its appreciation of home sentiment, the divorce evil will grow, year by year.

Joerns proposes that the higher sort of furniture manufacturers boost their brand by advertising it, not as furniture, but as “meuble.” This seems never to have caught on.

Tagged , , ,

## The Story of a New Name

2016 reading project is to have more than half my reading be books in translation.  So far this has translated into reading Ferrante after Ferrante.  Not really feeling equal to the task of writing about these books, which color everything else around them while you read.  The struggle to be the protagonist of your own story.  Gatsby is a snapshot of it, Ferrante is a movie of it.

Tagged , ,