Long Paths and Expanders

Posted on August 19, 2013 by dominicyeo

I’m in Birmingham this week for the LMS-EPSRC summer school on Random Graphs, Geometry and Asymptotic Structure. The event consists of three five-hour mini-courses, a plenary lecture, leaving plenty of time for problem sheet and discussion. I thought it would be worth trying to say a couple of interesting things each day – I do not know whether this will succeed, but I might as well try.

Today, a few thoughts on the first two lectures of Michael Krivelevich’s course on Long Paths and Hamiltonicity in Random Graphs. The aim is to develop tools to investigate the threshold for the presence of a Hamiltonian cycle in G(n,p). In this first part of the course, we were mainly thinking about long paths.

One tool we used a lot was the Depth-First Search algorithm. This is very similar to the exploration process I’ve talked about before. Essentially, here we consider trying to explore the graph in a depth-first way, but instead of viewing all the edges incident to a vertex we have just arrived at, we only look to see whether there is an edge out of the new vertex. If there is, we explore it, then come back eventually to look for more. It really comes down to a difference in the information we are storing. In this DFS, we store the vertices which we haven’t finished exploring, which is the set of vertices on the explored path between the root and the current vertex. So the size of this set evolves like the contour process. In particular, we can read off the sizes of paths from this description. These dynamics are useful in particular because we know there are no edges between the set of vertices we have finished exploring, and the ones we have yet to explore. The stack of ‘processing’ vertices must glue everything else together.

We can translate one of the arguments back into the language for the old exploration process. Recall the increments of the exploration process are $\mathrm{Bin}(\alpha n,\frac{c}{n}) -1$ once we have explored $\alpha n$ vertices. We don’t need to worry about the -1 bit for now. Observe that because we are exploring in a depth-first way, if a subsequence of the Binomial variables of length k are all positive, this corresponds to a path of length (k-1).

So to prove, for example, that the longest path in a subcritical random graph is O(log n), it suffices to prove that there are O(log n) consecutive positive entries in the sequence of n binomial entries. Since the distribution changes continuously, it is convenient to prove that there are O(log n) consecutive positive entries in the first $\epsilon n$ binomial entries. The probability that any of these entries is positive is bounded below by some p, so it suffices to consider instead a sequence of Bernoulli RVs with parameter p. So if we never have clog n consecutive, this gives control of the sequence of geometric random variables corresponding to the gaps between 0s in the sequence. Precisely, these are Geom(q), and we must have $\frac{\epsilon n}{c\log n}$ of them independently being less than clog n. We have to chase a few constants, and use the fact that if $f(n)\rightarrow\infty, \frac{g(n)}{f(n)}\rightarrow\infty$ , then

$(1-\frac{1}{f(n)})^{g(n)}\rightarrow 0,$

by comparison with the standard asymptotic result for $e^{-x}$. In any case, we get that this probability tends to 0 if we choose c small enough, and so with high probability there is a path of length clog n.

This is interesting, because we knew already that the largest component in a subcritical random graph had size O(log n). But we also knew that all the components were trees, or ‘almost trees’, and were uniformly chosen from the set of trees (or trees + an edge or two) with appropriate size. And the largest path in a UST on n vertices is $O(n^{1/2})$ with high probability. So we learn that there are enough components of size $\geq c\log n$ that it is actually very probable that one of them will have the unlikely property of being much more path-like than a typical tree.

Krivelevich also showed a pleasant elementary proof of the result that a supercritical random graph has a path of length O(n), using a similar idea.

The other definition of major interest was an expander graph. Often when doing calculations about neighbourhoods of sets of vertices, we run into the problem that the neighbourhoods may overlap, and so we cannot get the total outer neighbourhood (or outer boundary) just by summing over the individual neighbourhood sizes. In an expander graph, we demand that all small sets of vertices have neighbourhood at least as large as some constant multiple of the set size, essentially giving us a bound on the above problem. Concretely, G is a $(k,\alpha)$ -expander is for any set of vertices $|U|\leq k, |N(U)|\geq \alpha |U|$ .

There’s a very nice argument using Posa’s lemma, where we consider all the possible ways to rearrange the vertices in some longest path into a different longest path, and then focus on the endpoints of all these paths. With this so-called rotation-extension technique, we can show that a (k,2)-expander has a path of length at least 3k-1.

