|
|
You are viewing the most recent 20 entries September 8th, 200910:55 am: A graph-theoretic question
Given my friends list this is as good a place as any to post math questions, so here goes: I have a undirected graph G=(V,E) and I also have a natural total order ≤ on the set V. With this I can immediately produce a directed acyclic graph G2=(V,E2) where, for x,y ∈ V, there is a directed edge from x to y in E2 (written x→y ∈ E2) whenever there is an edge from x to y in E and x ≤ y (in the total order). I am looking for cliques in the original graph. I know the maximum clique problem is NP-complete, but I'm hoping I can exploit the total order to solve the problem with way less work. Specifically, I'm looking for the largest set S ⊆ V such that for every x,y ∈ S, x ≤ y implies x → y ∈ E2 and y ≤ x implies y → x ∈ E2. That is to say, every node in S is incident with every other node in S in a way respecting the total order. S will form a clique in the original undirected graph G. Does this sound like a familiar problem? I'm no expert on graph theory would have expected there to be a fair amount of literature on directed analogues of the clique problem, but can't find any description of it. I'm also wondering if my expectation that this is a simpler problem than the undirected clique problem is naive. It seems simpler, and the total order suggests that I should be able to break up the graph into subpieces and solve the clique problem on this smaller set, then hook the cliques together. However, I don't see how it involves any loss of generality and that concerns me. Even though my total order is a natural one which the problem itself imposes, if there's truly no loss of generality then it would be possible to solve the clique problem on any graph simply by choosing an arbitrary total order and employing this newly-created 'special structure' which seems very fishy. It may be that there's something further specific to my problem which imposes special structure that I haven't captured in this description. Tags: clique, graph theory, math
November 3rd, 200805:29 pm: This is why Arar can't get off the no-fly list?
The Ottawa Citizen has a story about Canadian/American intelligence co-operation which features a quote from a speech at a security conference by one Christopher Sands of the Hudson Institute about Maher Arar: "I don't think that we're convinced Maher Arar was vindicated or acquitted by your process," Mr. Sands said, referring to the O'Connor judicial inquiry. "What you did was re-evaluate the treatment of Maher Arar and decide that procedural mistakes along the way had been made. That didn't vindicate him from the charge that he was involved in fundraising for terror. Excuse me? I feel I've been following the Arar case quite closely, and while it's possible I missed something I have never even heard before that he was "charged" with terrorist fundraising. ( Read more... )Tags: arar
October 15th, 200812:00 am: Quote from Clemenceau
"Une dictature est un pays dans lequel on n'a pas besoin de passer toute une nuit devant son poste pour apprendre le résultat des élections." It's midnight; think I'll go to bed now. Tags: federal election
September 12th, 200807:29 am: Anti-information
A nice succinct quote about the reaction to Sarah Palin's selection by McCain supporters, by someone I'm not used to quoting: There's a photograph circulating on conservative blogs that shows Palin lounging on a motorcycle, paired with another of Obama in a helmet on a bicycle. It's headed: "All you need to know." Personally I need to know a little more. That's not even insufficient information. It's anti-information — a denial that information matters. — David Frum, New York Magazine
July 23rd, 200809:58 am: Putting the Mean back in Mean Value Theorem
Hmm, I can't think of another recent case of such a direct instance of the Mean Value Theorem being applied so visibly. I know photo radar really does the same thing. However, because the time points in photo radar are so much closer, in the popular mind it's measuring instantaneous velocity rather than computing an average. It's all the same, really, but I expect with the "average speed" cameras people will feel the victims of oppressive mathematics rather than believe they were fairly caught out. I wonder what the response would be if a believer in constructivist mathematics responded to an automated speeding ticket with a demand for a witness? Tags: law, mean value theorem
June 2nd, 200811:23 am: About damn time...
The Globe and Mail is now putting their full daily content online without a paid subscription model. For years I have been going through all kinds of tricks to find the content (mostly just Googling for the headline to find the same story at G&M affiliate sites), with varying success. I guess the Globe has realized what I've long thought to be true and which the New York Times finally realized nine months ago: for a big enough newspaper, the ad revenue generated from a free site likely outweighs the revenue from subscriber fees in a subscription model.
February 5th, 200805:35 pm: Too-fast indexing from Google?
At 17:15 EST, I created a Wikipedia article about a Rwandan government minister. In the interests of adding more content, I happened to be googling the subject of the article. My Wikipedia article, then less than 15 minutes old, came up as the second hit. I suppose Google's indexing bot might have hit the page and updated its search cache in those 15 minutes, but that seems a little implausible, no? I find this search result to be rather creepy. My first ill-conceived paranoid thought was that my being logged in to Gmail had somehow enabled Google to monitor my Wikipedia edits, but I suppose the more natural and innocent explanation is that Google is using the Recent Changes RSS feed from Wikipedia to update its own search results. Still, I wasn't aware that Google employed site-specific change tracking like this. And wouldn't such an indexing strategy generate an awful lot of false hits owing to constant vandalism of Wikipedia? Perhaps they have a more refined strategy, such as updating based on all edits from 15 minutes ago that have not since been reverted. Tags: google, wikipedia
November 5th, 200712:05 pm: On being adopted
It feels strange to be part of a small minority which is directly and uniquely affected by provincial legislation, but this is the case. Being adopted (and yes, for me it is a question of being rather than having been) is a strange sort of "optional minority" status: a truth which I can selectively reveal but of which I am always aware, even if I don't always think of it. Both my sister and I were adopted, so there were no blood relatives in my immediate family: even now I still find watching two relatives to be a novelty. Of course, a large part of this interest comes from speculating about my unknown birth relatives. I know a little about them, thanks to the Non-Identifying Infomation which was released to my parents when they adopted me; the idea is to paint a picture of the birth family, short of giving enough to find them. Which is of course exactly what I want to do. ( Read more... )
Tags: adoption disclosure
May 17th, 200711:42 am: On Facebook
Good god, Facebook is a terrifying and awesome construction. It's easy to take it for granted at first, because it's one of a long line of social-networking sites I have joined, and the pattern is now a familiar one: join, watch a bunch of my university friends join too, then watch the system slowly starve to death as the initial rush fades. Facebook is still on the rise, and its unique features (mostly, the wall-posts) will probably sustain its rise for some time yet. But the singular reason it is so terrifying is its penetration. ( Read more... )Current Mood:  contemplative January 19th, 200604:04 pm: Deep Blue is not quite yet a grandmaster
It's pretty mild as gaffes go, but Harper's strange statements of yesterday show that he's not above making mistakes. There's been a lot of talk about him avoiding the word "majority", but it's inevitable that he'd talk about it at this point. What's really odd is that his intent was to reassure people: don't worry that I have a sinister agenda, because any such agenda would be blocked by the Liberal-dominated government apparatus. It's not terribly hard to spin this to conclude that: 1) Harper indeed does have a sinister agenda, and 2) since Harper believes the judiciary and civil service is full of Liberal stooges, the first thing he'll do as PM is purge them and put in his own political stooges. This message is hardly the reassuring effect he was shooting for. Maybe it's just because the Alito hearings going on right now, but I must say that Harper's description of the "judicial temperament" and "ability to competently and shrewdly and wisely apply the laws that are passed" that he'd look for in his appointees reminded me quite strongly of the "strict constructivism" so beloved by Republicans.
January 17th, 200603:05 pm: The sound of inevitability
I've been pretty lucky in my adult life thus far: I followed politics for quite some time before I developed comprehensive political opinions. As such, the great electoral disappointments of my life — the victories of the federal Tories in 1984 and 1988, and the defeat of the NDP at the hands of Mike Harris in 1995 — mostly preceded deep concern on my part about election results. I did follow the 1995 Ontario election, and I certainly came to despise the Harris government afterwards, but at the time I remember mentally shrugging at its victory.
There have been defeats, but they've been muted for various reasons. Harris was re-elected in 1999: this was, however, a continuation of an unpleasant status quo and therefore somehow more palatable. Bush got in for two terms, but that was the States.
Now we all hear the sound of inevitability. ( Read more... )
Powered by LiveJournal.com
|
|
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
listless
amused