16,119 reputation
1397147
bio website gowers.wordpress.com
location
age
visits member for 5 years, 6 months
seen Apr 17 at 10:31
Mathematics professor at Cambridge

Oct
26
comment Believing the Conjectures
As for Maximize, I find it unhelpful in this context, since it is not clear what is "likely to occur". For example, it is still open whether there exists an infinite-dimensional Banach space such that every operator defined on it is a multiple of the identity plus a nuclear operator. I feel as though the answer could go either way, and no principle like Maximize is going to alter that perception. On the other hand, the existence of examples with comparable properties, such as Argyros and Haydon's construction where "nuclear" is replaced by "compact", does have an impact.
Oct
26
comment Believing the Conjectures
The fact that there ought to be a separable example is too trivial to count as a success of Reflection, since if there is any example at all, you can take a separable subspace of it and then you've got a separable example.
Sep
8
comment Is every distance-regular graph vertex-transitive?
Yes, but the hypercubes are vertex transitive, as are most of the obvious families.
Sep
6
comment A combination of two well-known complexity problems
@joro, what you're asking is in a sense what's in the back of my mind when I asked the original question: hard instances of graph isomorphism are rather delicate, so can they be combined with a condition about containing Hamilton cycles? If they can't, then the answer to my question is that you can indeed distinguish between the two situations.
Sep
6
comment A combination of two well-known complexity problems
@Suvrit, if you were to take two typical hard instances for the Hamilton cycle problem, one that contains a Hamilton cycle and one that doesn't, then it is very likely that it will be easy to tell that they are non-isomorphic. (For example, their degree sequences are likely to differ.) In the other direction, if you have two graphs of large minimal degree that are a difficult case for graph isomorphism, they will both contain Hamilton cycles. I'm not sure whether this is answering your question though.
Sep
6
comment A combination of two well-known complexity problems
@Gerhard "I'm sure it's the latter" Paseman, it's only half the latter. I know what zero-knowledge proofs are, but don't immediately see how they answer the question. Could you spell it out?
Sep
6
comment A combination of two well-known complexity problems
@Richard Stanley -- that's why I insist that they are both hard, though obviously if graph isomorphism is hard then so are NP-complete problems so I could have just said "assuming that graph isomorphism is hard".
Sep
5
comment A combination of two well-known complexity problems
A quick remark: one can of course ask the same question for many other NP-complete problems -- I'd be just as interested, for example, in the same question but with "clique of size m" instead of "Hamilton cycle".
Apr
3
comment Almost orthogonal vectors
Looking at this almost a further year later, I'm still confused by Bill's remark, because what I wrote in the previous comment seems (i) correct and (ii) the standard volume argument that he discusses. Can anyone shed light on this?
Mar
31
comment What are the Applications of Hypergraphs
Here are two partial explanations for why algorithms based on hypergraphs are less common than algorithms based on graphs. 1. Some polynomial-time algorithms for graphs turn into NP-complete problems when you try to generalize them to hypergraphs (e.g., finding a perfect matching). 2. We often use graphs to model symmetric binary relations, and symmetric binary relations appear much more frequently than symmetric ternary relations (and beyond).
Mar
31
comment functions satisfying “one-one iff onto”
Does $f$ have to be continuous, or something like that? Otherwise, the result seems to be trivially false because you can mess about with the map on a set of measure zero.
Mar
30
comment Family of subsets such that there are at most two sets containing two given elements
It is perhaps worth adding that the above construction is generated by two standard tricks. The first is to dualize the problem by defining $T_i$ to be the set of $k$ such that $i\in S_k$ and reformulating the conditions in terms of the $T_i$. (The main one says that the maximum intersection of any two $T_i$ is 2.) The other trick is to use graphs of polynomials to get plenty of sets with small intersections.
Mar
30
comment Family of subsets such that there are at most two sets containing two given elements
Thanks a lot -- I've edited it now.
Mar
25
comment Family of subsets such that there are at most two sets containing two given elements
Have you tried taking the characteristic functions of the $S_i$, adding them up, and looking at the $\ell_2$ norm? The condition on the $S_i$ should put a strong condition on the average inner product, and then the Cauchy-Schwarz inequality should give a bound the other way. I feel this ought to work, but can't quite be certain without writing it down.
Mar
23
comment Do good math jokes exist?
Approximately two and a half years later I see that I didn't write what I intended to write. I did of course intend to write "compact" -- or else the joke makes no sense. In other words, Andrew Stacey's version is what I intended (except that in my version there was just one examiner).
Feb
28
comment How to mentor an exceptional high school student?
I've always wondered how people know they've been downvoted. Is it by repeatedly checking the number of votes so that one catches it after it decreases and before it increases again? Or is there some more efficient method that I've been too stupid to work out?
Feb
7
comment Economical hard word problem
I don't know whether this suits my motivation until I've messed around with it for a while. But it looks promising, so many thanks. (Sorry for not writing this earlier -- I've been away from Mathoverflow for a while.)
Dec
27
comment Economical hard word problem
It looks to me as though these examples aren't quite what I'm looking for, interesting though they are. I haven't properly understood the first paper you refer to, but it looks as though it takes an arbitrary semigroup and encodes it as one with just three relations. From that I deduce that the relations are probably very complicated. I think I'm more interested in the relations being short than in there being few of them, though I'd like the latter as well. Also, if there are many relations but they can be easily grasped (as occurs in, say, the braid group on n generators) I would be happy.
Dec
27
comment Economical hard word problem
That might be OK, but not all such sets would be convenient. For example, I think one can probably have some fun exploring patterns that can be made with Penrose tiles, but writing anything down symbolically would be a nuisance.
Dec
27
comment Economical hard word problem
@Dylan, I don't know if I'm looking at the same example, but if I am, then I don't like it because it encodes another problem. Maybe I should add that as a further restriction. In fact, I think I will.