There are structural similarities between expander graphs and regular graphs, so it seems natural that there will be some interesting spectral properties. I don’t know much about this, but perhaps it will come up later in the week. But, returning to the random graph long path problem, it now suffices to show subcritical G(n,p) is a (clog n,2)-expander for some c. Expander properties are in some sense the opposite of clustering properties, and independence of a RG inhibit most clustering properties (as discussed in much greater detail in some of the posts about network models). Unfortunately, this doesn’t actually work, as in a subcritical graph, the typical expansion coefficient, even of a small set will be c, for G(n,c/n), which is not large enough. However, if you chose the constants carefully, such an argument should work for c>2, so long as you chose k=an, with a small enough that the probability of a vertex elsewhere in the graph being joined to (at least) two of the k vertices in the set, was small compared with (c-2).

REFERENCES

The course notes are not available, though chapter 3 from these 2010 notes by the same lecturer are related and interesting.

How much is the stacks project graph like a random graph? (quomodocumque.wordpress.com)
Welcome to Random Graphs and Complex Networks, T-79.7003 (randomgraphsaalto.wordpress.com)
Some old and new problems in combinatorics and geometry (gilkalai.wordpress.com)
The Binomial Distribution (squstat.wordpress.com)
Karger min cut problem (teacode.wordpress.com)
recent work on social networks and politics (orgtheory.wordpress.com)

Cambridge Linyi Summer School 2012 – Part Six – Jinan and Home

Posted on August 25, 2012 by dominicyeo

Thursday 23rd August

Whatever conspiracy theories were proposed yesterday were proved unfounded, as today we do indeed go to the mountain. First, however, are the student presentations. I am paired with Jonas, so my students present first to his group, then the reverse. I am extremely pleased with the Markov Chains presentations – it is clear that the speakers have not only understood much of the course than I’d suspected, but have put a great deal of thought and time into preparing a talk that would be well-selected, interesting and intelligible. Given what a disaster would result if I had to give a talk on probability in a foreign language, we were all very impressed with the standard of English shown in all the talks as well. I think everyone is agreed that this was an excellent high point on which to end our trip to Linyi.

Anyway, finally we are off to the Meng Shan mountain. The first stop is a family-run restaurant at the roadside on the edge of the forest park. While we drink tea on stools, we see a chicken being fetched from the outside coop by a Chinese lady with a cleaver and a determined glint in her eye. Sadly, our meal is meat-free, though some of the seasoning and spices go a long way to disproving the assertion that all vegetarian food is bland. The toilet is out back in an ominous brick hut in the middle of the apple orchard. To describe it as a ****hole would be inaccurate. There was no hole. Chris has evidently chosen a bad day for his experience of what our illustrious leader in absentia Marj Batchelor euphemistically defined as V&D. I view this as divine retribution for his shameless attempts to peer pressure me into the club last night.

The mountain itself is a maze of paths through forests, rocks and waterfalls. We are relatively pleased with the cardiovascular exertions of the journey to the main waterfall, until Georgios, who has forsaken the climb for a cable car tour, informs us we saw merely a quarter of the resort. Highlights include the questionable English on pretty much every visible sign, attempting to identify the silhouette of a sleeping Buddha apparently formed by a valley (topology in action?) and the tourist’s t-shirt declaring ‘Love Oneself. Slow. Vicious.’ Glibness aside, the view from the summit was astonishing, and rounded off an excellent visit.

Friday 24th August

Our final morning in Linyi is a ceremonial one. First we each receive a scroll, featuring a quotation by Linyi’s most famous philosopher, as notated by Linyi’s most famous calligrapher. Then we trek across campus for the obligatory photograph next to the stone commemorating the first edition of this summer school, adorned with sage words from Confucius and Dr Marj Batchelor. All that remains is to pack and brace oneself for the four hour drive across Shandong province to the capital, Jinan. Some of the students (who have come from universities in Jinan) are travelling with us. Evidently they had limited faith in the Linyi University accommodation, as we are sharing the bus with twenty duvets…

This is probably an excellent moment to thank the staff at Linyi, in particular Dr Lu, for everything they’ve done to organise and run this summer school. Everyone has been entirely helpful and welcoming, and we’ve all enjoyed our stay a great deal. Also Yuan, my teaching assistant, for her assistance with everything from translating probabilistic notation to advice on ice cream flavours!

I spend some of the journey thinking about whether you can think of measures and metrics as the same thing. I decide that you can’t. More accurately, I decide that I can’t. We are being housed in an impressive hotel on the campus at Shandong Polytechnic. A reunion with hot showers is most welcome. Dinner with our host professors is an astonishing spread. After everyone receives an amuse-bouche of a lightly sauteed sea cucumber, a dazzling array of local dishes arrive. The highlights are oysters, a ferociously spicy brain soup and a trio of donkey meats. We are strongly encouraged to try everything, and though it is a pleasure I am enormously full afterwards, and slightly nervous about maintaining my digestive composure during a 9am research talk tomorrow.

Saturday 25th August

If two attempts at delivering ‘Coalescence: various modern perspectives’ have taught me anything, it’s that I really need to improve my title selection skills. The schedule runs fairly late today, so the four speakers are asked at the last minute to cut the talks to 20 minutes, including time for questions and non-simultaneous translation, which proves a challenge too far. I overrun slightly so as to make sure I have actually got somewhere in terms of content. Many of the audience leave directly after my talk. I can only assume there is an unmissable commitment elsewhere in Jinan at 10.25 rather than any reflection on the quality…

After lunch, we are taken on a tour of Jinan, with stops at the two most famous sites, the Baotu Spring park, and the Daming Lake. As with some of the sights in Beijing, these are very much places of simple beauty and quiet reflection, and so are rather spoilt by the presence of crowds of tourists. A group of locals poke a floating log with umbrellas in an attempt to persuade a shy turtle to emerge from underneath. I can understand its reluctance. Nonetheless, the more peaceful areas were delightful. There is mild panic when we hear by email that the group departing on the late afternoon train are facing five hour delays. Ruadhai, Richard and I are starting to have misgivings about choosing an overnight train to Beijing for the ’experience’. In preparation, I am cautious in observing calls of gan bei, and avoid all dishes with visible chillis. The lack of any signs at Jinan railway station using the Western alphabet is a bit concerning, especially as our train, the illustrious K47, has a different display to all the other departures. After some pained gesticulation we ascertain that it is running half an hour late, so enjoy the additional time with the packs of people sleeping on the concourse. Eventually, just after midnight, the sleeper from Qingdao pulls in, so we join the human tide down to the platform, to see exactly what awaits us in coach 6…

Sunday 26th August

Well that cliffhanger was entirely justified. It turns out that hard seats rather than beds of some kind have been booked for us. Whether this was out of necessity or to enhance the sense of ‘experience’ I do not know. That said, we still feel like emperors in comparison to the scores of travellers who have standing tickets only. I had been worried that my suitcase might be anti-socially unwieldy, but it was as nothing compared to the guy who was travelling with only a 100kg sack of rice for company. Eventually, with everyone safely on board, and luggage stored in a variety of increasingly improvised locations, we steam off into the night. There is initial confusion when it turns out we have arrived at a different station in Beijing to what we had been expecting, but all is forgotten as we find a McDonalds and so by extension, coffee. Richard is suffering somewhat, but Ruadhai and I managed to get a reasonable amount of sleep, so decide to head across town to the airport. After check-in, I come across Ben – or at least, I think it’s Ben, but then all these Westerners look the same… – so we fill the time by talking about stochastic analysis and trying to spend our last handful of Yuan. The flight home is long and uneventful. The modern art instalment next to Gate 37 at Helsinki airport provides brief distraction, but finally back to London. An excellent trip is at an end!

Cambridge Linyi Summer School 2012 – Part Five – Finishing in Linyi

Posted on August 22, 2012 by dominicyeo

Sunday 19th August

Today’s lectures show greater promise, though we have stalled at around the 15 page mark of James Norris’s canonical textbook. I think a change of direction may be called for on Monday, just to avoid getting bogged down in the same calculations every time. The main excitement today was the burst water pipe caused by yesterday evening’s extraordinary thunderstorm. Annoyingly, I didn’t realise this until after I had loaded my laundry into one of the alfresco washing machines, so won’t have any usable clothes until tomorrow at the earliest. Still, worse things happen at sea. I was surprised to realise that I have now been in China for over two weeks. My only real hardship at this point is the limited choice of carbohydrates. Ruadhai agrees – this the probably the longest time an Irishman has gone without a potato since the Famine.

Monday 20th August

The water has returned to an extent. The shower provides only hot, and the washing machine only cold, but now both me and my clothes are clean so my happiness knows no bounds. We cover invariant distributions in the fifth lecture. I am confused why the students choose to ask only today what ‘distribution’ means when it has featured several times in every session so far. Nonetheless, by talking about convergence to equilibrium, I am glad we are approaching a natural finishing point for the course, as there’s nothing worse than a story with a weak ending. Over dinner there are toasts of varying degrees of seriousness with the dean as Siu is leaving tomorrow. The beer of choice is unsubtly called ‘WHEAT’. Afterwards, Karolina does an excellent job of teaching some basic Latin dance steps to an unexpectedly large gathering of the Cambridge group and some students. The plan for teacher-student bonding over the cha cha cha is a huge success. My many left feet are in high demand, but not quite as much as Jonas’s – I think tall blond Germans are something of a rarity in these parts.

Tuesday 21st August

I decide against including too many examples in today’s lecture and instead race through some material so that I can finish early and leave my students some time to prepare for the presentations which they will give on Thursday. The teaching component of this trip has been a challenge. My main difficulty was that I found it very hard to gauge whether the students were understanding what I was doing. In other situations, you can sense what any problems might be from the audience’s real-time reaction, but in China it is clearly a show of disrespect to make any such demonstration. On the other hand, some of the questions they finally realised it was acceptable to ask towards the end of the course, for example about the eigendecomposition of stochastic matrices, showed that the enterprise might have had some positive effect. And in my final lecture, I managed to get through two hours without breaking either a stick of chalk or the blackboard pulley mechanism for the first time… To celebrate the end of the courses, the group is heading out to a karoake bar in town, but my voice and my brain are tired, and I’m mindful of needing to be in full tenor in a few days, so I refrain. Well that’s the excuse I give: mainly I just despise karoake.

Wednesday 22nd August

Another rest day. For a second time, our planned day trip to the Meng Shan mountain and national park is cancelled because of concerns over the potentially dangerous weather, despite both the forecasts and the actuality showing sun and moderate temperatures all day. I feel rather like the little boy in To the Lighthouse, doomed forever to wonder what might have been. Perhaps reflecting the lack of much to do other than foment, various extravagant conspiracy theories are proposed. Instead we play a great deal more table tennis, and I meet my students briefly to help them prepare their presentations. Disappointingly, it seems several have already gone home, but I am confident those who remain will do a good job tomorrow. After dinner, we find a bar beside the Yi river which seems to be the focal point for the few foreigners who live here. Two Americans, Dwayne and Tom, regale us with stories of a year teaching English privately to the city’s swelling middle class. Most of them seem to revolve around implementations of their patented three-step local seduction technique. Apparently white skin and knowing how to say ‘Hello you sexy bitch’, ‘I have food for two at my apartment’ and ‘I don’t understand’ (in response to any attempt at further conversation) in Mandarin, is enough for a sizeable number of the maidens of Linyi. In case you were wondering, they found their current employment advertised on Craigslist. We also meet a young lady who makes a florid but vaguely plausible claim to be the daughter of a local mafia boss then immediately invites us all to a private room she has booked in a nearby club. Despite extreme attempts at coersion, I feel I have already exceeded my surreality limits for the day.

Cambridge Linyi Summer School 2012 – Part Four – Teaching in Linyi

Posted on August 18, 2012 by dominicyeo

Tuesday 14th August

When it rains in this part of the world, you certainly know about it. The skies turned black during breakfast and I was left feeling grateful for my trusty UKMT- issue umbrella. By the end of the day, however, there was no sign of any respite, and the way onto the campus resembled a river more than a road. We were invited to lunch with the Vice-President of the university at a nearby hotel. This proves a truly surreal experience. The selection of dishes is far more eclectic than anything we’ve seen so far. The fried cicadas were surprisingly nice. The sauce made all the difference. The slabs of tofu were less of a success, being more reminiscent of scouring pads than anything edible. The quantities were astonishing. Just when we thought we were making progress, we were each brought a pork tenderloin, served with a single segment of orange. A sequence of toasts was made: for each one the call of ‘gan bei’ demanded that we down our beers. Fortunately the glasses were small, but plans to write lectures and examples sheets in the afternoon had to be rearranged hastily! The Vice-President was very keen for everyone to say something in Chinese, especially the girls present, with mixed success. The few hours spent watching ‘Growing up with Chinese’ finally earned some reward. Tomorrow the raison d’etre of the trip begins, with the first lectures of our courses. I think everyone feels reasonably prepared, but also aware that we have no real idea what we should expect.

Wednesday 15th August

In the end, my first lecture went rather better than I could have expected. I had sat in on Robin’s first session in the morning, on basic statistical theory, and was surprised to chat to the students near the back and learn that some of them were not even science students. I guess their timid responses to relatively straightforward questions were understandable for English majors. My group, however, were all Linyi mathematics students and they seemed to have an excellent grasp of basic probability, so we made reasonably fast progress through the prerequisites, despite the language barrier, and so we should be ready to start the course (mine is on Markov chains) proper tomorrow. In many ways, this summer school is not so much about imparting knowledge of particular new subjects. Rather the focus is instead on promoting a Cambridge style of learning mathematics in Linyi, where the majority of learning seems to be via rote. To that end, today was actually a great success. I think choosing slightly easier material for the first lecture made the students feel more comfortable about answering questions in class and going up to the board to attempt various problems. Hopefully this promising trend will continue through the next five days! Meanwhile, as ever after teaching sessions, I cannot believe how tired I feel. Will be having an early night as soon as I have chosen some problems for tomorrow’s examples sheet.

Thursday 16th August

In the morning I give an examples class, in which we go through some exercises consolidating the material introduced yesterday, and then start another two hours of lectures after lunch. I am confused as to why the audience members are rather different to yesterday, but it seems that flexibility is the order of the day. Anyway, we made it through some of the elementary theory of memoryless random variables and Markov chains, with a view to starting work on ‘real’ examples tomorrow.

In other news, my table tennis skills have improved to the point where I was able to beat one of my students. My chopstick technique has enjoyed a similar transformation. The question of why a proud and technologically advanced nation continues to insist that a pair of glorified needles constitutes the best way to manipulate food is a mystery, but if these are the only route to fullness, you’ve rather got to man up and master them. Rice, fried eggs and chickpeas have provided excellent practice to raise one’s ability to the level required for the twice-daily dessert, banana, pear and tomato fruit salad. Meanwhile, our enthusiasm to spend our Yuan has devastated the campus shop’s supply of ice-creams.

Friday 17th August

My afternoon lecture was rather frustrating. We were talking about n-step transition probabilities, and had worked through the case of the general Markov chain with two states. All subsequent problems could be reduced to this, but it was an impossible task to persuade the students to use the general result which had taken us twenty minutes to develop and which was still sitting on the blackboard, rather than diving into another specific eigenvalue search. The problem is surely cultural. Here, great value is placed on being able to perform difficult computations competently, and this lessens the impact of theory which removes the need for repeated calculation. I’m unsure how to resolve the problem, except by continuing to give examples which are increasingly unyielding to ‘brute force’ methods. Tomorrow is a rest day, so there are plans afoot to examine the nightlife in the city centre with some other foreign residents in our building. I am exhausted by the combination of unrelenting heat and mathematics, so opt instead to join the group watching Groundhog Day in the kitchen. Although my feeling of ennui has declined sharply since the teaching began, aspects of the film feel dangerously similar to two weeks of maths at Linyi University.

Saturday 18th August

We have a day off to mark the halfway point of the teaching week. There is some consternation to learn that the main door to our accommodation, which also serves as the fire exit, is closed with a bike lock overnight. Conversely, our hosts have learned about last night’s club trip, and are apparently ‘very concerned’ for our safety. Hopefully some form of entente will be reached very soon. After lunch a group heads into the city once again, for a taste of ‘real’ life in China. Standards of public hygiene are, well, different. Everyone spits everywhere, and on the bus a mother holds out her little girl to pee all over the floor. Georgios is horrified – such indelicacy would be inconceivable in Athens. Our first stop is an enormous bookshop. Sections are devoted to, amongst others, poultry, adhesive science, and mushroom cultivation. Sadly mathematics does not feature. Jonas is amused to see an aisle devoted to Bildungsroman. This turns out to feature a collection of children’s adventures, all of whose characters appear to be Aryan. I retire to the piano music section. It is clear why the stereotype of prodigious young Chinese pianists exists. The majority of the available repertoire is etudes. That is an unhealthy quantity of Czerny and Burgmuller. I find some Debussy, Schoenberg and the complete Prokofiev sonatas in reasonable editions for a ridiculously low price. The joys of capitalist consumerism

Cambridge Linyi Summer School 2012 – Part Three – Talks in Linyi

Posted on August 13, 2012 by dominicyeo

Friday 10th August

On the Word document controlling the schedule of the summer school, today’s itinerary takes up more room than the rest of the fortnight combined. First up is the official opening ceremony. In the university’s main hall are sixteen armchairs with sixteen steaming pots of green tea set for our group, while the chancellor and the dean make the usual welcoming speeches, before a stream of photographs. After lunch, we are treated to a tour of the campus, and in particular the museum recording the history of the university. The exhibits detailing visits of influential local figures to the building site had an impact that was perhaps slightly lost in translation, but everyone enjoyed the large-scale model of the campus, partly because of its intricacy but also for its assistance in navigating the confusingly sprawling 6km wide site.

An opening banquet is scheduled for the evening, and indeed we turn up at the dining room to find an impressive spread on the lazy Susan. Soups, squids and a whole roasted carp are just the start as the dishes keep on arriving faster than we can possibly make possibly attend to them. We later find out that because the university party chairman could not make the date, this was not in fact the ceremonial dinner. We are intrigued to find out how the banquet could conceivably surpass this?

Saturday 11th August

The mathematical programme begins. For three days there is a series of seminars given by the Cambridge contigent and staff and students from Linyi, all in English. The quality is naturally quite mixed, but I doubt my mathematics would be up to much if I had to deliver a talk in Chinese! There is some confusion about pre-requisite knowledge: Georgios’ talk on ‘Post-Grothendieck Categorical Galois Theory’ gets off to a shaky start when the local students make it clear that they know neither what a category nor a Galois group is. Even the notion of a group causes some murmurings, so he decides to start from the very beginning instead. I don’t mind in the least: now I know the definition of a category! As lunch and dinner come round again, it becomes clear that last night’s feast was no rarity. The campus shop’s selection of red bean paste flavoured ice cream is also a new candidate for my favourite thing ever. My worries about eating well are no longer. For the princely sum of 6 Yuan (about 60p), we find a bottle of the local spirit from the campus supermarket. It smells like over-fermented Malibu but has a surprisingly complicated palate. The initial sensation of peaches gives way to something more woody and finally a heady aftertaste of anti-freeze.

Sunday 12th August

Another full day of seminars. The maths department at Linyi seems to specialise in graph theory, so I get to remind myself of the world of hyper-edges and vertex colouring problems. The highlight of the day is a trip into town. Well, I say town, but in fact Linyi is a city of 10 million people, according to Wikipedia. In spite of that, there doesn’t seem to be a whole lot to do in the centre of town, at least by the standards of Western cities. We have a look at the People’s Square then find a rapid restaurant, where a plate of noodles is a nice change from the rice that is the staple at the university. Afterwards, there are plans to find a bar, but Linyi seems to be somewhat lacking. Instead we check out a supermarket, where the few who remain outside are a major tourist attraction, and the rest of us examine the spirits aisle, where the local brew comes in varieties ranging from 6 to 17,000 Yuan. Unsurprisingly, the student mentality remains and we aim for the lower end of that range. An interesting evening, but with two weeks here remaining, it is slightly worrying that we might already have seen the best of Linyi.

Monday 13th August

I give my research seminar this morning. I choose to talk about coalescence, in particular the multiplicative kernel, essentially describing the skeleton of my Part III essay. It seemed reasonably suitable as it was possible to talk about several ideas and methodologies without actually working through any of the analysis involved in full. It also seemed an excellent opportunity to practise giving a talk on very little preparation. After all, apart from about five Cambridge people, no-one in the audience spoke much English… It was clear from the platform that many of the local undergraduates were engaged in other activities, and most of the remainder just smiled and nodded irrespective of the content. Nonetheless a worthwhile experience. Later, we were able to get into the university’s sports centre. On the ground floor we were greeted by the sight of thirty yellow-shirted ten year olds practising table tennis backhands in regimented unison with astonishing efficiency. The rooms upstairs were a bit less congested, and it was excellent to work off some energy in a way that maths can never quite achieve. And I suspect that by the time we leave, we may all be quite a lot better at badminton!

Cambridge Linyi Summer School 2012 – Part Two – Beijing continued

Posted on August 9, 2012 by dominicyeo

Tuesday 7th August

An early start to beat the Beijing rush hour. I’ve booked myself onto a bus tour of the area north of the city, including a visit to the famous Great Wall. First though, we stop at the Ming dynasty tomb at Dingling. Inside the burial chambers, which are dug deep into a wooded mountainside, the tombs themselves are somewhat less impressive than the stone thrones for the emperor and empresses. It turns out that the entire excavation was ransacked by Red Guards during the Cultural Revolution. The relics from the site were left to spoil, and the skeletons of the emperor and empress were removed and burned. Since then, plans to excavate other, grander tombs have been put on hold.

Then on to Mutianyu, a strategically-located mountain pass 70km north of Beijing. There we eat lunch at a rather touristy restaurant boasting the full range of lazy Susans and sweet and sour pork intestines. I get a chance to meet the rest of the group properly: Roger, Alfredo and Africa from Barcelona and Franz and Barbara, a couple from Basel who have spent the past four weeks in outer Mongolia, and have a fortnight left in China! I ask whether this is a once-in-a-lifetime trip and they look shocked – apparently they do this sort of thing every year.

Anyway, afterwards we board the cable car through the forest canopy and up to the wall. Approaching from below, it is a truly impressive spectacle, stretching for further than the eye can see along the skyline. Any Mongol hordes approaching from the north wouldn’t have stood a chance. The humidity is stifling and even the flatter sections feel like a fair hike. The climb up to the Chinese flag at the end of the main restored section proves a struggle for many, and the hawkers who have somehow raised a fridge up there are getting good business from selling water at 30 Yuan a bottle. The physical reality of the Great Wall is breath-taking, but even more so is the thought of the power of spirit than surrounded its construction. Over hundreds of years, for hundreds of miles and in the most inhospitable of locations, walls like this were built, restored and maintained, all by hand, and they endure to this day. Truly awe-inspiring.

Wednesday 8th August

The temperature hits a high of 35 degrees around lunchtime today, so I decide a slightly quieter day is called for. I head for the picturesque Beihai Park behind the Forbidden City, where a white pagoda rises mole-like from the Jade Island in the middle of the central lake. The water is full of Beijingers on pedalos. I feel equally energetic by the time I get to the top of the island – the marvellous view over the lakes and the sprawling hutong is reward enough for the sweat pouring from my forehead. A group of four Chinese twenty-somethings ask me to join them in posing for a photograph, seemingly in each of the 32 possible configurations, but I am in distinctly no rush, and enjoy the chance to practise my Chinese. I feel it is embarassing that the hotel’s talking mynah bird knows more phrases than I do, but it is improving. Mindful of meeting the Cambridge group tomorrow to travel south to Linyi, I spend the hottest hours of the day resting and doing some preparation work for my lecture course. The Guizhou restaurant I chosen for my final dinner in Beijing turned out to have been closed, so I trusted pot luck, and found a place specialising in the cuisine of Xinjiang in the far northwest. Unexpectedly, the meal is accompanied by intermittent belly-dancers and a optimistically enthusiastic guitarist. The food is somewhat less louche, the house special dapanji is a spicy chicken casserole. It is always easy to exaggerate such things, but my ‘small portion’ genuinely would have fed a party of four and left room to spare. I barely make it past the rim of the bowl before declaring defeat and trudging back heavily laden through Dongzhimen.

Thursday 9th August

I squeeze in a quick trip to the Olympic Park before leaving Beijing. For the first time since arriving it is a brilliantly sunny morning, which is somewhat unfortunate since the park is an entirely exposed concrete esplanade. The Bird’s Nest stadium is very striking though, as you wander through the beams which are somehow both disarranged and artful. Opposite, beside the Water Cube, is the food tent – dumplings and noodles as far as the eye can see! I go for steamed pork versions, before a bizarre dessert that describes itself as fried ice cream.

Then it’s time to join the gang at Beijing Nanzhan. The plan to meet is slightly fraught as the station is absolutely enormous (comparable to the Forbidden City on the overhead map) and is the home to six KFC’s, the agreed rendezvous point. Eventually everyone makes it in time for the high speed train south. It’s refreshing to catch up with the familiar faces at 300 km/h. There are 18 of us, so a bus seating 15 is sent to pick us up from the nearest station for the two hour run into Linyi. Only the driver gets a seatbelt. I’m just glad to get a seat. Not that many places are open in Linyi at 9.30, so we end up with our guides at a corner diner in the centre of town. There is confusion about whether the bowl of warm soy milk that everyone receives is a starter, a soup or a dessert. Matters improve with an onion omelette and further dumplings. The accommodation at the university is exciting. My roommate David and I are surprised to find a water-cooler and a widescreen television, yet there are no cupboards, or any other furnishings. The previous occupants have left us a small gift: a string bag of garlic shoved down the back of the TV stand. We spend a slightly futile twenty minutes attempting to swat mosquitos before turning in.

Cambridge Linyi Summer School 2012 – Part One – Travel and Beijing

Posted on August 6, 2012 by dominicyeo

Saturday 4th August

Painfully early start to Heathrow for the start of this Far Eastern mathematical adventure. In the cause of economy, I’m flying on Finnair with a six hour stop in Helsinki. At this point I should mention how grateful we all are for the generous donation from an anonymous Hong Kong businessman which means this part of the trip has been covered. It turns out to be entirely possible to slip into the town centre for a few hours, rather than stay confined in the clean but rather sterile Finnish airport. The weather is beautiful, with not a cloud in the sky as I stop for freshly grilled salmon on the harbourside then wander round the stylish waterfront shops, the two cathedrals and a sprawling park with a stunning greenhouse complex at its centre. The now scorching conditions do nothing to deter the legions of stallholders attempting to shift arctic fox stoles and reindeer fur throws. I return on the regular airport shuttle bus and head for the gate, albeit two hours early, but unbelievably there is an almost infinite supply of flat sofa-chairs, so I can settle down with Fifty Shades of Grey inconspicuously stored on my Kindle. In many ways, Finland has been an excellent, if brief, preparation for China. Firstly, the language is completely unintelligible. Secondly, I stand out like a black sheep amongst the perfect Nordic specimens, at least until the rest of the passengers turn up for my Asian flight. On the other hand, the price of everything here is absurd. Nothing plausible for lunch comes to less than 10 Euros. I’m informed that might well supply several three-course dinners in Beijing… In any case though, my stay here is short, and I’m on the evening flight East.

Sunday 5th August

I get some sleep leaning against the bulkhead, but am still disastrously tired as I yawn my way through border control at 6am Beijing time. I can’t quite face rush hour right now, so have a snooze in the arrivals lounge before making my way across town. I realise I am being royally ripped off by a taxi driver, who refuses to turn on the meter, but I fail to be demanding enough at the appropriate moment. I think he realises that I realise, and looks suitably sheepish, so I only pay a quarter and he seems happy enough. My room contains a bed, which right now is all I want. After a nap, I catch up on some of the Olympics on Chinese TV while I sort my life out. Evidently I missed the British Gold rush, but unfortunately since none of the remarkable medal haul lay in table tennis or badminton, it’s hard to find any relevant highlights. Later, I head out for a stroll through North-East Beijing. It doesn’t take too long to get used to the humidity and the traffic. I’d been apprehensive about the logistics of crossing the road, when right turns are allowed at all times, but as in Vietnam, it seems that if you just keep going at constant velocity the mopeds will swerve around you. I end up at Gui Jie, the ‘Ghost Street’, and location of hundreds of neon-lit, red-lanterned restaurants facades. Amid the imprenetable character displays, I pick one at random. My phrasebook Chinese and frantic gesticulation on both sides is enough to produce a beer and a serving of the Sichuan speciality, Gongbao chicken, with a worrying mountain of chillis and peppercorns piled in a corner. I proceed with caution.

Monday 6th August

Breakfast is a further adventure. I’ve been a massive fan of the jiaozi dumplings at Dojo in Cambridge for ages, and something similar appears here – a bit odd at 8am. Truly odd, however, are the thousand-year eggs, which are pickled raw in mud (thankfully for only two weeks or so) until the yolk turns a dark green-black and the whole thing carries an aroma of the stable. I’m sure they are an acquired taste. I have not acquired this taste yet. On the other hand, the selection of exotic fruit is excellent, and I always approve of plenty of fish in the morning.

Thus fortified, I descend into the efficient underground realm of the Beijing metro to make my way to Tiananmen Square. It is grey but enormous. Even with thousands of visitors you still feel isolated. I wander round Mao’s Mausoleum, but the queue deters me from paying my respects up close. Instead, across the small moat, and under his famous portrait which gazes down on visitors entering the South Gate of the Forbidden City. The crowd meanders through the collection of gates, hall and palaces that make up the residence of the two dynasties worth of emperors and their extensive entourages. Everywhere there is red and blue, and the copper of the elegant roofs. Some of the most interesting sights are to be found in the less grand arcades and more intimate quarters ranging around the gardens at the back of the complex. In many ways the life of the Emperor doesn’t sound all that fun. From as young as three years old, they had a daily schedule of rituals, sacrifices and administrative meetings, with only the court officials and the intriguing eunuchs who guarded the concubines for company. The best bit in a way was the view from the top of the Coal Hill Park opposite, looking down through the lingering mist (or possibly smog…) at the intricate layers that made up the fascinating enclosed city.

One of the more surprising aspects of today’s sightseeing was how few international tourists there are here. The overwhelming majority of the enthusiastic camera-pointers were Chinese. It felt nice, and a pleasant novelty after the likes of Rome and Istanbul to be with the locals even during the most stereotypical of tourist activities. Dinner tonight was much more of a success. On a terrace by the Houhai lake, a picture menu made life much easier, and I enjoyed my whole roasted duck Sichuan-style, even after the disconcerting moment where I discovered the charred remains of what had once evidently been the head, lurking under a pile of peppercorns.