Surveys in Combinatorics 2022 Anthony Nixon

Surveys in Combinatorics 2022 Anthony Nixon
Surveys in Combinatorics 2022 Anthony Nixon
Surveys in Combinatorics 2022 Anthony Nixon

1. Surveys in Combinatorics 2022 Anthony Nixon
install download
https://ebookmeta.com/product/surveys-in-
combinatorics-2022-anthony-nixon/
Download more ebook from https://ebookmeta.com

2. We believe these products will be a great fit for you. Click
the link to download now, or visit ebookmeta.com
to discover even more!
Surveys in Combinatorics 2021 Konrad K. Dabrowski
https://ebookmeta.com/product/surveys-in-
combinatorics-2021-konrad-k-dabrowski/
Surveys in Geometry I Athanase Papadopoulos
https://ebookmeta.com/product/surveys-in-geometry-i-athanase-
papadopoulos/
Surveys in Geometry I Athanase Papadopoulos Editor
https://ebookmeta.com/product/surveys-in-geometry-i-athanase-
papadopoulos-editor/
High-Performance Programming in C# and .NET: Understand
the nuts and bolts of developing robust, faster, and
resilient applications in C# 10.0 and .NET 6 1st
Edition Jason Alls
https://ebookmeta.com/product/high-performance-programming-in-c-
and-net-understand-the-nuts-and-bolts-of-developing-robust-
faster-and-resilient-applications-in-c-10-0-and-net-6-1st-
edition-jason-alls/

3. Infernal Affairs Agents of PEACE 1 1st Edition Destiny
Draco
https://ebookmeta.com/product/infernal-affairs-agents-of-
peace-1-1st-edition-destiny-draco/
The Meaning of Life and Death Ten Classic Thinkers on
the Ultimate Question 1st Edition Michael Hauskeller
https://ebookmeta.com/product/the-meaning-of-life-and-death-ten-
classic-thinkers-on-the-ultimate-question-1st-edition-michael-
hauskeller/
Mader Biology: Ap Edition (AP Biology Mader) Sylvia S.
Mader
https://ebookmeta.com/product/mader-biology-ap-edition-ap-
biology-mader-sylvia-s-mader/
Just War and Christian Traditions 1st Edition Eric
Patterson J Daryl Charles Eds
https://ebookmeta.com/product/just-war-and-christian-
traditions-1st-edition-eric-patterson-j-daryl-charles-eds/
The Cambridge Handbook of Social Theory 1st Edition
Peter Kivisto
https://ebookmeta.com/product/the-cambridge-handbook-of-social-
theory-1st-edition-peter-kivisto-2/

4. TIME LOOP Interdimensional Ebook Twinflame1111
https://ebookmeta.com/product/time-loop-interdimensional-ebook-
twinflame1111/

6. LONDON MATHEMATICAL SOCIETY LECTURE NOTE SERIES
Managing Editor: Professor Endre S¨uli, Mathematical Institute, University of Oxford, Woodstock Road, Oxford OX2
6GG, United Kingdom
The titles below are available from booksellers, or from Cambridge University Press at
www.cambridge.org/mathematics
372 Moonshine: The first quarter century and beyond, J. LEPOWSKY, J. MCKAY & M.P. TUITE (eds
373 Smoothness, regularity and complete intersection, J. MAJADAS & A. G. RODICIO
374 Geometric analysis of hyperbolic differential equations: An introduction, S. ALINHAC
375 Triangulated categories, T. HOLM, P. JØRGENSEN & R. ROUQUIER (eds
376 Permutation patterns, S. LINTON, N. RUˇSKUC & V. VATTER (eds
377 An introduction to Galois cohomology and its applications, G. BERHUY
378 Probability and mathematical genetics, N. H. BINGHAM & C. M. GOLDIE (eds)
379 Finite and algorithmic model theory, J. ESPARZA, C. MICHAUX & C. STEINHORN (eds)
380 Real and complex singularities, M. MANOEL, M.C. ROMERO FUSTER & C.T.C WALL (eds
381 Symmetries and integrability of difference equations, D. LEVI, P. OLVER, Z. THOMOVA &
P. WINTERNITZ (eds
382 Forcing with random variables and proof complexity, J. KRAJ´IˇCEK
383 Motivic integration and its interactions with model theory and non-Archimedean geometry I, R. CLUCKERS,
J. NICAISE & J. SEBAG (eds)
384 Motivic integration and its interactions with model theory and non-Archimedean geometry II, R. CLUCKERS,
J. NICAISE & J. SEBAG (eds)
385 Entropy of hidden Markov processes and connections to dynamical systems, B. MARCUS, K. PETERSEN &
T. WEISSMAN (eds
386 Independence-friendly logic, A.L. MANN, G. SANDU & M. SEVENSTER
387 Groups St Andrews 2009 in Bath I, C.M. CAMPBELLet al(eds)
388 Groups St Andrews 2009 in Bath II, C.M. CAMPBELLet al(eds)
389 Random fields on the sphere, D. MARINUCCI & G. PECCATI
390 Localization in periodic potentials, D.E. PELINOVSKY
391 Fusion systems in algebra and topology, M. ASCHBACHER, R. KESSAR & B. OLIVER
392 Surveys in combinatorics 2011, R. CHAPMAN (ed)
393 Non-abelian fundamental groups and Iwasawa theory, J. COATESet al(eds)
394 Variational problems in differential geometry, R. BIELAWSKI, K. HOUSTON & M. SPEIGHT (eds
395 How groups grow, A. MANN
396 Arithmetic differential operators over thep-adic integers, C.C. RALPH & S.R. SIMANCA
397 Hyperbolic geometry and applications in quantum chaos and cosmology, J. BOLTE & F. STEINER (eds
398 Mathematical models in contact mechanics, M. SOFONEA & A. MATEI
399 Circuit double cover of graphs, C.-Q. ZHANG
400 Dense sphere packings: a blueprint for formal proofs, T. HALES
401 A double Hall algebra approach to affine quantum Schur–Weyl theory, B. DENG, J. DU & Q. FU
402 Mathematical aspects of fluid mechanics, J.C. ROBINSON, J.L. RODRIGO & W. SADOWSKI (eds
403 Foundations of computational mathematics, Budapest 2011, F. CUCKER, T. KRICK, A. PINKUS &
A. SZANTO (eds)
404 Operator methods for boundary value problems, S. HASSI, H.S.V. DE SNOO & F.H. SZAFRANIEC (eds
405 Torsors,´etale homotopy and applications to rational points, A.N. SKOROBOGATOV (ed)
406 Appalachian set theory, J. CUMMINGS & E. SCHIMMERLING (eds)
407 The maximal subgroups of the low dimensional finite classical groups, J.N. BRAY, D.F. HOLT &
C.M. RONEY-DOUGAL
408 Complexity science: the Warwick master’s course, R. BALL, V. KOLOKOLTSOV & R.S. MACKAY (eds)
409 Surveys in combinatorics 2013, S.R. BLACKBURN, S. GERKE & M. WILDON (eds
410 Representation theory and harmonic analysis of wreath products of finite
groups, T. CECCHERINI-SILBERSTEIN, F. SCARABOTTI & F. TOLLI
411 Moduli spaces, L. BRAMBILA-PAZ, O. GARC´IA-PRADA, P. NEWSTEAD & R.P. THOMAS (eds
412 Automorphisms and equivalence relations in topological dynamics, D.B. ELLIS & R. ELLIS
413 Optimal transportation, Y. OLLIVIER, H. PAJOT & C. VILLANI (eds
414 Automorphic forms and Galois representations I, F. DIAMOND, P.L. KASSAEI & M. KIM (eds
415 Automorphic forms and Galois representations II, F. DIAMOND, P.L. KASSAEI & M. KIM (eds
416 Reversibility in dynamics and group theory, A.G. O’FARRELL & I. SHORT
417 Recent advances in algebraic geometry, C.D. HACON, M. MUSTAT¸˘A & M. POPA (eds
418 The Bloch–Kato conjecture for the Riemann zeta function, J. COATES, A. RAGHURAM, A. SAIKIA &
R. SUJATHA (eds)
419 The Cauchy problem for non-Lipschitz semi-linear parabolic partial differential equations, J.C. MEYER &
D.J. NEEDHAM
420 Arithmetic and geometry, L. DIEULEFAITet al(eds)
421 O-minimality and Diophantine geometry, G.O. JONES & A.J. WILKIE (eds
422 Groups St Andrews 2013, C.M. CAMPBELLet al(eds)

7. 423 Inequalities for graph eigenvalues, Z. STANI´C
424 Surveys in combinatorics 2015, A. CZUMAJet al(eds)
425 Geometry, topology and dynamics in negative curvature, C.S. ARAVINDA, F.T. FARRELL &
J.-F. LAFONT (eds
426 Lectures on the theory of water waves, T. BRIDGES, M. GROVES & D. NICHOLLS (eds
427 Recent advances in Hodge theory, M. KERR & G. PEARLSTEIN (eds
428 Geometry in a Fr´echet context, C.T.J. DODSON, G. GALANIS & E. VASSILIOU
429 Sheaves and functions modulop, L. TAELMAN
430 Recent progress in the theory of the Euler and Navier–Stokes equations, J.C. ROBINSON, J.L. RODRIGO,
W. SADOWSKI & A. VIDAL-L´OPEZ (eds
431 Harmonic and subharmonic function theory on the real hyperbolic ball, M. STOLL
432 Topics in graph automorphisms and reconstruction (2nd Edition), J. LAURI & R. SCAPELLATO
433 Regular and irregular holonomic D-modules, M. KASHIWARA & P. SCHAPIRA
434 Analytic semigroups and semilinear initial boundary value problems (2nd Edition), K. TAIRA
435 Graded rings and graded Grothendieck groups, R. HAZRAT
436 Groups, graphs and random walks, T. CECCHERINI-SILBERSTEIN, M. SALVATORI &
E. SAVA-HUSS (eds)
437 Dynamics and analytic number theory, D. BADZIAHIN, A. GORODNIK & N. PEYERIMHOFF (eds)
438 Random walks and heat kernels on graphs, M.T. BARLOW
439 Evolution equations, K. AMMARI & S. GERBI (eds
440 Surveys in combinatorics 2017, A. CLAESSONet al(eds)
441 Polynomials and the mod 2 Steenrod algebra I, G. WALKER & R.M.W. WOOD
442 Polynomials and the mod 2 Steenrod algebra II, G. WALKER & R.M.W. WOOD
443 Asymptotic analysis in general relativity, T. DAUD´E, D. H¨AFNER & J.-P. NICOLAS (eds)
444 Geometric and cohomological group theory, P.H. KROPHOLLER, I.J. LEARY, C. MART´INEZ-P´EREZ &
B.E.A. NUCINKIS (eds)
445 Introduction to hidden semi-Markov models, J. VAN DER HOEK & R.J. ELLIOTT
446 Advances in two-dimensional homotopy and combinatorial group theory, W. METZLER &
S. ROSEBROCK (eds)
447 New directions in locally compact groups, P.-E. CAPRACE & N. MONOD (eds
448 Synthetic differential topology, M.C. BUNGE, F. GAGO & A.M. SAN LUIS
449 Permutation groups and cartesian decompositions, C.E. PRAEGER & C. SCHNEIDER
450 Partial differential equations arising from physics and geometry, M. BEN AYEDet al(eds)
451 Topological methods in group theory, N. BROADDUS, M. DAVIS, J.-F. LAFONT & I. ORTIZ (eds
452 Partial differential equations in fluid mechanics, C.L. FEFFERMAN, J.C. ROBINSON & J.L. RODRIGO (eds)
453 Stochastic stability of differential equations in abstract spaces, K. LIU
454 Beyond hyperbolicity, M. HAGEN, R. WEBB & H. WILTON (eds
455 Groups St Andrews 2017 in Birmingham, C.M. CAMPBELLet al(eds)
456 Surveys in combinatorics 2019, A. LO, R. MYCROFT, G. PERARNAU & A. TREGLOWN (eds
457 Shimura varieties, T. HAINES & M. HARRIS (eds)
458 Integrable systems and algebraic geometry I, R. DONAGI & T. SHASKA (eds
459 Integrable systems and algebraic geometry II, R. DONAGI & T. SHASKA (eds
460 Wigner-type theorems for Hilbert Grassmannians, M. PANKOV
461 Analysis and geometry on graphs and manifolds, M. KELLER, D. LENZ & R.K. WOJCIECHOWSKI
462 Zeta andL-functions of varieties and motives, B. KAHN
463 Differential geometry in the large, O. DEARRICOTTet al(eds)
464 Lectures on orthogonal polynomials and special functions, H.S. COHL & M.E.H. ISMAIL (eds)
465 Constrained Willmore surfaces,´A.C. QUINTINO
466 Invariance of modules under automorphisms of their envelopes and covers, A.K. SRIVASTAVA,
A. TUGANBAEV & P.A.GUIL ASENSIO
467 The genesis of the Langlands program, J. MUELLER & F. SHAHIDI
468 (Co
469 Computational cryptography, J.W. BOS & M. STAM
470 Surveys in combinatorics 2021, K.K. DABROWSKIet al(eds)
471 Matrix analysis and entrywise positivity preservers, A. KHARE
472 Facets of algebraic geometry I, P. ALUFFIet al(eds)
473 Facets of algebraic geometry II, P. ALUFFIet al(eds)
474 Equivariant topology and derived algebra, S. BALCHIN, D. BARNES, M. KE¸ DZIOREK & M. SZYMIK (eds
475 Effective results and methods for Diophantine equations over finitely generated domains, J.-H. EVERTSE &
K. GY˝ORY
476 An indefinite excursion in operator theory, A. GHEONDEA
477 Elliptic regularity theory by approximation methods, E.A. PIMENTEL
478 Recent developments in algebraic geometry, H. ABBAN, G. BROWN, A. KASPRZYK & S. MORI (eds
479 Bounded cohomology and simplicial volume, C. CAMPAGNOLO, F. FOURNIER- FACIO, N. HEUER &
M. MORASCHINI (eds
480 Stacks Project Expository Collection (SPEC), P. BELMANS, W. HO & A. J. DE JONG (eds
481 Surveys in combinatorics 2022, A. NIXON & S. PRENDIVILLE (eds

8. London Mathematical Society Lecture Note Series: 481
Surveys in Combinatorics 2022
Edited by
ANTHONY NIXON
Lancaster University
SEAN PRENDIVILLE
Lancaster University

9. University Printing House, Cambridge CB2 8BS, United Kingdom
One Liberty Plaza, 20th Floor, New York, NY 10006, USA
477 Williamstown Road, Port Melbourne, VIC 3207, Australia
314–321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre,
New Delhi – 110025, India
103 Penang Road, #05–06/07, Visioncrest Commercial, Singapore 238467
Cambridge University Press is part of the University of Cambridge.
It furthers the University’s mission by disseminating knowledge in the pursuit of
education, learning, and research at the highest international levels of excellence.
www.cambridge.org
Information on this title:www.cambridge.org/9781009096225
DOI:10.1017/9781009093927
© Cambridge University Press 2022
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2022
Printed in the United Kingdom by TJ Books Limited, Padstow Cornwall
A catalogue record for this publication is available from the British Library
ISBN 978-1-009-09622-5 Paperback
Cambridge University Press has no responsibility for the persistence or accuracy of
URLs for external or third-party internet websites referred to in this publication
and does not guarantee that any content on such websites is, or will remain,
accurate or appropriate.

10. Contents
Preface pagevii
Anthony Nixon and Sean Prendiville
1 Fair Partitions 1
Noga Alon
2 Hypergraph Tur´an Problems in
2-Norm 21
J´ozsef Balogh, Felix Christian Clemen, Bernard Lidick´y
3 Circuit Imbalance Measures and Linear Programming 64
Farbod Ekbatani, Bento Natura, L´aszl´oA.V´egh
4 Intersection Problems in Extremal Combinatorics: Theorems,
Techniques and Questions Old and New 115
David Ellis
5 Finite Geometry and Extremal Graph Theory 174
Valentina Pepe
6 Rainbow Subgraphs and their Applications 191
Alexey Pokrovskiy
7 Explicit Bounds for Graph Minors 215
Paul Wollan
8 Convex and Combinatorial Tropical Geometry 237
Josephine Yu
v

12. Preface
The twenty-ninth British Combinatorial Conference takes place at Lancaster
University, from Monday 11th to Friday 15th of July 2022. The British Combinato-
rial Committee invited nine distinguished combinatorialists to give survey lectures
in areas of their expertise, and this volume contains the survey articles on which
eight of these lectures are based.
In compiling this volume, we are indebted to the authors for preparing their
articles so accurately and professionally, and to the referees for their rapid responses
and keen eye for detail. We would also like to thank Tom Harris at Cambridge
University Press. Finally, without the previous efforts of editors of earlier Surveys
and the guidance of the British Combinatorial Committee, the preparation of this
volume would have been somewhat daunting.
The twenty ninth British Combinatorial Conference is organised in partnership
with the Clay Mathematics Institute, the Heilbronn Institute for Mathematical Re-
search through the UKRI/EPSRC Additional Funding Programme for Mathematical
Sciences, the London Mathematical Society, the Institute of Combinatorics and its
Applications, the Foundation Compositio Mathematica and Lancaster University;
we thank each of these organisations for their generous involvement and support.
Anthony Nixon
Sean Prendiville
Lancaster University
January 2022
vii

14. Fair Partitions
Noga Alon
Abstract
A substantial number of results and conjectures deal with the existence of a
set of prescribed type which contains a fair share from each member of a finite
collection of objects in a space, or the existence of partitions in which this is
the case for every part. Examples include the Ham Sandwich Theorem in Mea-
sure Theory, the Hobby-Rice Theorem in Approximation Theory, the Necklace
Theorem and Ryser’s Conjecture in Discrete Mathematics. The techniques in
the study of these results combine combinatorial, topological, geometric, proba-
bilistic and algebraic tools. This paper contains a brief description of the topic,
focusing on several recent existence results and their algorithmic aspects. This
is mainly a survey paper, but it also contains several novel results.
1 Introduction
The problem of the existence of a set with desired properties that has a fair share
of each of a family of measures has been studied in several areas. The related notion
of fair partitions has also received a considerable amount of attention. Although
there have been several earlier results of this type it is common to view the Ham
Sandwich Theorem as the initial statement in the area.
Theorem 1.1 (The Ham Sandwich Theorem) For any collection ofdprobabil-
ity measures inR
d
, each absolutely continuous with respect to the Lebesgue measure,
there is a hyperplane that bisects all measures.
Thus, each of the two half spaces determined by the separating hyperplane contains a
fair share of each of the measures. This was conjectured by Steinhaus and proved by
Banach, using the Borsuk-Ulam Theorem, a fundamental result in Topology which
asserts that any continuous function fromS
n
toR
n
maps two antipodal points to
the same image.
The Ham Sandwich Theorem is first mentioned in45], where Steinhaus at-
tributes the proof to Banach (ford= 3, but the proof for generaldis essentially
identical).
There are numerous results and questions dealing with partitions of prescribed
types of Euclidean spaces and the ways they can split measures. See[40]for a
comprehensive recent survey of the subject. The formulation of most of these results
is geometric, dealing with sets or measures in Euclidean spaces. There are, however,
also purely combinatorial results and conjectures of the same flavor. Here we focus
on questions of this type. The following examples of two results and two conjectures
illustrate the diversity of the topic.
Theorem 1.2 (The Cycle and Triangles Theorem) LetGbe a cycle of length
3mand letPbe an arbitrary partition of its set of vertices into pairwise disjoint sets
P
1,P2,...,Pm,eachofsize3. Then there is an independent setSofGthat contains
exactly one vertex of each setP
i. Moreover, all vertices ofGcan be partitioned into
3independent setsS
1,S2,S3, each containing exactly one point of eachP i.
1

15. 2 Noga Alon
This result (for one setS) was conjectured by Du, Hsu and Hwang in16], the
stronger conjecture is due to Erd˝os]. It was proved (in a strong form) by Fleis-
chner and Steibitz in21], using the algebraic technique of8]. Additional proofs of
the initial conjecture of16] 42],2]and[1].
Theorem 1.3 (The Necklace Theorem) LetNbe an open necklace withka
i
beads of typei,for1≤i≤t. Then it is possible to cutNin at most(k−1)t
points and partition the resulting intervals intokcollections, each containing ex-
actlya
ibeads of typei, for all1≤i≤t.
A continuous version of this result fork= 2 has been proved in[29], the discrete
result fork= 2 is proved in[24],andashortderivationofitfromtheBorsukUlam
Theorem appears in[9]. The general result is proved in[3].
Conjecture 1.4 (Rota’s Basis Conjecture)LetB
1,B2,...,Bnbenbases of a
matroid of rankn. Then there is a partition of the elements in the (multiB
1∪
B
2∪...∪B nintonpairwise disjoint basesA 1,A2,...,Anof the matroid, where
eachA
icontains exactly one element of eachB j.
This was conjectured in[28]. It has been proved in several special cases. It is also
known that there are always at leastn/2 disjoint basesA
isatisfying the desired
property11] −o(1))npairwise disjoint independent setsA
i,
each of size (1−o(1))n, and each containing at most one element from anyA
i[35].
ALatin Square of ordernis annbynmatrix in which each row and each column
is a permutation of thensymbols [n]={1,2,...,n}.ALatin transversalin such a
square is a set ofnentries containing one element in each row, one in each column
and one copy of each symbol.
Conjecture 1.5 (Ryser’s Conjecture, [41], [13])Every Latin Square of odd or-
der contains a Latin transversal.
An equivalent formulation of this conjecture is that for every proper edge coloring of
the complete bipartite graphK
n,nbyncolors, wherenis odd, there is arainbowper-
fect matching, that is, a perfect matching in which no two edges have the same color.
It is known that there is a rainbow matching of size at leastn−O(logn/log logn),
as proved in31], improving an estimate of30]. It is also known that for every
nbesides 3 there are examples of Latin Squares of ordernthat cannot be parti-
tioned into Latin Transversals. Therefore while the existence of one fair matching
is conjectured to always hold (for oddn) the corresponding partition result here
fails. This was proved by Euler for all evenn, by Mann for alln≡1mod433],
and independently by Wanless and Webb and by Evans46],19]
cases.
In the rest of this paper we describe several recent variants and extensions of the
examples above. The next section deals with the Necklace Theorem focusing on the
investigation of random necklaces and on the algorithmic aspects of the problem. In
Section 3we consider problems dealing with subgraphs of prescribed type in edge
colored graphs that contain a fair or nearly fair share of each color. The results
inSubsection 3.2here are new. The finalSection 4contains a discussion of open
problems.

16. Fair Partitions 3
2 Necklaces
The bound (k−1)tin the Necklace Theorem (Theorem 1.3) is tight for all
admissible values of the parameters. One example demonstrating this is a necklace
in which all the beads of each type appear contiguously. In this case at leastk−1
cuts are needed somewhere in the interval of beads of typeifor everyijust in order
to ensure that each of the collections contains a positive number of beads of each
type. A possible interpretation of the Theorem is the following. Suppose thatk
mathematically oriented thieves want to distribute the necklace fairly among them.
The statement ensures that if the number of beads of each of thettypes is divisible
bykthen they can always do it by opening the necklace at the clasp and making
at most (k−1)tcuts between beads. This raises two natural questions. The first
is if the bound (k−1)tcan typically be improved. The second is the algorithmic
problem of finding the cuts and the partition intokfair collections efficiently. In
this section we briefly describe recent results about both problems.
2.1 Random Necklaces
As mentioned above the bound (k−1)tin the Necklace Theorem is tight. Is
the typical minimum number of required cuts smaller? This is studied in a recent
joint work in progress with Dor Elboim, Jan´os Pach and G´abor Tardos,6]. The
random model considered is a necklace of total lengthn=ktmconsisting of exactly
kmbeads of typeifor each 1≤i≤t, chosen uniformly among all intervals ofn
beads as above. Call a set of cuts of such a necklacefair, if it is possible to split the
resulting intervals intokcollections, each containing exactlymbeads of each type.
For a necklaceN,letX=X(N) be the minimum number of cuts in a fair collection.
WhenNis chosen randomly as above,Xis a random variable which we denote by
X(k, t, m). ByTheorem 1.3we haveX(k, t, m)≤(k−1)twith probability 1. In6]
we study the typical behavior of the random variableX=X(k, t, m). The results
are asymptotic, where at least one of the three variablesk, t, mtends to infinity.
As usual, we say that a result holdswith high probability(whp, for short), if the
probability that it holds tends to 1 when the relevant parameter(s
The problem of determining the asymptotic behavior ofX(k, t, m) turns out to
be connected to several seemingly unrelated topics, including matchings in nearly
regular hypergraphs with small codegrees and random walks in Euclidean spaces.
The first observation in[6]is the following.
Proposition 2.1For every fixedkandt,asmtends to infinity,X=X(k, t, m)≥
ffi
(k−1)(t+1)
2
Θ
whp.
The proof is a simple first moment argument, whose details are omitted.
The main result describes the asymptotic behavior ofX=X(k, t, m) for two
thieves (k= 2) and any fixed number of typest,asmtends to infinity.
Theorem 2.2Lettbe a fixed positive integer andm→∞.
1. For all1≤s<
t+1
2
,
P
Ω
X(2,t,m)=s
ff
=Θ
Ω
m
s−
t+1
2
ff
. (2.1)

17. 4 Noga Alon
2. Whentis odd ands=
t+1
2
,
P
Ω
X(2,t,m)=s
ff
=Θ
→
1
logm
∞
. (2.2)
3. For all
t+1
2
<s≤t,
P
Ω
X(2,t,m)=s
ff
=Θ(1). (2.3)
Two additional results deal with the casem= 1, in which every thief should get
a single bead of each type.
Theorem 2.3Fortandk/logttending to infinity, the random variableX=
X(k, t,1)iso(kt)whp.
Theorem 2.4The random variableX=X(2,t,1)is at least2H
−1
(1/2)t−o(t)=
0.220...t−o(t)whp, whereH
−1
(x)is the inverse of the binary entropy function
H(x)=−xlog
2x−(1−x)log
2(1−x)taking values in the interval[0,1/2].
On the other hand,X≤0.4t+o(t)holds whp.
The upper bound above was obtained jointly with Alweiss, Defant and Kravitz, c.f.
[6].
The proof ofTheorem 2.2applies the first and second moment and is rather
lengthy and technical. A brief outline of the argument for the special caset=3
follows. Fort= 3 the probability that for the random necklaceN,X(N)=1is
easily seen to be Θ(1/m). ByTheorem 1.3for everyN,wehaveX(N)≤3. Thus,
it remains to show that the probability thatX(N)≤2isΘ(1/logm). In order to
estimate this probability, note that two cuts suffice if and only if there is a balanced
partition ofNinto two cyclic intervals that is fair. There are exactly 3mbalanced
partitions into two cyclic intervals. For 0≤i<3m,wedenotebyP
ithe balanced
partition into an interval starting at positioni+ 1 and ending at positioni+3m,
and its complement.
LetY=Y(N) denote the random variable counting the number of fair partitions
into cyclic intervals. Clearly,X(N)≤2 if and only ifYis positive. This probability
is lower bounded by the second moment method. It is not too difficult to check that
the expectation ofYis Θ(1 Y
2
is Θ(logm). Therefore, by
the Paley-Zygmund Inequality38],39] Yis positive is at least
Ω(1/logm).
The proof of the upper bound for the probability thatYis positive is more
interesting. It is done by defining another random variableZ=Z(N). It is then
shown thatZis positive with probabilityO(1/logm), and that the probability
thatYis positive butZis not, is even lower. The crucial step in bounding the
probability thatZis positive, is the analysis of the probability that an appropriate
two-dimensional random walk does not return to the origin in a certain number of
steps. For this one can apply a slightly modified version of a classical argument of
Dvoretzky and Erd˝os]. The details will appear in6].
The proof ofTheorem 2.3applies a hypergraph edge-coloring result of Pippenger
and Spencer[36]. This result asserts that the edges of any hypergraph of constant
uniformity and large maximum degreekin which every pair of vertices lie in at most

18. Fair Partitions 5
o(k) common edges, can be partitioned into (1 +o(1))kmatchings. By cutting the
necklace into intervals of large constant size it is possible to define an appropriate
hypergraph and show that whp it satisfies the conditions of the theorem of36],
which provides the required result.
2.2 The Algorithmic Aspects
The proof ofTheorem 1.3is topological. It starts by converting the problem into
a continuous one dealing with interval coloring. LetI=[0,1] be the unit interval.
Anintervalt-coloringis a coloring of the points ofIbytcolors, such that for each
i,1≤i≤t, the set of points colorediis (Lebesgue) measurable. Given such a
coloring, ak-splitting of sizeris a sequence of numbers 0 =y
0≤y1≤...≤y r≤
y
r+1= 1 and a partition of the family ofr+ 1 intervalsF={[y i,yi+1):0≤i≤r}
intokpairwise disjoint subfamiliesF
1,...,Fkwhose union isF, such that for each
1≤j≤kthe union of the intervals inF
jcaptures precisely 1/kof the total measure
of each of thetcolors. The continuous version of the theorem is then the following.
Theorem 2.5Every intervalt-coloring has ak-splitting of size(k−1)·t.
It is not difficult to show that this implies the Necklace Theorem. Indeed, the
necklace can be converted to an interval coloring by replacing each bead by a small
interval of the corresponding color. If the splitting ensured by the last theorem
contains cuts that lie inside intervals corresponding to beads, it can be shown that
these can be shifted to produce a splitting of the discrete necklace. The proof of
Theorem 2.5proceeds by first showing, by a simple combinatorial argument, that
its validity for (t, k
1)andfor(t, k 2) implies its validity for (t, k 1k2). The main step
is a proof that the assertion of the theorem holds for any primek. This is done
by applying a fixed point theorem of B´ar´any, Shlosman and Sz¨ucs14], which can
be viewed as an extension of the Borsuk-Ulam Theorem. Indeed, the casek=2
ofTheorem 2.5admits a short proof using the Borsuk-Ulam Theorem, as shown in
[9]. It can also be derived quickly from the Ham Sandwich Theorem, applying it to
the measures obtained by placing the interval along the moments curve inR
t
.The
assertion of the theorem actually holds for general continuous probability measures,
and not only for ones corresponding to interval colorings. Indeed, fork=2this
extension is the Hobby-Rice Theorem29], and the general case is proved in3]. It is
worth noting that a classical result of Liapounoff32]
oftcontinuous probability measuresμ
ion [0,1] and any 0≤α≤1 there is a subset
Aof [0,1] withμ
imeasureαfor each 1≤i≤t. The assertion ofTheorem 2.5for
general continuous measures shows that forα=1/kthe interval can be partitioned
intoksuch setsA
i, each being a union of a relatively small number of intervals.
The topological proof of the main step in the derivation ofTheorem 1.3is non-
constructive, and does not supply any efficient algorithm for finding the required
(k−1)tcuts that provide a fair partition for a given input necklace. Fork=2this
algorithmic problem, raised in4], is calledthe Necklace Halving Problem. A recent
result of Filos-Ratsikad and Goldberg[20]shows that this is a hard problem.
PPA and PPAD are two complexity classes introduced by Papadimitriou,[34].
Although this is not our focus here, we include a very brief paragraph about the
relevance of these classes to some of the problems discussed here. Both PPA and

19. 6 Noga Alon
PPAD are contained in the class TFNP, which is the complexity class of total search
problems, consisting of all problems in NP where a solution exists for every instance.
A problem is PPA complete if and only if it is polynomially equivalent to the canon
ical problem LEAF, described in34]. Similarly, a problem is PPAD-complete if
and only if it is polynomially equivalent to the problem END-OF-THE-LINE. A
problem is PPA-hard or PPAD-hard if the respective canonical problem is polyno-
mially reducible to it. A number of important problems, such as several versions of
Nash Equilibrium, have been proved to be PPAD-complete. It is known that PPAD
⊆PPA. Hence, PPA hardness implies PPAD-hardness, and if a PPA hard problem
admits an efficient algorithm, so do all problems in PPA (and hence also in PPAD).
Filos-Ratsikas and Goldberg20]
is the problem of finding a collection oftcuts that provide a fair partition of a given
input necklace with beads ofttypes and an even number of beads of each type,
is PPA hard20]. This suggests the problem of finding an efficient algorithm for
obtaining a fair partition using a somewhat larger number of cuts. An early result
in this direction appears in12], but it only provides a partition in which the number
of beads of each type in the two collections are close to each other, and the number
of cuts is exponential in the number of types. A recent improved algorithm is given
in7]. Its performance is described in the next result.
Theorem 2.6There is a polynomial time algorithm that given an input necklace
with beads ofttypes, in which the number of beads of each type is an even number
that does not exceedm, produces a collection of at mostt(logm+O(1))cuts and a
partition of the resulting intervals into two collections, each containing exactly half
of the beads of each type.
The algorithm proceeds by first converting the problem to the continuous interval
coloring problem described above. The continuous problem is tackled using a linear
algebra procedure based on Carath´eodory’s Theorem for cones. Its solution can then
be rounded to produce a solution of the discrete problem. The details are sketched
below.
Proof ofTheorem 2.6(sketch):
Given a necklace withm
ibeads of colorifor 1≤i≤t,wherem=maxm i,
replace each bead of coloriby an interval ofμ
i /m iandμ j
allj =i. These intervals are placed next to each other according to the order in the
necklace, and their lengths are chosen so that altogether they cover [0,1]. We first
describe a procedure that splits the interval into two collections so that for every
ithe difference between theμ
i-measures of the two collections is at mostε,where
ε=
1
2m
. The number of cuts used here is at mostt(logm+O(1
too difficult to round the cuts and get a solution of the discrete problem without
increasing the number of cuts.
Letμ
ibe thetmeasures defined above. Our objective is to describe an efficient
algorithm that cuts the interval in at mostt(2 +log
2
1
ε
) places and splits the
resulting intervals into two collectionsC
0,C1so thatμ i(Cj)∈[
1
2
−
ε
2
,
1
2
+
ε
2
] for all
i∈[t]={1,2,...,t},0≤j≤1.
For each intervalI⊂[0,1] denoteμ(I)=μ
1(I)+...+μ t(I). Thusμ([0,1]) =t.
Using 2t−1 cuts split [0,1] into 2tintervalsI
1,I2,...,I2tso thatμ(I r)=1/2 for all

20. Fair Partitions 7
r. Note that it is easy to find these cuts efficiently, since each measureμ
iis uniform
on its support. For each intervalI
rletvrdenote thet-dimensional vector
(μ
1(Ir),μ2(Ir),...,μt(Ir)).
By a simple linear algebra argument, which is a standard fact about the prop-
erties of basic solutions for Linear Programming problems, one can write the vector
(1/2,1/2,...,1/2) as a linear combination of the vectorsv
rwith coefficients in [0,1],
where at mosttof them are not in{0,1}. This follows from Carath´edory’s Theorem
for cones. Here is the simple proof, which also shows that one can find coefficients
as above efficiently. Start with all coefficients being 1/2. Call a coefficient which is
not in{0,1}floatingand one in{0,1}fixed. Thus at the beginning all 2tcoefficients
are floating. As long as there are more thantfloating coefficients, find a nontrivial
linear dependence among the corresponding vectors and subtract a scalar multiple
of it which keeps all floating coefficients in the closed interval [0,1] shifting at least
one of them to the boundary{0,1}, thus fixing it.
This process clearly ends with at mosttfloating coefficients. The intervals with
fixed coefficients with value 1 are now assigned to the collectionC
1and those with
coefficient 0 toC
0. The rest of the intervals remain. Split each of the remaining
intervals into two intervals, each withμ-value 1/4. We get a collectionJ
1,J2,...,Jm
ofm≤2tintervals, each of them has the coefficient it inherits from its original
interval. Each such interval defines at
with the corresponding coefficients (in (0,1)) is exactly what the collectionC
1should
still get to have its total vector of measures being (1/2,...,1/2).
As before, we can shift the coefficients until at mosttof them are floating,
assign the intervals with{0,1}coefficients to the collectionsC
0,C1and keep at
mosttintervals with floating coefficients. Split each of those into two intervals
ofμ /8 each and proceed as before, until we get at mosttintervals with
floating coefficients, where theμ-value of each of them is at mostε/2. This happens
after at mostlog
2(1/ε)rounds. In the first one, we have made 2t−1 cuts and
in each additional round at mosttcuts. Thus the total number of cuts is at most
t(2 +log
2(1/ε))−1.
From now on we do not increase the number of cuts, and show how to shift
them and allocate the remaining intervals toC
0,C1.LetIdenote the collection of
intervals with floating coefficients. Then|I| ≤tandμ(I)≤ε/2foreachI∈I.
This means that
t
⊆
i=1
⊆
I∈I
μi(I)≤tε/2.
It follows that there is at least one measureμ
iso that
⊆
I∈I
μi(I)≤ε/2.
Observe that for any assignment of the intervalsI∈Ito the two collections
C
0,C1, the totalμ i C 1(and hence also ofC 0) lies in [1/2−ε/2,1/2+ε/2],
as this measure with the floating coefficients is exactly 1/2 and any allocation of the
intervals with the floating coefficients changes this value by at mostε/2. We can thus

21. 8 Noga Alon
ignore this measure, for ease of notation assume it is measure numbert, and replace
each measure vector of the members inIby a vector of lengtht−1 corresponding to
the othert−1 measures. If|I|>t−1 (that is, if|I|=t), then it is possible to shift
the floating coefficients as before until at least one of them reaches the boundary, fix
it assigning its interval toC
1orC0as needed, and omit the corresponding interval
fromIensuring its size is at mostt−1. This means that for the modifiedIthe
sum
t−1
⊆
i=1
⊆
I∈I
μi(I)≤(t−1)ε/2.
Hence there is again a measureμ
i,1≤i≤t−1sothat
⊆
I∈I
μi(I)≤ε/2.
Again, we may assume thati=t−1, observe that measure numbert−1 will stay
in its desired range for any future allocation of the remaining intervals, and replace
the measure vectors by ones of lengtht−2. This process ends with an allocation of
all intervals toC
1andC 0, ensuring that at the endμ i(Cj)∈[1/2−ε/2,1/2+ε/2]
for all 1≤i≤t,0≤j≤1. These are the desired collections. It is clear that
the procedure for generating them is efficient, requiring only basic linear algebra
operations.
This completes the (sketch of the) proof. The full details can be found in7].∈
3 Graphs
3.1 Fair Representation
Theorem 1.2andConjecture 1.5mentioned in Section 1 are two examples of
fair representation problems dealing with graphs. There are quite a few additional
results and conjectures of this type. We start this section by discussing several
examples.
Anoptimal proper edge coloringof the complete graphK
2non an even number of
vertices is a coloring of the edges by 2n−1 colors, each forming a perfect matching.
Given such an edge coloring, the fair share of a spanning tree in each color class
is exactly 1. Brualdi and Hollingsworth10]
coloring ofK=K
2nwheren>4 one can partition all edges ofKintonpairwise edge
disjointrainbowspanning trees, that is, each tree containing exactly one edge of each
color. Constantinos15]
in which all trees are isomorphic. This is proved for all sufficiently largenin a recent
paper of Glock, K¨uhn, Montgomery and Osthus23]. The proof is probabilistic, and
is based on hypergraph matching results and the so-called absorption technique.
This technique starts by removing an appropriate small part of the graph, finding
an approximate partition of the rest, and then using the small part to complete it
to a precise partition. The details, which require quite some work, can be found in
[23]. Similar ideas are useful in the study of several related problems, as described
in[23]and its references.

22. Fair Partitions 9
The Cycle and Triangles Theorem (Theorem 1.2) has been proved in21]using
the algebraic approach of[8]. This approach enables one to bound the chromatic
number of a graph, and in fact even its so-called list chromatic number, by showing
that a certain coefficient of an appropriate polynomial is nonzero. Subsequent proofs
of the theorem (at least of the statement about the existence of a single independent
set of the required form) apply topological ideas. The shortest proof is the one in
[1]where the result is derived from Schrijver’s Theorem on vertex critical subgraphs
of the Kneser graph. This Theorem, which strengthens the result of Lov´asz about
the chromatic number of the Kneser graph, is proved in[43]using the Borsuk Ulam
Theorem.
Theorem 3.1 (Schrijver[43])Forn>2kthe family of independent sets of sizek
in the cycleC
ncannot be partitioned into fewer thann−2k+2intersecting families.
Now letGbe a cycle of length 3mand letPbe a partition of its set of vertices
into pairwise disjoint setsP
1,P2,...,Pm, each of size 3. Assuming the first assertion
ofTheorem 1.2fails, there is no independent set ofGthat contains exactly one vertex
of each setP
i. In this case each independent set of sizemin the cycleGcontains at
least two vertices in some setP
i, and we can partition all these independent sets into
mfamilies, where a setSbelongs to family numberiiffiis the smallest index so that
|S∩P
i|≥2. Note that each such family is intersecting, as each member of it contains
at least two vertices among the three vertices ofP
i. But sincem<3m−2m+2
this contradictsTheorem 3.1withn=3mandk=m, proving the existence of an
independent set containing one vertex in eachP
i.
The short proof above can be extended in several ways. In particular the follow-
ing holds.
Proposition 3.2 ([1])IfV=V
1∪V2∪···∪V mis a partition of the vertex set of
acycleCintompairwise disjoint sets, and|V
i|is odd for alli, then for any vertex
vofCthere is an independent setSofCso thatv ∈Sand|S∩V
i|=(|V i|−1)/2
for alli.
In an attempt to strengthen Ryser’s Conjectures (Conjecture 1.5), Stein44]sug-
gested the stronger conjecture that for any partitionPof the edges of the complete
bipartite graphK
n,nintonpairwise disjoint color classes, each containing exactly
nedges, there exists a rainbow matching of sizen−1. This turned out to be too
strong. A counterexample was found by Pokrovskiy and Sudakov in[37], where the
authors describe a coloring as above so that every matching misses at least Ω(logn)
color classes. This shows that in some natural cases tight fair representations fail
and suggests relaxed versions of questions of this type, as discussed in the following
subsection.
3.2 Nearly Fair Representation
A special case of the approach described here was initiated in discussions with
Eli Berger and Paul Seymour. LetG=(V, E) be a graph and letPbe an arbitrary
partition of its set of edges intompairwise disjoint subsetsE
1,E2,...,Em.Thesets
E
iare called the color classes of the partition. For any subgraphH
ε
=(V
ε
,E
ε
)ofG,
letx(H
ε
,P) denote the vector (x 1,x2,...,xm), wherex i=|E i∩E
ε
|is the number

23. 10 Noga Alon
of edges ofH
Θ
that lie inE i. Thus, in particular,x(G, P)=(|E 1|,...,|E m|).In
a completely fair representation of the setsE
iinH
Θ
,eachentryx iof the vector
x(H
Θ
,P) should be equal to|E i|·
|E
ε
|
|E|
. Of course such equality can hold only if all
these numbers are integers. But even when this is not the case the equality may
hold up to a small additive error.
We are interested in results and conjectures asserting that whenGis either the
complete graphK
nor the complete bipartite graphK n,n, then for certain graphsH
and for any partitionPofE(G) into color classesE
1,...,Em, there is a subgraph
H
Θ
ofGwhich is isomorphic toHso that the vectorx(H
Θ
,P) is close (or equal)
to the vectorx(G, P)
|E(H
ε
)|
|E(G)|
. As mentioned in the previous subsection, Stein[44]
conjectured that ifG=K
n,nandPis any partition of the edges ofGintonsets,
each of sizen, then there is always a rainbow matching of sizen−1inG. However,
this turned out to be false as shown by a clever counter-example of Pokrovskiy and
Sudakov37].
In1] G=K
n,n,Pis arbitrary, andHis a matching
of sizen, then there is always a copyH
Θ
ofH(that is, a perfect matchingH
Θ
inG),
so that
x(H
Θ
,P)−
1
n
x(G, P)
∞<2.
This is proved in1] Pwith 2 or 3 color
classes. Here we first prove the following, showing that when allowing a somewhat
larger additive error (which grows with the number of colorsmbut is independent
ofn) a similar result holds for partitions with any fixed number of classes.
Theorem 3.3For any partitionPof the edges of the complete bipartite graphK
n,n
intomcolor classes, there is a perfect matchingMso that
x(M, P)−
1
n
x(K
n,n,P) ∞≤x(M, P)−
1
n
x(K
n,n,P) 2<(m−1)2
(3m−2)/2
.
It is worth noting that a random perfect matchingMtypically satisfies
x(M, P)−
1
n
x(K
n,n,P) ∞≤Om(
√
n).
The main challenge addressed in the theorem is to get an upper bound independent
ofn.
Theorem 3.3is a special case of a general result which we describe next, starting
with the following definition.
Definition 3.4LetGbe a graph and letHbe a subgraph of it. Call a family of
graphsH(which may have repeated members) auniform cover of widthsof the
pair(G, H) if the following four conditions hold.
•Every memberH
Θ
ofHis a subgraph ofGwhich is isomorphic toH.
•The number of edges of each suchH
Θ
which are not edges ofHis at mosts.
•Every edge ofHbelongs to the same number of members ofH.

24. Fair Partitions 11
•Every edge inE(G)−E(H) belongs to the same positive number of members
ofH.
An example of a uniform cover of widths=2forG=K
n,nandHa perfect
matching in it is the following. Let thenedges ofHbea
ibiwhere{a 1,a2,...,an}
and{b
1,b2,...,bn}are the vertex classes ofG.LetHbe the family of all perfect
matchings ofGobtained fromHby omitting a pair of edgesa
ibianda jbjand by
adding the edgesa
ibjanda jbi. The width is 2, every edge ofHbelongs to exactly
Ω
n
2
ff
−(n−1) members ofH, and every edge inE(G)−E(H) belongs to exactly 1
member ofH.
Theorem 3.5LetGbe a graph withgedges, letFbe a subgraph of it withfedges,
and suppose there is a uniform cover of widthsof the pair(G, F). Then for any
partitionPof the edges ofGintomsubsets, there is a copyHofFinGso that
x(H, P)−
f
g
x(G, P)
∞≤x(H, P)−
f
g
x(G, P)
2≤(m−1)2
(m−2)/2
s
m
.
Theorem 3.3is a simple consequence ofTheorem 3.5.A similar simple conse-
quence is the following.
Proposition 3.6For any partitionPof the edges of the complete graphK
ninto
mcolor classes, there is a Hamilton cycleCso that
x(C, P)−
2
n−1
x(K
n,P) ∞≤x(C, P)−
2
n−1
x(K
n,P) 2<(m−1)2
(3m−2)/2
.
Similar statements follow, by the same reasoning, for a Hamilton cycle in a complete
bipartite graph, or for a perfect matching in a complete graph on an even number
of vertices. We proceed to describe two more general applications.
For a fixed graphTwhose number of verticestdividesn,aT inK
nis
the graph consisting ofn/tpairwise vertex disjoint copies ofT. In particular, when
T=K
2this is a perfect matching.
Theorem 3.7For any fixed graphTwithtvertices andqedges and anymthere
is a constantc=c(t, q, m)≤(m−1)2
(m2)/2
(qt)
m
so that for anyndivisible byt
and for any partitionPof the edges of the complete graphK
nintomsubsets, there
is aT-factorHso that
x(H, P)−
2q
(n−1)t
x(K
n,P) ∞≤x(H, P)−
2q
(n−1)t
x(K
n,P) 2≤c.
Another application, proved together with Sacheth Sathyanarayanan, is the fol-
lowing.
Theorem 3.8For any fixeddandmthere is a constantc=c(d, m)so that for any
d-regular graph onnverticesHand for any partitionPof the edges of the complete
graphK
nintomsubsets, there is a copy ofHso that
x(H, P)−
d
n−1
x(K
n,P) ∞≤x(H, P)−
d
n−1
x(K
n,P) 2≤c.

25. 12 Noga Alon
Note thatProposition 3.6is a special case of the result above (with a specific value
ofc(2,m)).
We proceed with the proofs of the results above, starting with the proof of
Theorem 3.5.
Proof ofTheorem 3.5:LetPbe a partition of the edges ofGintomcolor classes
E
i.Put
y=(y
1,y2,...,ym)=
f
g
x(G, P).
LetHbe a copy ofFinGfor which the quantityy−x
2
2
=

m
j=1
(yi−xi)
2
is
minimum wherex=(x
1,x2,...,xm)=x(H, P). LetHbe a uniform cover of width
sof the pair (G, H). Suppose each edge ofHbelongs toamembers ofHand each
edge inE(G)−E(H) belongs tob>0 such members. For each memberH
∪
ofH,let
v
H
εdenote the vector of lengthmdefined as follows. For each 1≤i≤m, coordinate
numberiofv
H
εis the number of edges inE(H
∪
)−E(H) colorediminus the number
of edges inE(H)−E(H
∪
) coloredi. Note that the≡ 1-norm of this vector is at most
2sand its sum of coordinates is 0. Therefore, its≡
2-norm is at most
√
2s
2
. Note
also thatx(H
∪
,P)=x(H, P)+v H
ε.
We claim that the sumSof all|H|-vectorsv
H
εforH
∪
∈His a positive multiple
of the vector (y−x). Indeed, each edge inE(G)−E(H) is covered bybmembers of
H, and each edge ofE(H) is covered byamembers ofH.InthesumSabove this
contributes to the coordinate corresponding to color numberi,btimes the number
of edges of coloriinE(G)−E(H)minus(|H|−a) times the number of edges of color
iinH. Equivalently, this isbtimes the number of all edges ofGcolorediminus
(|H|+b−a) times the number of edges ofHcoloredi. Since the sum of coordinates
of each of the vectorsv
H
εis zero, so is the sum of coordinates ofS, implying that
bg=(|H|+b−a)f,thatis,|H|+b−a=
g
f
b.Since
g
f
y=x(G, P)thisimpliesthat
S=
bg
f
(y−x), proving the claim.
Since the vectory−xis a linear combination with positive coefficients of the
vectorsv
H
εit follows, by Carath´eodory’s Theorem for cones, that there exists a set
Lof linearly independent vectorsv
H
εso thaty−xis a linear combination with
positive coefficients of them. Indeed, starting with the original expression ofy−x
mentioned above, as long as there is a linear dependence among the vectorsv
H
ε
participating in the combination with nonzero (hence positive) coefficients, we can
subtract an appropriate multiple of this dependence and ensure that at least one
of the nonzero coefficients vanishes and all others stay non negative (positive, after
omitting all the ones with coefficient 0). As each vectorv
H
εhasmcoordinates and
their sum is 0, it follows that|L|≤m−1.
We can now solve the system of linear equationsy−x=

z
H
εvH
εwith the
variablesz
H
εforv H
ε∈L. Note that it is enough to consider any|L|≤m−1
coordinates ofy−xand solve the system corresponding to these coordinates. By
Cramer’s rule applied to this system eachz
H
εis a ratio of two determinants. The
denominator is a determinant of a nonsingular matrix with integer coefficients, and
its absolute value is thus at least 1. The numerator is also a determinant, and by
Hadamard’s Inequality its absolute value is at most the product of the≡
2
of the columns of the corresponding matrix. The norm of one column is at most
y−x
2(this can be slightly improved by selecting the|L|-coordinates with the

26. Fair Partitions 13
smallest≡
2
column has norm at most (2s
2
)
1/2
. Therefore each coefficientz H
≤satisfies 0≤z H
≤≤
y−x
2(2s
2
)
(m−2)/2
.By taking the inner product withy−xwe get
y−x
2
2
=
⊆
v
H
≤
∈L
zH
≤.y−x, v H
≤/
≤
⊆
v
H
≤
∈L,≥y−x,v
H
≤
→>0
zH
≤.y−x, v H
≤/
≤(m−1)y−x
2(2s
2
)
(m−2)/2
max.y−x, v H
≤/.
Therefore, there is av
H
≤so that
y−x
2
(m−1)(2s
2
)
(m−2)/2
=
y−x
2
2
(m−1)(2s
2
)
(m−2)/2
y−x 2
≤y−x, v H
≤/,
that is,
y−x
2≤(m−1)(2s
2
)
(m−2)/2
.y−x, vH
≤/=(m−1)2
(m−2)/2
s
m−2
.y−x, vH
≤/.(3.1)
By the minimality ofy−x
2
2
x+v H
≤−y
2
2
=x−y
2
2
−2.y−x, v H
≤/+v H
≤
2
2
≥x−y
2
2
,
implying that
2s
2
≥v H
≤
2
2
≥2.y−x, v H
≤/.
Plugging in (3.1)weget
y−x
2≤(m−1)2
(m−2)/2
s
m
,
and the desired results follows sincey−x
∞≤y−x 2. ≤
The assertions ofTheorem 3.3andProposition 3.6follow easily fromTheo-
rem3.5.Indeed, as described above there is a simple uniform cover of widths=2
for the pair (K
n,n,M)whereMis a perfect matching. There is also a similar uni
form coverHof widths= 2 for the pair (K
n,C)whereCis a Hamilton cycle. The
n(n−3)/2membersofHare all Hamilton cycles obtained fromCby omitting two
nonadjacent edges of it and by adding the two edges that connect the resulting pair
of paths to a cycle.
To proveTheorem 3.7we need the following simple lemma.
Lemma 3.9LetTbe a fixed graph withtvertices andqedges, supposetdividesn
and letHbe aT-factor inK
n. Then there is a uniform cover of width at mostqt
of the pair(K
n,H).
ProofLetHbe a fixedT-factor inK
n, it consists ofp=n/t(not necessarily
connected) vertex disjoint copies ofTwhich we denote byT
1,T2,...,Tp.LetH 1be
the set of all copiesH
∪
of theT Hby replacing one the copies
T
iby another copy ofTon the same set of vertices, in allt! possible ways. Note
that ifThas a nontrivial automorphism group some members ofH
1are identical,

27. 14 Noga Alon
andH
1is a multiset. By symmetry it is clear that each edge ofHbelongs to the
same number of members ofH
1. Similarly, each edge connecting two vertices of the
sameT
iwhich does not belong toHlies in the same positive number of members of
H
1. Beside these two types of edges, no other edge ofK nis covered by any member
ofH
1.LetH 2be the (multi)-set of all copies of theT-factor obtained fromHby
choosing, in all possible ways,tof the copies ofT,say,T
i1
,Ti2
,...,Tit, removing
them, and replacing them by all possible placements oftvertex disjoint copies ofT
where each of the newly placed copies contains exactly one vertex of eachT
ij
. Again
by symmetry it is clear that each edge ofHbelongs to the same number of members
ofH
2. In addition, each edge ofK nconnecting vertices from distinct copies ofTin
Hbelongs to the same (positive) number of members ofH
2. No other edges ofK n
are covered by anyH
Θ
∈H2. It is now simple to see that there are two integersa,
b, so that the multisetHconsisting ofacopies of each member ofH
1andbcopies
of each member ofH
2is a uniform cover of the pair (K n,H). The width of this
cover is clearlyqt,aseverymemberofH
2containsqtedges not inE(H), and every
member ofH
1contains at mostqedges not inE(H). This completes the proof.
ffi
The assertion ofTheorem 3.7clearly follows from the last lemma together with
Theorem 3.5.
Proof ofTheorem 3.8:ByTheorem 3.5it suffices to show that there is a uniform
cover of bounded width of the pair (K
n,H). Fix a copyH
Θ
ofHinK nand letHbe
the (multi)-set of all
Ω
n
2
ff
graphsH
u,vobtained fromH
Θ
by swapping a pair of vertices
u, v. Specifically, for every pair of distinct verticesu, vofH
Θ
,letH u,vbe the graph
obtained fromH
Θ
by removing all edges incident withuor withv, and by adding all
edges connectingvtoaneighborofuand all edges connectinguto a neighbor ofv.
It is clear that each graphH
u,vis isomorphic toH
Θ
(by the isomorphism swapping
uandv). It is also clear that eachH
u,vcontains at most 2dedges that do not lie
inH
Θ
. Therefore the width of the collection is at most 2d. It remains to check that
this is a uniform cover.
Letxybe an edge ofH
Θ
. This edge belongs toH uviff either{u, v}∩{x, y}=∅,
or one of the members of{u, v}isxand the other is a neighbor ofy(oryitself),
or, symmetrically, if one of the members of{u, v}isyand the other is a neighbor
ofx. Altogether there are
Ω
n−2
2
ff
+2d−1 such (unordered {u, v}. Thisisthe
same number for every edgexy, as needed for a uniform cover. Now letxybe a
non-edge ofH
Θ
. Then it belongs toH u,viff either one of the members of{u, v}isx
and the other is a neighbor ofyor one of the members of{u, v}isyand the other is
a neighbor ofx. There are exactly 2dsuch pairsH
u,v, independently of the specific
choice of the non edgexy. This shows thatHis indeed a uniform cover of (K
n,H),
completing the proof. ffi
Remark
A similar argument shows that for everyd-regular spanning subgraphHof the
complete bipartite graphK
n,nthere is a uniform cover of width at most 2dof the
pair (K
n,n,H). Indeed, here the family of all
Ω
n
2
ff
copies ofHobtained from a fixed
one by swapping every pair of vertices in one of the two color classes is such a uniform
cover. This andTheorem 3.5implies a result about nearly fair representations of

28. Fair Partitions 15
any regular spanning subgraph ofK
n,n.Theorem 3.3is a special case.
Additional Remarks
•The statement ofTheorem 3.7holds for any graphHconsisting ofn/t(not
necessarily connected) vertex disjoint components, each havingtvertices and
qedges. The proof applies with no need to assume that all these components
are isomorphic.
•The proof ofTheorem 3.5is algorithmic in the sense that if the coverHis
given then one can find, in time polynomial innand|H|,acopyHofF
satisfying the conclusion. Indeed, the proof implies that as long as we have a
copyHfor which the conclusion does not hold, there is a memberH
Θ
∈Hfor
whichx(H
Θ
,P)−
f
g
x(G, P)
2
2
is strictly smaller thanx(H, P)−
fg
x(G, P)
2
2
.
By checking all members ofHwe can find anH
Θ
for which this holds. As
both these quantities are non negative rational numbers smaller thann
4
with
denominatorg
2
<n
4
, this process terminates in a polynomial number of steps.
We make no attempt to optimize the number of steps here.
•Theorem 3.5can be extended tor-uniform hypergraphs by a straightforward
modification of the proof.
•There are graphsHfor which no result like those proved above holds when
Gis either a complete or a complete bipartite graph even if the number of
colors is small. A simple example is whenG=K
2n,H=K 1,2n−1 andm=3.
The edges ofK
2ncan be partitioned into two vertex disjoint copies ofK n
and a complete bipartite graphK n,n. For this partition, every copy of the
starHmisses completely one of the color classes, although its fair share in
it is roughly a quarter of its edges. More generally, letHbe any graph with
a vertex cover of size smaller thanm−1 (that is,Hcontains a set of less
thanm−1 vertices touching all its edges). Consider a partition of the edges
of the complete graphK
nintom−1 pairwise vertex disjoint copies of the
complete graph on1n/(m−1)2vertices, and an additional class containing
all the remaining edges. Then any copy ofHin this graph cannot contain
edges of all thosem−1 complete subgraphs, as the edges of the copy can be
covered by less thanm−1 stars. It is easy to see that similar examples exist
forG=K
n,nas well.
4 Open Problems
Several open problems and conjectures dealing with the topic of this article are
mentioned in the previous sections. In this final section we discuss several additional
intriguing problems.
•Recall that the random variableX(k, t, m) is the minimum number of cuts in
a fair partition of a random necklace withkmbeads of each ofttypes into
kparts.Theorem 2.2determines the asymptotic behavior of this variable for
k= 2 and fixedt,asmtends to infinity. It will be interesting to study the
behavior of this random variable for all admissible values of the parameters.

29. 16 Noga Alon
•Theorem 2.4provides upper and lower bounds for the ratioX(2,t,1)/t,im-
plying that the liminf of this quantity is at least roughly 0.22 and the limsup
is at most 0.4. Both these bounds can be slightly improved, as shown in6],
but there is still a large gap between the upper and lower bounds. While the
problem of closing this gap appears to be difficult, it is not even known if the
limit of this ratio asttends to infinity exists. Naturally, we believe it does
exist, but have not been able to prove it.
•The algorithmic aspects of the Necklace Theorem (Theorem 1.3) are discussed
inSubsection 2.2.
described here are also interesting. In particular, the algorithmic question cor
responding to the Cycle and Triangles Theorem (Theorem 1.2) is challenging.
The input of this problem is a cycle of length 3mand a partitionPof its
set of vertices into pairwise disjoint setsP
1,P2,...,Pm,eachofsize3. The
output, in the simpler problem, is an independent set containing exactly one
vertex in eachP
i, and in the harder problem it is a proper 3-coloring of the
cycle in which each color class contains exactly one vertex of eachP
i.There
is no known efficient algorithm for solving this problem, and yet it is also not
known to be PPA-hard (or PPAD hard). On the other hand, Haviv25]proved
that the more general algorithmic problem corresponding toProposition 3.2
is PPA-hard. Specifically, he showed that the following problem is PPA-hard.
The input is a partitionV=V
1∪V2∪···∪V mof the vertex set of a cycleCinto
mpairwise disjoint setsV
i, and the output is an independent set containing
at least|V
i|/2−1 vertices of eachV i. The proof proceeds by reduction to the
PPA-hardness results in20], and the setsV
ihave to be polynomially large (in
m) for establishing hardness. Therefore this hardness result does not apply to
the Cycle and Triangles Problem. It is worth noting that asTheorem 1.2ad-
mits several very different proofs, including an algebraic one and a topological
one, proving hardness for it may be difficult, as it would imply hardness for
the algorithmic version of each of the corresponding techniques from which it
can be deduced.
Note that if we replace the setsP
iof size 3 inTheorem 1.2by sets of size 4, then
the corresponding algorithmic problem does admit a simple efficient solution.
This follows from the proof in5]. The invariant studied there is the so-called
strong chromatic number of a graph. The strong chromatic numbersχ(G)of
agraphGwithnvertices is the smallest numberksuch that after adding
kn/k−nisolated vertices toG, for any partition of the set of vertices of
the resulting graph into disjoint subsetsP
1,P2,...,P
∞n/k⊆, each of sizek,there
is a proper vertex coloring ofGbykcolors so that each color class contains
exactly one vertex of eachP
i. The Cycle and Triangles Theorem asserts that
the strong chromatic number of a cycle of length 3mis 3, and as shown in5]
it is easy to see that the strong chromatic number of any graph with maximum
degree 2 is at most 4. For higher degrees, it is proved in[5]that the strong
chromatic number of any graph with maximum degreedis at mostO(d). The
hidden constant in thisOnotation has been vastly improved by Haxell[26],
who showed that this maximum possible strong chromatic number is at most
3d−1. For large valuesdthis is further improved in[27]to(11/4+ε)d

30. Fair Partitions 17
for alld>d
0(ε). It is believed, but not known, that the sharper bound 2d
always holds. Regarding the algorithmic problem it is shown in22]howto
find efficiently one independent set containing a vertex of each setP
iin any
partition of the vertex set of any given input graphGwith maximum degree
dinto setsP
i, each of size at least 2d+1.
•The discussion inSubsection 3.2suggests the following conjecture.
Conjecture 4.1For everydthere exists ac(d)so that for any graphHwith
at mostnvertices and maximum degree at mostdand for any partitionPof
the edges ofK
nintomcolor classes, there is a copyH
Θ
ofHinK nso that
x(H
Θ
,P)−
|E(H)|
|E(K n)|
x(K
n,P) ∞≤c(d).
The analogous conjecture for bipartite bounded-degree graphsHwith at most
nvertices in each color class and for partitions of the edges ofK
n,nis also
plausible. Note that the conjecture asserts that the same error termc(d)
should hold for any number of colorsm. Note also thatc(d)mustbeatleast
Ω(d) as shown by the example of a starH=K
1,dand the edge-coloring of
K
2nwithm= 3 colors described inSubsection 3.2.
•Another interesting question related to the results inSubsection 3.2is whether
or not for anydthere is a constantc(d) so that for any graphHonnvertices
with maximum degreedthere is a uniform cover of width at mostc(d)ofthe
pair (K
n,H). Together with Sacheth Sathyanarayanan we proved that this
is not the case for 3-uniform hypergraphs. Indeed, letH
(3)
n
be the tight 3-
uniform cycle of lengthnin which the vertices arev
0,v1,v2,...vn−1and the
edges are all triples{v
i,vi+1,vi+2}where the indices are reduced modulon.
This hypergraph is 3-regular, and it can be shown that ifK
(3)
n
denotes the
complete 3-uniform hypergraph onnvertices then any uniform cover of the
pair (K
(3)
n
,H
(3)
n
)isofwidthΩ(n). The definition of a uniform cover of a pair
of hypergraphs is defined just as it is defined for graphs inDefinition 3.4.
References
[1] R. Aharoni, N. Alon, E. Berger, M. Chudnovsky, D. Kotlar, M. Loebl and R.
Ziv, Fair representation by independent sets,in: A Journey through Discrete
Mathematics, (eds. J. Kratochvil, M. Loebl, J. Nesetril, R. Thomas and P.
Valtr), Springer, Cham (2017
[2] R. Aharoni, R. Holzman, D. Howard and P. Spr¨ussel, Cooperative colorings and
independent systems of representatives,Electron. J. Combin.22(2015
2.27, 14pp.
[3] N. Alon, Splitting necklaces,Advances in Mathematics63(1987
[4] N. Alon, Non-constructive proofs in combinatorics, inProceedings of the Inter-
national Congress of Mathematicians (ICM)(1990

31. 18 Noga Alon
[5] N. Alon, The strong chromatic number of a graph,Random Structures and
Algorithms3(1992
[6] N. Alon, D. Elboim, J. Pach and G. Tard´os, Random necklaces require fewer
cuts, in preparation, 2021.
[7] N. Alon and A. Graur, Efficient Splitting of Necklaces, inProceedingsICALP,
to appear, (2021), 18pp.
[8] N. Alon and M. Tarsi, Colorings and orientations of graphs,Combinatorica12
(1992
[9] N. Alon and D. B. West, The Borsuk-Ulam theorem and bisection of necklaces,
Proceedings of the American Mathematical Society98(1986
[10] R. A. Brualdi and S. Hollingsworth, Multicolored trees in complete graphs,J.
Combin. Theory Ser. B68(1996
[11] M. Buci´c, M. Kwan, A. Pokrovskiy and B. Sudakov, Halfway to Rota’s Basis
Conjecture,Int. Math. Res. Not. (IMRN21(2020
[12] S. N. Bhatt and F. T. Leighton, A Framework for Solving VLSI graph layout
problems,Journal of Computer and System Sciences28(1984
[13] R. A. Brualdi and H. J. Ryser,Combinatorial Matrix Theory,Encyclopedia of
Mathematics and its Applications, Cambridge University Press, Cambridge39
(1991).
[14] I. B´ar´any, S. B. Shlosman and A. Sz¨ucs, On a topological generalization of a
theorem of Tverberg,J. London Math. Soc. (223(1981
[15] G. M. Constantine, Edge-disjoint isomorphic multicolored trees and cycles in
complete graphs,SIAM J. Discrete Math.18(2005
[16] D. Z. Du, D. F. Hsu and F. K. Hwang, The Hamiltonian property of consecutive-
d-digraphs,Mathematical and Computer Modelling17(1993
[17] A. Dvoretzky and P. Erd˝os, Some problems on random walk in space, in Proc.
2nd Berkeley Symp, 1951, 353-367.
[18] P. Erd˝os, On some of my favourite problems in graph theory and block design,
Le Matematiche45(1991
[19] A. B. Evans, Latin squares without orthogonal mates,Des. Codes Cryptogr.40
(2006
[20] A. Filos-Ratsikas and P. W. Goldberg, The Complexity of Splitting Necklaces
and Bisecting Ham Sandwiches., inProceedings of the 51st Annual ACM Sym-
posium on Theory of Computing (STOC), (2019), pp. 638–649.
[21] H. Fleischner and M. Stiebitz, A solution to a colouring problem of P. Erd˝os,
Discret. Math.101(1992

32. Fair Partitions 19
[22] A. Graf and P. Haxell, Finding independent transversals efficiently,Combin.
Probab. Comput.29(2020
[23] S. Glock, D. K¨uhn, R. Montgomery and D. Osthus, Decompositions into iso-
morphic rainbow spanning trees,J. Combinatorial Theory, Ser. B146(2021),
439–484.
[24] C. H. Goldberg and D. B. West, Bisection of circle colorings,SIAM J. Algeb.
Discrete Methods6(1985
[25] I. Haviv, The Complexity of Finding Fair Independent Sets in Cycles,
arXiv:2011.01770, 2020, 18 pp.
[26] P. E. Haxell, On the strong chromatic number,Combin. Probab. Comput.13
(2004
[27] P. E. Haxell, An improved bound for the strong chromatic number,J. Graph
Theory58(2008
[28] R. Huang and G.-C. Rota, On the relations of various conjectures on Latin
squares and straightening coefficients,Discrete Mathematics128(1994
236.
[29] C. R. Hobby and J. R. Rice, A moment problem inL
1approximation,Proc.
Amer. Math. Soc.16(1965
[30] P. Hatami and P. W. Shor, A lower bound for the length of a partial transversal
in a Latin square,Journal of Combinatorial Theory, Series A115(2008
1113.
[31] P. Keevash, A. Pokrovskiy, B. Sudakov and L. Yepremyan, New bounds for
Ryser’s Conjecture and related problems, arXiv:2005.00526, 2020, 25 pp.
[32] A. Liapounoff, Sur les fonctions vecteurs completement additives,Izv. Akad.
Nauk SSSR4(1940
[33] H. B. Mann, On orthogonal Latin squares,Bull. Amer. Math. Soc.50(1944),
249–257.
[34] C. H. Papadimitriou, On the complexity of the parity argument and other
inefficient proofs of existence,Journal of Computer and System Sciences48
(1994
[35] A. Pokrovskiy, Rota’s Basis Conjecture holds asymptotically, arXiv:2008.06045,
2020, 9pp.
[36] N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for
hypergraphs,J. Combin. Theory Ser. A51(1989
[37] A. Pokrovskiy and B. Sudakov, A counterexample to Stein’s Equi n-square
Conjecture,Proc. AMS147(2019

33. 20 Noga Alon
[38] R. E. A. C. Paley and A. Zygmund, On some series of functions, (3Mathe-
matical Proceedings of the Cambridge Philosophical Society28(1932
[39] R. E. A. C. Paley and A. Zygmund, A note on analytic functions in the unit
circle,Mathematical Proceedings of the Cambridge Philosophical Society28
(1932
[40] E. Rold´an-Pensado and P. Sober´on, A survey of mass partitions, arXiv
2010.00478v2, 2020, 35 pp.
[41] H. Ryser, Neuere probleme der kombinatorik,Kombinatorik, Oberwolfach
(1967
[42] H. Sachs, Elementary proof of the cycle-plus-triangles theorem,in: Combina-
torics, Paul Erd¨os is eighty, Jan´os Bolyai Math. Soc., Budapest (1993
359.
[43] A. Schrijver, Vertex-critical subgraphs of Kneser graphs,Nieuw Arch. Wisk.26
(1978
[44] S. K. Stein, Transversals of Latin squares and their generalizations,Pacific J.
Math.59(1975
[45] H. Steinhaus, A note on the ham sandwich theorem,Mathesis Polska9(1938),
26–28.
[46] I. M. Wanless and B. S. Webb, The existence of Latin squares without orthog-
onal mates,Des. Codes Cryptogr.40(2006
Department of Mathematics
Princeton University
Princeton
NJ 08544
USA
[email protected]

34. Hypergraph Tur´an Problems in→ 2-Norm
J´ozsef Balogh, Felix Christian Clemen, Bernard Lidick´y
Abstract
There are various different notions measuring extremality of hypergraphs. In
this survey we compare the recently introduced notion of the codegree squared
extremal function with the Tur´an function, the minimum codegree threshold
and the uniform Tur´an density.
The codegree squared sum co
2(G) of a 3-uniform hypergraphGis defined
to be the sum of codegrees squaredd(x, y)
2
over all pairs of verticesx, y.In
other words, this is the square of the→
2-norm of the codegree vector. We
are interested in how large co
2(G) can be if we requireGto beH-free for
some 3-uniform hypergraphH. This maximum value of co
2(G)overallH
freen-vertex 3-uniform hypergraphsGis called the codegree squared extremal
function, which we denote by exco
2(n, H).
We systemically study the extremal codegree squared sum of various 3-
uniform hypergraphs using various proof techniques. Some of our proofs rely
on the flag algebra method while others use more classical tools such as the
stability method. In particular, we (asymptotically
squared extremal numbers of matchings, stars, paths, cycles, andF
5,the5-
vertex hypergraph with edge set{123,124,345}.
Additionally, our paper has a survey format, as we state several conjectures
and give an overview of Tur´an densities, minimum codegree thresholds and
codegree squared extremal numbers of popular hypergraphs.
1 Introduction
Given ak-uniform hypergraph (ork-graph)H,theTur´an function(orextremal
number)ex(n, H) is the maximum number of edges in anH-freen-vertexk-uniform
hypergraph. TheTur´an densityofH, denote byπ(H), is the scaled limit
π(H) = lim
n→∞
ex(n, H)
→
n
k
.
Determining these numbers is a central problem in extremal combinatorics. For
graphs (k= 2), this question is well-explored. The Erd˝os-Stone theorem[24, 23]
asymptotically determines the Tur´an density for graphs with chromatic number at
least three. For hypergraphs, determining the Tur´an density is notoriously difficult;
very few exact results are known. For example, the Tur´an density of the inno-
cent lookingtetrahedronK
3
4
, the complete 3-uniform hypergraph on 4 vertices, is
unknown.
In order to get a better understanding of these problems, various different kinds
of extremality such as the generalized Tur´an function or the minimum codegree
threshold have been studied. We[3]recently introduced a new type of extremality
for hypergraphs and solved the tetrahedron problem asymptotically for this notion.
Here, we will systematically study extremal problems regarding this function.
LetGbe ann-vertexk-uniform hypergraph. For a vertex setT⊂V(G), the
codegreeofT, denoted byd
G(T), is the number of edges inGcontainingT.Wedrop
the index ifGis clear from the context. Thecodegree vectorofGis the vectorX∈
21

35. 22 J.Balogh,F.C.Clemen,B.Lidick´y
Z
(
V(G)
k−1
)
,whereX(v
1,v2,...,vk−1)=d G(v1,v2,...,vk−1) for all{v 1,v2,...,vk−1}∈
ff
V(G)
k−1
π
. Finding ex(n, H) is equivalent to determining the maximumff
1-norm of
the codegree vector of anH n-vertexk-uniform hypergraph. Here, we study
maximality with respect to theff
2 codegree squared
sumco
2(G) is the sum of codegrees squared over allk−1setsT, i.e.,
co
2(G)=
σ
T∈(
[n]
k−1
)
d
2
G
(T).
In other words, the codegree squared sum is the square of theff
2
vector.
Question 1.1[3]Given ak H, what is the maximumff
2
of the codegree vector of ak H n G?
It also seems interesting to study Tur´an problems forff
p-norms forpother than 1,2,
in particular forpbeing close to 1.
We follow the notation introduced in[3]. LetFbe a family ofk-uniform hy-
pergraphs. We say that ak-graphGisF-free, if it does not contain anyk-graph
F∈Fas a subhypergraph. Denote by exco
2(n,F) the maximum codegree squared
sum among allk-uniformn F
densityσ(F) be its scaled limit, i.e.,
exco
2(n,F)= max
GisF-free
co2(G)and σ(F) = lim sup
n→∞
exco2(n,F)
ff
n
k1
π
(n−k+1)
2
.(1.1)
We3] σincluding the existence of the limit in (1.1). In
Table 1we present bounds and exact values for the codegree squared density of var
ious hypergraphs.Table 2provides the definitions with pictures of all hypergraphs
included inTable 1. σin this
table were obtained using Razborov’s flag algebra machinery58]. It is a standard
application of flag algebras to obtain these results; we give a short explanation of it
inSection 2.3.Table 1also gives an overview of known results for the Tur´an density,
the minimum codegree threshold and the uniform Tur´an density. Denote byδ(G)
the minimum (k−1)-codegree of ak-graphG, i.e.,
δ(G)= min
T∈(
V(G)
k−1
)
d
G(T).
For a family ofk-graphsF,theminimum codegree Tur´an numberex
k−1(n,F)isthe
maximumδ(G)overallF k-graphsGonnvertices. Theminimum codegree
threshold,
π
k1(F) = lim
n→∞
exk1(n,F)
n−k+1
,
is its scaled limit.
Reiher, R¨odl and Schacht[61]recently introduced a variant of the Tur´an density,
where we want to maximize the density of every linear sized subset ofH-free hyper-
graphs. For real numbersd∈[0,1] andη>0, a 3-graphG=(V, E)is(d, η,1)-dense

36. Hypergraph Tur´an Problems in⊂ 2 23
if for allU⊆Vthe relation
∩
∩
∩U
(3)
∩E
∩
∩
∩≥d
≥
|U|
3
φ
−η|V|
3
holds, whereU
(3)
denotes the set of all three element subsets ofU.Theuniform
Tur´an densityπ
u(H) of a 3-graphHis defined to be
π
u(H):=sup{d∈[0,1] : for everyη>0andn∈Nthere exists anH-free
(d, η,1)-dense hypergraphGwith|V(G)|≥n}.
Theorem 1.2All bounds presented inTable 1hold.
Here we collect many known results, and when known results are lacking, we at
least mention the ‘trivial’ bounds. Most upper bounds were obtained by a simple
application of flag algebras.
In addition to the bounds presented inTable 1,
maximum⊂
2-norm of 3-graphs not containing a loose cycle, loose path, matching
or star. These problems are not approachable with flag algebra methods due to the
fact that their codegree squared extremal number iso(n
4
). We use non computer
assisted methods to obtain these results. The discussion about the history of these
problems will be deferred to the corresponding sections. Additionally, we provide
a non-computer assisted proof determining the exact codegree squared extremal
number ofF
5.
Denote byS
nthe complete 3-partite 3 graph onnvertices with part sizes
φn/3ε,φ(n+1)/3ε,φ(n+2)/3ε.We[3]showed thatS
nis the largest{F 4,F5}-free
3-graph in⊂
2-norm using a simple double counting argument and the corresponding
⊂
1-norm result by Bollob´as[5]. Here, we will expand this result forF 5-free 3-graphs,
which requires more work than just applying the corresponding⊂
1-norm result.

40. Hypergraph Tur´an Problems in⊂ 2 27
Theorem 1.6Lets≥3.Ifsis odd, then
exco
2(n, S
3
s
)=s(s−1)n
2
(1 +o(1)).
Ifsis even, then
exco
2(n, S
3
s
)=
≥
s
2
−
3
2
s
φ
n
2
(1 +o(1)).
In this work, we are not intending to duplicate or replace the excellent survey[45]
by Keevash; our aim is to supplement it with new results and directions.
Our paper is organized as follows; inSection 2we explain our notation and
explain the flag algebra technique briefly. InSection 3we present the constructions
leading to the bounds onσ, π, π
u,π2inTable 1and state conjectures on some of the
non-sharp results. InSection 4we present the proof ofTheorem 1.3.InSections 5,
6and7we proveTheorems 1.4,1.5and1.6,
questions for higher uniformities inSection 8.
2 Preliminaries
2.1 Terminology and Notation
LetHbe a 3-uniform hypergraph,x, y, z∈V(H)andA, B, C⊆V(H)be
pairwise disjoint sets. We will use the following notation throughout the paper.
•For an edgee={x, y, z}∈E(H)wewritexyzfor convenience.
•Denote byL(x) the link graph ofx, i.e., the graph onV(H)\{x}withab∈E(L(x))
iffabx∈E(H).
•Denote byL
A(x)=L(x)[A] the induced link graph onA.
•Denote byL
A,B(x) the subgraph of the link graph ofxonly containing edges
betweenAandB, i.e.,V(L
A,B(x)) =V(H)\{x}andab∈E(L A,B(x)) iffa∈
A, b∈Bandabx∈E(H).
•Denote byL
c
A,B
(x) the subgraph of the link graph ofxonly containing non
edges betweenAandB, i.e.,V(L
A,B(x)) =V(H)\{x}andab∈E(L
c
A,B
(x)) iff
a∈A, b∈Bandabx∈E(H).
•e(A, B) denotes the number of cross-edges betweenAandB, this means
e(A, B):=|{xyz∈E(H):x, y∈A, z∈B}|+|{xyz∈E(H):x, y∈B, z∈A}|.
•Denote bye(A, B, C) the number of cross-edges betweenA, BandC, i.e.,
e(A, B, C):=|{abc∈E(H):a∈A, b∈B, c∈C}|.
•Lete=xyz∈E(H) be an edge. Define the weight ofeto be
w
H(e)=d(x, y)+d(x, z)+d(y, z).
We drop the index if the hypergraphHis clear from the context.

43. 30 J.Balogh,F.C.Clemen,B.Lidick´y
http://lidicky.name/pub/co2b/. Next, we will present the constructions which
give the lower bounds fromTable 1.
3 Bounds fromTable 1
3.1K
3
4
Tur´an’s tetrahedron problem asks to determine the Tur´an density ofK
3
4
.The
best lower bound,π(K
3
4
)≥5/9, is obtained byC n(seeFigure 1), the 3-graph onn
vertices with vertex setV(C
n)=V 1∪V2∪V3where||V i|−|V j|| ≤1fori=jand
edge set
E(C
n)={abc:a∈V 1,b∈V 2,c∈V 3}∪{abc:a, b∈V 1,c∈V 2}
∪{abc:a, b∈V
2,c∈V 3}∪{abc:a, b∈V 3,c∈V 1}.
Brown9], Kostochka50], Fon-der Flaass29] 33]
lies ofK
3
4
-free 3-graphs with the same number of edges. A series of papers[11, 16, 59]
have improved on the upper bound ofπ(K
3
4
) culminating in the current best-known
bound by Baber1]
π(K
3
4
)≤0.5615.
We3]
showingσ(K
3
4
)=1/3, where the lower bound is achieved byC n.
For the minimum codegree threshold Czygrinow and Nagle[14]provided a con-
struction that showsπ
2(K
3
4
)≥1/2. LetTbe a uniformly at random chosen tourna-
ment onnvertices. Define a 3-graphG
Tonnvertices by setting the tripleijkwith
i<j<k to be an edge ofG
Tif the ordered pairs (i, j)and(i, k) receive opposite
directions inT. This 3 graph isK
3
4
n/2−o(n)with
high probability. Using flag algebras we can prove thatπ
2(K
3
4
)≤0.529.
The previous construction was used by R¨odl[63]to show that for the uniform
Tur´an densityπ
u(K
3
4
)≥1/2. Erd˝os]
also see Reiher60]. Using flag algebras as described inSection 2.3,
π
u(K
3
4
)≤0.531.
3.2K
3
5
For the Tur´an density ofK
3
5
it is known that
3
4
≤π(K
3
5
)≤0.769533,
where the upper bound is obtained via flag algebras70]
obtained by the balanced complete bipartite 3-graphB
n(seeFigure 1)asobserved
by Tur´an]. The followingn-vertex 3-graphH
5(presented in[64], seeFigure
1) also achieves the lower bound. The vertex set ofH
5is divided into 4 parts
A
1,A2,A3,A4with||A j|−|A i|| ≤1 for all 1≤i≤j≤4andatripleeis not an edge
ofH
5iff there is somej(1≤j≤4) such that|e∩A j|≥2and|e∩A j|+|e∩A j+1|=3,
whereA
5=A1.

46. Hypergraph Tur´an Problems in⊂ 2 33
3.4K
k
t
Denote byK
k
t
the completek-graph ontvertices. Large cliques are studied
intensively for all notions of extremality. For an overview of results in⊂
1-norm see
[65], in⊂
2-norm see[3], and for the minimum codegree threshold see[52]and[66].
The best-known bounds for the Tur´an density are
1−
≥
k−1
t−1
φ
k−1
≤π(K
k
t
)≤1−
≥
t−1
k−1
φ
−1
,
where the lower bound is due to Sidorenko64]
Caen15].
Fork= 3, Keevash and Mubayi45]
this lower bound. Their construction forK
3
t
-free graphs goes as follows. Take a
directed graphGont−1 vertices with both in-degree and out-degree equal to one,
i.e.Gis a vertex disjoint union of directed cycles. Note that cycles of length 2 in
Gare allowed but loops are not. Now we construct aK
3
t
Hon
(t−1)nvertices. PartitionV(H)intoA
1,...,At−1of equal sizes corresponding to
verticesv
1,...,vt1ofG. A triplexyzis not an edge inHif and only if there exists
A
isuch thatx, y, z∈A i, or there existsv ivj∈E(G)with|{x, y, z}∩A i|= 2 and
|{x, y, z}∩A
j|= 1. Notice thatH 5fromFigure 1is a case of this construction with
Gbeing a directed cycle on four vertices with edgesv
1v2,v2v3,v3v4,v4v1.Other
examples areC
n,BnandH 6.
The best known extremal constructions in⊂
2 tare possibly un
balanced versions of this construction.
•Fort=4,C
nis the resulting 3-graph whenGis a directed triangle.
•Fort=5,B
nis the resulting 3-graph whenGis the union of two cycles of
length 2.
•Fort=6,G
6is the resulting 3-graph whenGis formed by the union of a
directed triangle with a directed cycle of length 2, up to balancing of the class
sizes.
This suggests3] Gis maximizing the number of directed cycles, the
resulting 3-graphHcould be extremal in⊂
2-norm.
For the minimum codegree threshold of cliques of large size, the best-known
bounds, obtained by Lo and Zhao52], are
1−c
2
logt
t
k1
≤π2(K
k
t
)≤1−c 1
logt
t
k1
,
wherec
1,c2>0 are constants depending onk.
3.5F
3,2
F¨uredi, Pikhurko and Simonovits[36]provedthattheTur´an density ofF 3,2is
4/9 which is achieved by the 3-graph with vertex setV=V
1∪V2, where all edges
have two vertices inV
1and one vertex inV 2and|V 1|=
2
3
n.

48. Hypergraph Tur´an Problems inε 2 35
uniform Tur´an density, we have
1
4
=π
u(K
3−
4
)≤π u(F3,3)≤0.605, (3.1)
sinceK
3−
4
⊂F3,3.Forπ u(K
3−
4
)seeSection 3.9. 3.1) is obtained
by the method of flag algebras.
3.7F
5
Frankl and F¨uredi31]provedthatforn≥3000 theF 5-free 3-graph with the
largest number of edges isS
n,thus,π(F 5)=2/9. The codegree squared density of
F
5isσ(F 5)=2/27 which follows fromTheorem 1.3,seeSection 4for more details.
The minimum codegree threshold ofF
5isπ2(F5) = 0. To be more precise, we
have ex
2(n, F5)≤2, because if there exists anF 5-free 3-graphGwithd(x, y)≥3
for all pairsxy, then take any pairaband two verticesc, d∈N(a, b). Now there
existse=a, b, c, dwithe∈N(c, d). Thusa, b, c, d, espans anF
5, a contradiction.
The uniform Tur´an density ofF
5isπu(F5)=0byTheorem 2.1,
edges of the shadow graph can be colored in the following way. Color the edges
12,34 red, the edges 13,14,35 blue, and the edges 23,24,45 green; seeFigure 3.
3.8 Fano PlaneF
Denote byFthe Fano plane, i.e., the unique 3-uniform hypergraph with seven
edges on seven vertices in which every pair of vertices is contained in a unique edge.
S´os[67]proposed to study the Tur´an number for the Fano plane and conjectured the
complete balanced bipartite 3-graphB
nto be extremal. This problem was solved
asymptotically by Caen and F¨uredi17]. Later, F¨uredi and Simonovits37]
independently, Keevash and Sudakov48]
largen. Recently, Bellmann and Reiher4] n.
We conjecture that the extremal example in the codegree squared sense also is
the complete bipartite graph.
Conjecture 3.1There existsn
0, such that for alln≥n 0
exco2(n,F)=co 2(Bn).
Furthermore,B
nis the uniqueF-free3-graphHonnvertices satisfyingco 2(H)=
exco
2(n,F).
We have 5/8≤σ(F)≤3/4 as trivial bounds using the complete bipartite 3-graph
as a lower bound and the fact thatσ(F)≤π(F)≤3/4.
The minimum codegree threshold was asymptotically determined to beπ
2(F)=
1/2 by Mubayi54]. He conjectured that ex
2(n, F3,2)=φn/2εfor large enough
n. This conjecture was solved by Keevash44]
argument. Later, DeBiasio and Jiang18]
We did not use flag algebras forFbecause our computers cannot handle the
number ofF-free 3-graphs on 7 vertices.
The uniform Tur´an density ofFisπ
u(F)=0by Theorem 2.1,because the
edges of the shadow graph can be colored in the following way. Color the edges

49. 36 J.Balogh,F.C.Clemen,B.Lidick´y
12,34,15,24,14,25,36 red, the edges 13,35,16,26,17,27,37 blue, and the edges
23,45,56,46,47,57,67 green, where the edges of the Fano plane are 123,345,156,246,
147,257,367.
3.9K
3
4
Denote byS 6the 3-graph on six vertices with edge set
E(S
6)={123,234,345,451,512,136,246,356,256,146}.
Letn=6
k
beapowerof6andlet Gbe the iterated blow up ofS 6. The iterated
blow-up ofS
6on 6
k
vertices is a balanced blow-up ofS 6, where each part contains
a copy of the iterated blow-up on 6
k−1
vertices. This 3-graphGwas constructed by
Frankl and F¨uredi32] an density ofK
3−
4
.SinceG
isK
3−
4
π(K
3−
4
)≥2/7. The best know upper boundπ(K
3−
4
)≤0.28689 is by
Vaughan70] Ghas codegree squared sum
co
2(G)=
1
2
n
4
⎛
⎝
⊆
i≥1
5
6
i
≥
2
6
i
φ
2
+o(1)
⎞
⎠=10n
4
⎛
⎝
⊆
i≥1
1
216
i
+o(1)
⎞
⎠
=10n
4
1
1
1−
1
216
−1
2
(1 +o(1
2
43
n
4
(1 +o(1)).
Thus,σ(K
3
4
)≥4/43. We conjecture thatGis the extremal example in⊂ 2-norm.
Conjecture 3.2
σ(K
3
4
)=
4
43
≈0.0930232558.
Flag algebras only giveσ(K
3−
4
)≤0.09306286. The minimum codegree threshold
ofK
3−
4
was determined to beπ 2(K
3−
4
)=1/4 by Falgas-Ravry, Pikhurko, Vaughan
and Volec27] 57]. The lower bound is obtained by a
construction originally due to Erd˝os and Hajnal22]. Given a tournamentTon the
vertex set [n], define a 3-graphC(T)on[n] by taking the edge set to be all triples
of vertices inducing a cyclically oriented triangle inT. No tournament on 4 vertices
can contain more than two cyclically oriented triangles, henceC(T)isK
3−
4

Tis chosen uniformly at random, then the minimum codegree ofC(T)isn/4−o(n)
with high probability.
The uniform Tur´an density ofK
3−
4
was determined to beπ u(K
3−
4
)=1/4by
Glebov, Kr´al’ and Volec40]
by Reiher, R¨odl, and Schacht[62]via regularity method of hypergraphs without flag
algebras. The lower bound is also achieved byC(T).
3.10{K
3−
4
,F3,2,C5}
Denote byH
7the 3-graph on seven vertices with edge set
E(H
7)={124,137,156,235,267,346,457,653,647,621,542,517,431,327}.

50. Random documents with unrelated
content Scribd suggests to you:

51. Ghoorkas, whom he consulted, did not share in his fear. Bâl Narîn,
they said, knew what he was about. Most likely he did not care to go
any farther that night, and he had laid down where he was, so as
not to be ordered on. If he did not join them in the evening, they
would certainly see him at daybreak. With this Tom tried to be
satisfied, for it was quite evident that he could do nothing. The men
would not stir without Bâl Narîn, and for him to do so alone would
be as useless as it was dangerous.
They made him up his usual evening meal, a mess of rice and fried
vegetables; but he could not eat a morsel. Mounting his horse, he
rode slowly back to the point where he had seen Bâl Narîn last. Here
he whistled, cried out, tried to ride through the kutcha-grass; but
was driven back by the venomous tribes of insects that had come
out with the dying down of the day; then realising that these
spasmodic efforts were perfectly useless, he returned to the road,
and paced back sadly and slowly, seeing no signs of Bâl Narîn
anywhere.
The camp was illuminated by gleaming brands set high on poles,
and the little cooking-fires were smouldering in its midst. It made a
spot of glowing red in the spectral darkness; where everything but it
was being slowly obliterated. Tom would have preferred the
darkness; but he knew very well that in the jungle he was
surrounded with nameless dangers. If he did not wish to give his
body for a meal to the beasts of prey that were ranging it, he must
keep in the neighbourhood of his companions. So, trying to still his
fiery impatience, he lay down where they had spread his canvas
sheets, drew a gauze net over his face, and lighted a pastile to keep
the cloud of insects at a distance.
I have spoken of Tom's gift of sleeping at will. Even in this terrible
emergency it did not desert him. He had learned a few lessons,
however, in his life of adventure, and it would not have been so easy
now as on his first expedition to steal a march upon him.
The sleep, light and brief as it was, refreshed and invigorated him.
When, having indulged in it for about two hours, he sprang up and

52. looked round, he found that the feverish madness of excitement
which, if given place to, would have unfitted him for work that
needed decision and readiness, had gone. His brain was clear, and
his limbs had lost their languor.
In the encampment everything was as it had been. The fires were
smouldering and the torches flamed. Two Ghoorkas were on guard.
The rest slept, while the camel-drivers, syces, and coolies sat
doubled up together, their knees touching their noses, near the
beasts of burden which were tethered in the centre of the
encampment.
It was dead night; but the darkness was not such as it had been
earlier, for a three-quarter moon had come up from her bed of
snows behind awful Himâla and was shedding over the desolate land
a pale light, which, defective as it was, Tom hailed with pleasure.
'You have often been my friend, Lady Moon,' he said, as he gazed up
into the vapour-veiled sky, 'and though you don't shine as you do in
the plains, I think you will give me light enough to see what I am
doing.'
One of the Ghoorka sentinels, in the meantime, seeing him on his
feet, had approached him. 'Does the Rajah Sahib require anything?'
he asked.
'I want to know if Bâl Narîn has been seen,' said Tom.
'Bâl Narîn has not come back to camp,' answered the man.
'Then, of course, he has not been seen,' said Tom impatiently. 'Have
you heard anything?'
'We have heard nothing but the beasts of the jungle. Purtab killed a
serpent. It would have stung him. The gods grant that it may not
bring misfortune!'
'The gods have brought Purtab good fortune, my friend. His life is
better than a snake's—to himself at least.'
'That is as it may be, Sahib,' said the man enigmatically.

53. 'Settle it your own way, but, in the meantime, listen to me! I don't
like this lengthened absence of Bâl Narîn's, and I fear some evil has
come to him. I will go and look round.'
'If you go far, Sahib, you will never return. This is the devil's hunting-
ground. Men in company they spare. Solitary men they destroy.'
'Then how about Bâl Narîn?'
'Even the devil will not slay his own offspring,' said the man with a
chuckle. 'Bâl Narîn is safe, wherever he goes.'
'Is he?' said Tom laughing. 'I wish I had such distinguished ancestry;
however, I am not afraid. I have my revolver and my sword. If I
whistle, try and find me.'
'Right, Sahib!' said the man, falling back.
END OF THE SECOND VOLUME.
CHAPTER XXXIX
WHAT BÂL NARÎN HAD BEEN DOING
We return to Bâl Narîn, whom we left pondering deeply on the
significance that might belong to a muslin thread and two little silver
beads.
To make this part of my narrative clear, I must explain, having
received the information from this cleverest of Ghoorka guides, that
besides the robbers' path, as it was called, there were other narrow
tracks running in every direction through the jungle. These were due
to the animals that at this season make the kutcha-grass their
haunt. Wild beasts, like civilised men, are the creatures of habit.
They love their old lairs and their daily walks, and are given to
ranging certain circumscribed areas, which, no doubt, are to them

54. what our village, city, or club is to us. These animal highways, then,
had, through repeated use, become widened and trodden down, so
that it would have been easy for the inexperienced to mistake them
for paths frequented by men. When Bâl Narîn so impetuously waved
Tom away, the notion that thus it might have happened to the
fugitives of whom he was in search had suddenly come to him. It
was a terrible thought, for in such case they would probably have
walked right into a wild beast's lair, and nothing could save them
from destruction. The idea, however, having occurred to Bâl Narîn,
he could not cast it off.
His mind was of that dogged type which often distinguishes men of
his profession. From his boyhood it had been his meat and drink to
struggle with difficulties and overcome them. The more arduous the
task the better it pleased him, and the mere fact of his having
entertained the possibility of undertaking it was stimulus sufficient to
make him carry it through. By sympathy in the first place and severe
personal effort crowned by partial success in the second, he had
worked himself up to strong interest in this work of rescue, and
passionate determination that nothing should be wanting on his part
to bring it to a successful issue. All the force, all the dogged
resolution of his nature was aroused. Working for the master whose
kindliness and grace had won his attachment, he was also working
for himself, that no man in the future might relate how Bâl Narîn had
failed in the task he took in hand.
It was in this mood that the new idea met him, and he set himself
immediately to work it out. On the robbers' road, where he had been
told he might find the fugitives, he had seen indications which led
him to believe that he was on their track. If these indications
continued he would know, as far as it was possible to know
anything, that the fugitives were on ahead of him. If, on the other
hand, they stopped at any particular point, there would be every
reason to suppose that the road had been abandoned, in which case
he saw that there would be nothing for him to do but to try the
likeliest of the jungle paths.

55. Quietly he stole on. A few yards ahead of the spot where he had
paused to take his bearings the road was crossed by a path wider
than itself, and of such character and appearance as to be almost
certain to mislead any but the dwellers in the jungle, or those who,
like Bâl Narîn, had traversed it so often as to be fully acquainted with
all its peculiarities.
He happened to know it, for it led to a little marsh surrounded lake
where the tigers went down at night to quench their thirst, and near
which he had waited for them more than once with European
sportsmen.
He had lighted his lamp meanwhile, for he always carried one in his
belt, and with its help he was examining the ground. Close to the
opening of this jungle-road, where it turned off the road to the right,
he found a third bead. He went on for some distance and saw
nothing, then he retraced his steps. A conviction amounting almost
to certainty had come to him that it was down this pathway those
poor souls had gone. If so he must follow them. Having looked well
to the priming of his revolver, and taken from its sheath the short,
murderous-looking knife, which he had used several times with
effect in close encounters with his fierce jungle-foes, Bâl Narîn
adventured himself into the wild beasts' highway.
At first he found nothing to confirm his conjecture. The character of
his surroundings had changed. Instead of the tall kutcha-grass there
were about him low, thorny bushes, with here and there a ghostly-
looking tree; and nullahs, in which hideous forms of vegetable life
were growing, stretched along the sides of the beast-trodden path. A
strange way it was, and devious, going straight for a few yards, and
then shooting from right to left, as, like the fire-flash from lightning-
charged clouds, it followed the track of least resistance. A dangerous
region, and Bâl Narîn, being too old a hunter to be caught napping,
trod warily. Once, however, he almost lost his caution. It was when
the light of his lamp fell on a shred of coloured stuff that clung to
one of the spiked leaves of a sickly, stunted aloe. That moment, he
has told me, was one of the strangest, the most triumphant of his

56. whole fife. He knew now that the sagacity upon which he prided
himself had not failed him in his need. Whether the fugitives were
found or not, he had positive proof that they had passed this way.
Meanwhile the darkness that had made Tom curse his helplessness
began to assail Bâl Narîn's more subtly tempered senses. He did not
mind it. All his greatest enterprises had been carried out in the night
time, for it was then that the foes with whom he waged war were at
large, and the blackness of the heavens rather quickened than
deadened his energies. He drew aside quietly from the beasts'
highway, let his lamp, which was burning steadily, shine in front of
him, and having twisted some of the gigantic stems of the kutcha-
grass into a torch as he came along, he set light to it, and held it
flaming over his shoulder. Thus equipped he was far too terrible an
object for even the man-eating tiger to tackle. So he went on
towards the marsh-surrounded lake.
But what was his distinct object? He could not, I think, have
explained it to himself. I found, in fact, when I tried to pin him to
this point of his narrative, that a peculiar confusion reigned in his
mind. Up to it and beyond it he was perfectly clear. He could tell
about everything, even the working of his own mind. Here he
faltered and stumbled in his speech. 'Why did I go on?' he exclaimed
to me one day. 'Sahib, I must confess to you that I cannot tell. I
should have been mad to think that they were alive. I should have
been mad to suppose that, if they were alive, I should find them in
that darkness. I knew I was going into danger. Think, Sahib, of
where I should have been if my lamp had gone out. I thought of
that myself. "Billy," I said, "you are a fool. You are running into
danger like an ass that has no wit to keep out of it. Go back! Tell
them at the camp what you have found, and bring the rajah and his
men with you to search this place in the daylight." That would have
been the wisest plan, Sahib. Why did I not take it? As I live I cannot
tell you. Sometimes,' his voice dropped mysteriously, 'I have thought
that it was not of my own will I went forward. The Sahib, being a
wise man, will understand. There are things of which it is not well to

57. speak too plainly. The jealousy of the gods is easy to rouse, and
difficult to stay.'
I knew what Bâl Narîn meant, and I nodded my approval,
whereupon he proceeded with his story. Though, as he had
confessed, he was going forward without any distinct aim, his
vigilance did not sleep for a moment. His ear, trained to a subtlety of
perception such as we, dwellers in towns, and inheritors of the
grossness born of luxurious living, can scarcely imagine, was alive to
every sound. His eyes searched the darkness. His sense of touch,
which was not, as with us, confined to the effects that arise from
actual contact, sent out feelers in every direction. Through his
delicate nostrils—the subtlest of the nine gates of the body—he
interrogated the humid atmosphere, finding separate odours where
we should have distinguished nothing but the vaporous distilments
of the jungle.
Presently he came to a full stop, lowered his torch, and drew a long
breath. Something strange, subtle, impalpable, was floating towards
him. He could not for a moment determine what it was or even
through which of the sense-avenues it had come; but he knew, he
was penetrated with a conviction as strong as death, that presences,
either spiritual or corporeal, but other than the beasts of the jungle,
were near him.
He paused for fully five seconds, making an effort to define his
sensations, and in the meantime he made another observation.
Overhead the darkness grew darker, there was a curious agitation of
the air, and he knew that the vast birds of the mountains—the eagle
and the vulture—were flying round him in ever-narrowing circles.
The dead or the dying, then, were near, and they had scented them
from their eyrie in the hills. At this moment, when he had recognised
the birds as blots on the blackness, and was straining his eyes to
follow their flight, there was a faint glimmer of light in the east from
the rising moon. Faint as it was it gave the shikari all the light he
needed to enable him to see plainly. He looked up and saw a
gigantic bird sailing slowly down the wind. His heart beat, and his

58. blood seemed to bound in his veins as he watched it, for it was
taking the direction whence his own sense-perception had come. A
second followed, and then a third. By the help of the silver light in
the east he was able to keep them in sight. Leaping nullahs, tearing
through thick jungle, uttering fierce cries to frighten away the wild
creatures that might be crouching in cover, he followed in their track.
If he had stopped to think, as he has told me, he could not have
done it. Nor would it ever have occurred to him to follow the birds,
had it not been for that impression, inexplicable even to this day to
himself, that unseen presences were near him. But once started he
staggered on. Insects stung him, thorns cut into his flesh, his torch
was extinguished, his lamp burned dim. Through all his excitement
he realised that if he was left in darkness he was lost beyond hope
of redemption. His life-foes would have him as their prey. No one
would ever hear of Bâl Narîn again. Once he fell, but he sprang to
his feet again and flourished his lamp, and a tiger, disturbed in his
lair, rushed by with angry growling that would have chilled the blood
of a man of ordinary courage.
But still he held on. The vulture sailed on, swooped down, rose into
the air with a harsh cry—was it of disappointment?—swooped down
again, and was lost in the jungle. But Bâl Narîn was triumphant, for
he had marked the very spot of his disappearance. The second bird
and the third sailed up. They helped him to mark the spot. He could
not mistake it now, for a tall cotton-tree, whose candelabra-like
branches stood out boldly from the silver grey of the eastern sky,
was in its immediate neighbourhood. There were few of these trees
in the Terai, and they indicated places where the soil was
comparatively wholesome. So far as he could judge he was not now
very far from the tree which made his landing mark, but there was
still a wide nullah to be crossed. Torn and exhausted as he was he
experienced some difficulty in getting to the other side, and he
considered himself happy in meeting no tiger. He had scarcely force
left to grapple with one.
And now, to his measureless surprise, he saw the jungle open out
before him. A small clearing, such as those in which the Aswalia

59. villages are planted, only of much more limited extent, lay under his
eyes. A low fig-tree, a stunted bamboo, and the cotton-tree which
he had already seen, could be dimly discerned through the darkness.
Nothing else at first except the three vast birds. They sat side by
side under the cotton-tree, as if in hideous expectation of a feast.
Bâl Narîn stamped his foot and cried out, and they rose slowly, but
they did not go far. They hovered overhead, and it seemed to him
that they were watching his movements.
And now, pausing, he could hear distinctly sounds as of fluttered
stirring to and fro, and breath drawn labouringly. He trimmed his
lamp and went on cautiously, carrying it before him. In a few
instants its light fell on a rude shed, made of branches of trees and
dried leaves. On the side by which he had approached it there was
no opening; but he could see, through the interstices between the
branches, that figures were moving about within. Giving it rather a
wide berth so as to see before he was seen, he came round to the
front, and pulled up for a few moments to observe what was going
on.
Within the small enclosure, which was such a hut as hermits dwell
in, he saw three figures. Two were on the ground, whether dead or
asleep he could not tell, and the third—a slender figure in woman's
garments—was going from one to the other, stooping over them,
and, as it seemed to Bâl Narîn, weeping bitterly. While he was
considering how he should reveal himself without increasing her
distress and alarm, she came out to the front of the hut, and, his
lamp being turned that way, he saw her plainly. That was a moment
which Bâl Narîn will never forget. For an instant he shut his eyes. He
was seized with a tremor that seemed to be drawing away his
power, and the presence of mind on which he prided himself. Wild as
she was, with that haunting terror in her sweet eyes that was never,
so long as she lived, to leave them again, there was a beauty and
majesty in this face that awed him, he could not have told why. It
was like the face of a spirit, he said—of one who had done with the
earth for ever. Thus for a moment he saw it; in the next it was
suffused with a horror and anguish, such as he had never beheld

60. before. Looking up, he saw the heavens darkened with the wings of
the birds of prey that were swooping nearer and nearer to the
entrance of the hut, as if they would defy this weak living woman to
keep them any longer from the dead.
A cry of unspeakable despair broke from the woman's lips, and she
agitated her arms wildly above her head. They retired, settled,
approached again, the girl still gesticulating wildly. Then the ping of
the shikari's revolver rang through the jungle. Again it sounded, and
again, the girl retreated trembling, and two of the birds fell to the
ground mortally wounded, while their mate sailed away sullenly to
his eyrie in the hills.
Before the echo of his last shot had died away, Bâl Narîn was
standing with bowed head before the girl in the hut, and addressing
her in his choicest Hindoostani. 'Let me entreat my gracious lady not
to fear me,' he said. 'I am a poor hunter from the hills—a man of the
Ghoorka nation, to whom the white races are honourable. I saw my
gracious lady's distress, and I slew the birds that caused her fear.
Can I help her further?'
'Could you help me—would you?' said the poor girl.
'Let my gracious lady try me?' said Bâl Narîn.
At this moment there rang another sound through the jungle—a low
whistle, prolonged and flute-like, but curiously tremulous, that
seemed to be floating down from above them. The girl pressed her
finger to her lips, and a colour, soft as the crimson of the morning,
flooded her pale face.
The tremulous, sweet sounds go on—they form themselves into a
melody. Ah! What is this? What is this? In a moment—in less than a
moment—the poor girl is back again in the past. Under her feet is a
carpet of soft, green grass; above, swayed gently to and fro by the
breath of a June morning in England, wave the light branches of a
weeping willow-tree—the waters of a river lie before her—a boat is
cutting through them—it has one rower. Oh! the fair, boyish face—
the dreamy eyes—the rapture of adoring love!

61. 'Come where my love lies dreaming,' he sings.
'Yes; I am dreaming. I must awake,' sobs poor Grace.
The sounds go on—distant but clear. 'Dreaming the happy hours
away—Come—Come—Come where my love——' Groaning, she
covers her face with her hands.
Bâl Narîn, in the meantime, is showing the most extraordinary
excitement—shouting, dancing, tossing his hands about in
exultation. Returning from her dream, the girl gazes at him in
speechless surprise.
'Pardon your servant, gracious lady,' he says, 'if his pleasure lifts him
off his feet! My master and I have waited for this moment. As the
sick unto death long for the morning, so have we longed for it, and
how can I help being triumphant?'
'Your—master?' says the girl, fixing her large, fever-bright eyes upon
his face.
'My master—the Rajah of Gumilcund. He is on his way. He will be
here soon, if—now the demons of the jungle guide him! Here! here!'
he cries, lapsing into his native Ghoorka in his overpowering
excitement. 'Look for the cotton-tree! Ah! what a fool I am! He does
not know my tongue. Lady, you have a light within?'
Trembling with excitement, Grace ran inside and caught up a little
rush-candle—their last!
'One moment, dearest Kit!' she cried, for a little moan had come up
from the ground. 'They have found us. Tom—our Tom—will soon be
here. He will frighten the dreadful birds away.'
She ran out to Bâl Narîn, who had torn off a dried stick from the
cotton-tree and twisted a bunch of withered grass to its extremity.
Anointed with the drop of oil left in his lamp and lighted from the
rush-candle, it flamed out brilliantly in a moment. He waved it over
his head and rushed forward with shouts into the jungle, 'This way,
master; this way!'

62. But in a few instants he returned to the space before the hut, fed his
torch with wisps of straw, and caught up the rush-candle. The
whistling had ceased, and there was no answer to his frenzied cries.
Grace looked up into his face and saw its hazard look.
'Is he not there?' she moaned.
'It is a dangerous road,' he answered, 'and my master is not a
shikari like Bâl Narîn. Listen, Miss Sahib! Do you hear that?'
'Thunder. I have heard it several times to-night.'
'Not thunder—the tramp of a herd of wild elephants. Miss Sahib, I
must go——'
But Grace did not hear. She had rushed back into the hut. With
hands cramped together and beating heart she was crouched on the
ground, near the couch of dried grass where she had laid her little
Kit, praying that the Father in heaven, in Whom through all these
dreadful days she had trusted, would, at this last moment, be
gracious to them.
'Save him, oh! Father,' she sobbed. 'Let him take my darling Kit from
this awful place, and then my work will be done, and I will go to
Thee.'
Over and over again, while Kit's little arms were about her neck and
his burning cheek rested on her shoulder, she whispered the same
words, 'Save him! Save him!'
Moments passed into minutes. The hold of Kit's arms relaxed, as,
lulled by the sound of her voice, he fell back upon the pillow. Her
own head drooped. The long and awful watch by the dead that lay
in the hut with them—the sudden shock of terror and joy—the
suspense—the strain of expectation seemed to be more than her
enfeebled frame could bear. Her mind wandered. 'Kit! keep me
awake,' she whispered. 'Those awful birds will come again.' But Kit
did not hear her. He was dropping off into a doze. Her eyelids fell.
Oh! if she could only sleep! If somebody was here—a friend—some
one who would watch for her, and keep the birds and beasts away!

63. Ah!—she started up suddenly, wide awake and trembling in every
limb. The light that was diffused through the tent—that shone on the
rigid form of the old man who had protected them so far, giving at
the last his life for theirs, and on the yellow matted curls of poor
little Kit—was the light of the moon. There was nothing to keep the
wild things out. A convulsive shudder agitated her frame, and she
tried to rise but could not. Then she put her face down near Kit's.
'My poor darling,' she whispered. 'It is all over. I had a dream. It has
gone—and I have no more strength to fight.'
CHAPTER XL
THE ELEPHANTS' CHACE
This, in the meantime, was what had been happening to Tom.
When, having provided himself with tinned meats and a bottle of the
powerful restorative which he had always on hand, he left the camp,
he had turned, by what he spoke of afterwards as a happy instinct,
into the track which Bâl Narîn had been following, before the strong
impression of human neighbourhood and the eccentric movements
of the three birds of prey had started him on his perilous journey
across the belt of jungle that lay between the wild beasts' track and
the hermit's hut.
He, too, was well-armed with light and weapons, and he went
cautiously lest he should be taken by surprise. Suddenly the ping of
Bâl Narîn's bullet aroused him. He waited until the echoes died away
to make sure of the direction whence the sound had come, and then
dashed into another track. He was in great doubt as to whether he
was right, for there is nothing more confusing than the sound of
firing in a wood. The detonations repeated again and again, and
dashed, as it were, from one opposing substance to another, seem
to come from a hundred points at once. Instead of approaching Bâl

64. Narîn he might be putting immeasurable distance between them,
while, on the other hand, it was quite possible that one of a
company of robbers or fugitive sepoys had fired, in which case a
deadly conflict would be before him.
The prudent course would have been to retreat while he could, to
rouse his little camp, and to take the advice of those who knew
more than he did about this dangerous region. Tom, however, never
once thought of retreating, for he was launched—launched, as he
felt even at that moment of doubt and difficulty—on the last stage of
his enterprise; and, if hell and all its legions had yawned at his feet,
he was bound to go on.
The path into which he had struck, as being that which seemed to
lead in the direction where he had heard the firing, was
comparatively easy. As he went on cautiously, throwing the light of
his lamp in front of him, he felt surprised that he met with so few
difficulties. For a space several yards in width the tall kutcha-grass
was so completely trodden down, and the low trees and bushes,
with their rank wealth of undergrowth, were so uniformly levelled to
the ground, that he could have imagined an army with artillery and
baggage-waggons had passed this way. That such a thing was
impossible he knew very well, for he had studied the map of Terai
again and again with Bâl Narîn. The maharajah's road, which was
the only one used for military purposes, was many miles distant
from the point they had reached. But what he did not know was that
he was in the very track of the monarch of the jungle. Eight months
before, when the plains of the north-west were at peace, and the
Terai was unhaunted by the deadly fever that, for three-quarters of
the year, makes it uninhabitable to all but the savage Aswalias, Jung
Bahadoor, who was at that time one of the keenest sportsmen of his
generation, brought down from the high Nepaul valley a gallant
company of hunters, mounted on tame elephants of proved skill and
sagacity, to chase and capture some of the wild elephants that have
their dwelling in the morass and jungle, and it was along this road
that the hunters had come. A terrible chase it was to any but men
mounted and caparisoned as they were, for the wild herd had made

65. it their drive. Hither they came, from the mud in which they had
been wallowing—night after night in awful phalanx serried—to drink
from a pool in the morass, and to tear down the tall grasses and
trees on their passage, for the succulent young shoots that made
their food. Had Tom met the dark army, he was lost. Not even the
flaming torch, which was a protection from serpents and tigers,
would have saved him. They would have rushed over him—crushed
him into a grave, where even the birds of prey would scarcely have
found him.
Of this danger—the worst that had ever threatened him yet—Tom
had no more idea than a child. He trusted for his protection to his
torch, his lamp, and his weapons, and all the energies he had to
spare from picking out his way were bent on watching for anything
that might indicate human neighbourhood. That, at a moment so
critical, his mind should have strayed even for an instant from the
scenes in which he found himself, seems so strange as to be almost
incredible. He was alone; he was surrounded with unknown perils;
an object dearer far to him than the preservation of his own life was
—or seemed to be—within his grasp; everything might depend upon
the way in which he met the next few moments; and yet—I have it
on an authority which there is no disputing—at this point his mind
began to wander.
He could not help it, any more than he could have helped the
curious transfusion of his own thoughts and ideas with those of
another, which had come to him now and then since the night when
he wandered unbidden into Grace's rose-garden, and dreamed his
dream of fear. It came suddenly too, and without, as it seemed,
anything to lead up to it. When, thinking to make a signal to Bâl
Narîn, he lifted to his lips the flute-like reed which he always carried,
and felt his breath quiver through it, he stepped all at once into
another world. Instead of the long shrill whistle he had intended to
send forth, it was the notes of a melody, which he had sung a year
ago, floating with oars suspended, on the reach of the silver Thames
by the lawn of the General's little garden, that stole out on the
pestilential air of the wild beasts' haunt—'Come where my love lies

66. dreaming—dreaming the happy hours away.' Was it his own voice—
or was it the voice of another? He paused and looked round him
trying to collect his thoughts. Ah! to him too the scene is changed.
What are these—what are these—that come towards him out of the
darkness? Old hopes—old memories, old dreams. He is the Indian
rajah no longer—he is the English boy, into whose heart the honeyed
sweetness of a new land of promise is stealing. 'My love! my love!'
under his breath he whispers the magic words. And then again he
lifts the reed to his lips, and again the melody that he dared to sing
long ago, close—close to his darling's rose-bower—floats out upon
the air. 'Come! Come! Come where my love lies dreaming!'
Unconsciously—blindly—he was rushing on. He did not hear the
thunder behind him, and the mad cries of Bâl Narîn made no
impression whatever upon his senses. Why he swerved aside—how
it came about that he should have dashed into the jungle and
precipitated himself into the deep nullah that yawned close by, he
never knew. He thought he saw the flashing of silver water through
trees—this is the only explanation he could ever give. But,
meanwhile, as bruised and shaken, he lay in the slime, wondering
what had come to him, and bitterly cursing himself for his folly in not
being able, at a crisis so momentous, to keep his wits about him, the
black army that had been marching in his rear, dashed over the spot
where, but a few moments before, he had been tranquilly walking.
It took Tom some little time to recover his breath, climb to the edge
of the nullah, and shake off the mud from his clothes. That time, as
we know, had been spent by Grace in frenzied prayers to Heaven,
and by Bâl Narîn in no less frenzied ejaculations and gestures. When
silence fell upon the hut and silence upon the jungle—a silence
fearfully broken by the earth-shaking tread of the herd of elephants
—when he whistled and shouted, and fired wildly over his head, and
no one answered, he made up his mind that all was lost. The young
lord whom he had accompanied for gain, and clung to in despite of

67. his own better judgment for love, had met with a sudden and fearful
death at the very moment when his end was won.
Overcome for a few instants by pity and sorrow, Bâl Narîn covered
his face and wept.
A desire came over him then to see what was left of his unfortunate
young master, and leaving the little clearing he plunged into the
jungle. His senses being far better trained than Tom's, he had no
doubt whatever about the direction he should take. The last
articulate sound the rajah had made, before darkness and silence
swallowed him up, came from a point known to Bâl Narîn, who had
been one of the mahouts in Jung Bahadoor's famous hunt, as a
sharp curve in the elephants' drive. For this point he was making as
speedily and cautiously as he could, when a tall figure—bareheaded,
and covered from head to foot in a coating of mud—stood suddenly
before him.
Grasping his weapon, Bâl Narîn challenged the man. He was
answered by a voice that made his heart leap into his mouth. 'Don't
you know me in this disguise, Billy?' it asked.
'Rajah Sahib'—cried the poor fellow passionately. 'Forgive me. I
would have searched for you amongst the dead. Now thank the gods
and the demons of the jungle, who have been favourable to his
Excellency!' And he fell down before him and held him by the feet.
'Get up, you foolish fellow!' said Tom, who was touched, although he
would not show it, by his devotion. 'I have fallen into a mud-bath,
and got myself into a pretty mess; but why you should have thought
me dead, I confess I don't see. You must have come this way
yourself, since I find you here.'
'This way, that is true, Rajah Sahib, and why I came only the gods
know. But I kept clear of the Elephants' Chace. I would no more
have adventured myself there than I would have slipped my neck
into an enemy's noose.'
'The Elephants' Chace,' stammered Tom, 'was that road——?'

68. 'It is the deadliest road in all this region for a man not furnished as a
hunter,' said Bâl Narîn. 'And the herd has just gone by. How his
Excellency escaped is a mystery.'
'The herd—of what, Billy——?'
'Does not my lord know——?'
'I understand,' said Tom, a shiver, which he could not control,
running through him. 'Wild elephants! My life must be valuable to
some one, Billy. Yes; I heard them. I thought it was thunder. I must
have only jumped into the nullah in time. And I wasn't trying to
escape. Well! it is over now, so there's no use thinking about it. I will
stick to you for the future, my good friend! Why did you separate
yourself from us last evening?'
'If I tell my master, he will scarcely believe me,' said Bâl Narîn.
'Billy! Billy!' Tom was trembling from head to foot. 'You have found
something.'
'I have found those his Excellency is seeking.'
'What? The English lady and the child. And in life? Billy, you are
torturing me. Speak plainly. No; no; I cannot bear it. Don't speak at
all. I shall see. And yet—where has my manhood gone? If they are
dead——'
'Master, they are not dead.'
'Not? Now Heaven be praised!'
'Yes; but my master must be careful. See! there are pits here! If his
Excellency goes in so headlong a fashion, he will break his limbs,
and how will that profit his friends? Let him follow me, and I will
take him where they are.'
'Yes; yes; I will follow you—my good guide—my noble guide! If all I
have can recompense you, it is yours. But it cannot.'
'That my master gives me his confidence still is all I ask,' said Bâl
Narîn.

69. 'My confidence! I am bound to you for ever and ever. From this day I
look upon you as the nearest and dearest of my friends. But how, in
the name of heaven, could you have found them in this thicket?'
'That is a long story. Some day I will tell my master. But truly those
he loves are favoured by the gods, for the birds and the beasts that
are their children have helped me in my search——'
And there he broke off, for they had leapt over the last nullah that
separated them from the clearing and the hermit's hut; and the
moon having risen and floating freely overhead, Tom saw, as Bâl
Narîn had seen before him, the little enclosure of dried twigs and
leaves; but within there was darkness, and no one was moving to
and fro.
CHAPTER XLI
WHAT THE MORNING BROUGHT
How Tom lived through the next few moments he never knew. The
next thing of which he was distinctly conscious was standing in front
of the hut and looking within and seeing nothing but blackness. As
he groped forward with arms extended blindly, Bâl Narîn, who had
been busy kindling another torch, came up behind him, and the
flashing light flamed suddenly upon a spectacle that made Tom's
heart stand still, and brought a wild cry to his lips.
There were three figures in the small enclosure. On one side, rigid in
death, lay the fearfully emaciated body of an old man. A couch of
dried grass was his bier, and his limbs were covered with the long
robe that he had worn in his lifetime. On the other side, the little
heap of grass on which he lay pressed close against the opposite
side of the hut, and as far as possible from that sight of fear, was a
child with golden hair, whose tiny face, thin and pinched with
suffering, bore upon its lips the tranquil smile of sleep, or her twin-

70. sister death. This in the flashing of an instant Tom saw. But it was
not this, for all its pitifulness, that brought the sick chill to his heart,
and that wrung from his lips that tortured cry. For he saw something
else. She was lying there—his love—his darling! On the damp floor,
but close beside the couch, and with arms outspread, as if her last
conscious effort had been spent in defending the child, she lay
before him motionless. She did not stir when Bâl Narîn's light fell
upon her. The cry of irrepressible anguish that had broken from Tom
brought from her pale lips no answering note of recognition. It was
as he had so often dreamed it would be. He had found her, indeed;
but she was dead—dead—dead!
For the space of an instant he paused. Love and a reverence that
almost slew him were waging war in his heart. He was sick with the
longing to raise her in his arms, and press her against his breast,
and breathe into her lips of his own life and energy, and he dared
not.
In that instant Bâl Narîn looked over his shoulder. 'Quick, master,
quick!' he cried. 'They are not dead. This is the shock of a great joy.
A few moments ago the gracious lady was speaking to me. Bring her
out under the moonlight. And here are my chuddah and girdle to
make her a bed. You have the cordial?'
'Yes, Billy; I have the cordial. Thank God that I remembered it. So!'
as he lifted up the light form in his arms; 'gently! gently! Take away
the torch, Billy. Let there be nothing to frighten her when she
awakes! And the child, poor little Kit! bring him out—let him be near
her! God! how light she is! My sweet one! my love! how you must
have suffered! But it is all over now!' He laid her down reverently on
the couch that Bâl Narîn had prepared, and wet her lips with the
cordial. Then her eyelids fluttered, and a tremor ran through her
limbs, and her lips parted in a long, shuddering sigh that went
straight to Tom's heart. He was chafing one of her hands softly. 'My
poor love!' he whispered. 'Is it cruel to bring you back? Have you
suffered enough? But you shall never suffer again—never, so long as

71. I have life and strength to protect you. Will you not open your eyes
and look at me?'
Her lips parted, though her eyes were still sealed. He stooped over
her and caught one word—'Kit.'
'Kit is safe, darling. My good friend Billy is with him. Ah! I hear his
voice.'
Not his voice only. It was a little feeble laugh that came at that
moment from the door of the hut, for Kit, who was a proficient in
children's and bearers' Hindoostani, and Bâl Narîn were already on
the best of terms.
'Do you hear?' said Tom. 'Do you hear him, Grace?'
'Thank you,' she whispered.
Then her eyelids lifted, and her sweet eyes, deep with the passion of
pain and horror that, so long as she lived, would haunt her, rested
upon his. 'You are our Tom,' she said.
'I am Tom. Your Tom——'
'I have something to tell you. It is very strange—very horrible. I
don't quite understand it myself. Sometimes I think it is a dream;
but, if it were——'
'Dearest, you must tell me nothing now. See! You are exhausted.
You have suffered so much. And we are here now, Billy and I, to
look after your little Kit and you. Let me give you some of this
cordial—it is better than food—and then go to sleep and I will watch
over you, and in the morning, which is very near, dearest Grace, Billy
and I will carry you through the jungle to our camp.'
She did as he begged her. She was as weak as a little child, and the
feeling of security, absent from her for so many long days and
nights, was of itself enough to make her drowsy. But before she
settled herself to sleep, she opened her eyes once more.
'Rungya is in there,' she whispered. 'He died for Kit and me. You
won't let the wild birds have him?'

72. 'No; Bâl Narîn shall watch.'
'He killed two of the birds,' said Grace. 'They were watching for us. I
could not keep them away.'
And then her eyelids fell, and she slept peacefully until the morning.
Kit slept, too. He was in Bâl Narîn's arms, just as he had thrown
himself when he had eaten biscuit and tinned meat and drunk a
glass of cordial. The guide had, in the meantime, lighted a large fire,
which blazed and crackled, keeping effectually all the wild things
away. As he held the little one, and fed the fire with dried grass and
sticks, he and Tom were holding a council of war. Which would be
the best plan—to carry Grace and Kit between them to the spot
where they had left the men and waggons, or for Bâl Narîn to rush
thither at once and bring assistance?
Billy was for the latter alternative. He would take an hour to go, and
an hour to come back. By the time the sun was well up they could
start together.
But Tom, who, since the adventure of the previous evening, which
might have had so terrible a termination for himself, clung to his
Ghoorka guide as to a sheet-anchor of strength and hope, was of a
contrary opinion. 'Let us keep together, Billy,' he said. 'To-night we
have both escaped from almost certain death, and how can we
expect to escape a third time?'
'But, Sahib, consider——'
'I have considered. If there were ten bearers I should carry her
myself. And you, if you will, shall help me. How if we contrived a
litter——?'
'Out of our garments and those of the holy man,' said Bâl Narîn.
'He will not want them any more——'

73. 'We must burn him, Sahib. That is the burial for the Hindu-Saint.
Before we leave this place we will fire the hut.'
'Could we do it now, while they are sleeping?'
'I am afraid of the flame spreading, Sahib. With the first break of
day, I will set my torch to it, and we shall be far on our road before
it blazes high.'
Giving Kit over into Tom's arms. Bâl Narîn proceeded to make his
arrangements. Out of the hermit's robe and the rajah's upper
garment, and a long straight branch from the cotton-tree, he
devised such a litter as could be carried on the shoulders of two
men: then he took a parcel of dried twigs and grass into the hut,
scattered them over the old hermit's body, and anointed them with
oil. This done, he went outside again, cleared from the
neighbourhood of the hut everything of an inflammable nature, cut
two or three stout stakes from the cotton-tree, and hammered them
into the ground at a sufficient distance from the hut to allow of their
escaping from the fire that was presently to consume it.
'Rungya was a holy man,' he said, in explanation, 'and the time may
come when his friends and disciples will wish to do honour to his
ashes. We leave these stakes as a signal.' By the time all this was
done the light of the morning was beginning to peep in the east, and
the wild world of the jungle was sinking to rest.
'It is time for us to move,' said Bâl Narîn.
Tom looked down regretfully at Grace's sleeping face. 'Couldn't we
wait a little?' he said. 'It seems such a pity to disturb her.'
'We will not awake her,' said Bâl Narîn. 'Will his Excellency allow me?'
Tom moved aside while, with a dexterous gentleness which he
envied but could not emulate, the clever Ghoorka, who in his youth
had served an enforced apprenticeship to a robber tribe in the
plains, transferred the sleeping girl from her bed on the ground to
her bed on the litter.

74. Kit, in the meantime, had awoke. He was much stronger, he said,
though to Tom his poor little legs looked piteously weak and slender.
It was possible for him, however, to walk, and when he was tired Bâl
Narîn said he would carry him on his shoulder. Then a match was
applied to the touchwood under the hut; Grace, who had only stirred
once, was lifted slowly and carefully to the shoulders of her bearers,
and, with light hearts, they set out to rejoin the rest of their party on
the robbers' road.
The sleep which had fallen upon Grace when she knew that her task
was done, lasted for many hours. Passing through the air, resting for
brief spells when the shoulder of the rajah, which was
unaccustomed to weight-carrying, threatened to give way, taken up
again with reverent care, and lifted skilfully over the various
obstructions of the way, she neither moved nor spoke. Tom would,
now and then, look at her with alarm; but Bâl Narîn smiled.
'The gracious lady is a child of the Supreme Spirit,' he said, 'and this
is His sleep which has fallen upon her. When she awakes, Sahib, her
trouble will be gone.'
'Grace never slept,' said Kit, who was perched now on Bâl Narîn's
unoccupied shoulder, and holding on by his head, 'after Rungya
died.'
'How long was that, my little Sahib?' said Bâl Narîn.
'I don't remember,' said Kit wearily. 'A long time, I think. The big
birds came and frightened us. Grace had some candles and she
lighted them. I tried to keep awake; but I couldn't. She kept awake
always.'
'She is making up for it now,' said Tom from the other side of the
litter.

75. 'Yes, she is sleeping beautifully,' said Kit. 'She'll be all right when she
awakes, won't she?'
'All right? What do you mean, Kit?'
'She used to look so funny—just as if she were somewhere else. She
didn't look so at first, when that dreadful man was with us—but'—
pulling himself up, 'I mustn't say anything about that. I promised.'
'No,' said Tom. 'Grace will tell us everything herself when she
awakes.'
What the sleep was to her—how delicious it had been to close her
eyes, and to let herself drift away on the sea of unconsciousness
that, for these many days, had been wooing her; to half open her
eyelids just to be sure that she had not dreamed this strange and
sudden bliss, and then to close them again; to hear, without
understanding, Kit's bird-like voice throbbing through the air, and
Tom's grave, kind answers; to know that there was no need for her
to rouse herself, that she might sleep—sleep till the death-like
languor had gone from her limbs and the pain about her heart was
stilled—of the rapture of all this what tongue can tell? Only those
who have passed suddenly, as I did once, from peril and anguish,
and the mad terror of the hunted, to perfect rest and security, can
have the faintest idea of what it means.
It was impossible, meanwhile, that their progress could be swift, for
they could not tear straight through the jungle as they had done the
night before; and Bâl Narîn had to make many a detour to avoid the
wild beasts' haunts.
When the sun rose, he rigged up a leafy umbrella, which he fixed at
the head of the litter, and under it Grace lay like a sylvan queen
being borne in a trance to her woodland home. At last, after three
hours' steady tramp, they came out into the robbers' road, and
sighted their waggons and horses in the distance.
There had been much excitement in the camp. When they arose in
the morning, and Abiman, one of the Ghoorka soldiers, reported that
the rajah had left them shortly after moon-rise in search of Bâl

76. Narîn, and that neither of them had returned, it was felt that some
calamity must have happened.
'This is what comes of killing a serpent,' said Abiman to Purtab; and,
indeed, Purtab's conscience had already been reproaching him.
But when a swift-footed coolie, who had run back to see if anyone
was coming, rushed into camp with the joyful news that the rajah
and Bâl Narîn were on the road, and that they carried a litter
between them—then Purtab and Abiman changed places.
'The gods have won the day,' said Purtab seriously, 'and the demons
of the jungle may mourn.'
Everyone knew what to do, for the rajah had often prepared his
followers for this moment. In a trice the coolies dragged out and
rigged up the tent which was held in readiness, and the water-
carriers brought water from a neighbouring stream and heated it in
jars over the camp-fires, and the bearers unpacked the soft cushions
and fresh garments with which Gambier Singh had supplied Tom,
and laid them out temptingly, and toilet-appliances were hunted out
from their cases and set in order, so that before Grace, who had
been brought in and set down amongst them, had found strength to
open her eyes, her tent in the jungle was as well-served with all that
was needful for her refreshment and comfort as the room from
which she had fled when insurrection broke out in Nowgong. So
wonderful are Indian servants.
As for Tom, when he came in and looked round, he was so glad and
thankful that he would fain have scattered, then and there, rich
largesse amongst his people; and it was fortunate, perhaps, both for
himself and his guests, that he had nothing at that moment to
dispense but promises.
It was Kit who took Grace by the hand and led her into the tent, and
it was Kit who served her with the tea and biscuits which had been
prepared for her. They were together for a few minutes, and then he
came out, and dropped the curtain, and they saw that there was an
awed look on his little face.

77. 'She is somewhere else still,' he said to Tom; 'but I think if we don't
make any noise she will come back to us.'
'You are sure, Kit?' said Tom, in a broken voice.
'She always came back when she could sleep a little,' said Kit. 'Poor
old Rungya used to watch sometimes. Then he died. I will look, in
and see how she is presently,' he added, with an encouraging nod,
and then he went on to play the hero, and to be petted and tenderly
cared for by the Indian servants.
They happened to be in a comparatively wholesome region when
they halted, and it was decided, in the brief consultation which Tom
held with his followers, that they should remain where they were for
that day and part of the next night, starting for the Maharajah's
Road with the rising of the moon. Grace and Kit would have a cart to
travel in, so, although their progress would be slow, the fatigue
would not be great, and as there would be no need now for any of
those tentative flights into the open spots amongst the jungle that
made their former journey tedious, they would get over the ground
more quickly. Bâl Narîn calculated that in two or three days, at the
outside, they would reach the Maharajah's Road, at the point where
they left it. Here Tom hoped to pick up Hoosanee. It had been
arranged that if he found no trace of the fugitives on the lower
slopes of Sisagarhi, he should return to the point where the
cavalcade had divided, and wait there a certain specified time for his
master, after which time, should no news come, he would hasten
back to Gambier Singh, acquaint him with what had happened, and
ask his advice. It was almost certain now that the rajah and his
party would reach the meeting-point before the time agreed upon,
and Tom's only fear was that Hoosanee, who was so much of his
friend that he longed to let him know speedily his success and
happiness, would not be there so soon. But, in such case, a plan for
communicating with him could soon be devised.
After all this, having heard through Kit that Grace wanted nothing,
the rajah and Bâl Narîn gave themselves up to the rest which they
needed so sorely. The hours of the day rolled on. The sun rose high

78. in the heavens, and a deep noontide silence, unbroken by the noises
that at dead of night and early morning make the jungle terrible,
brooded over the camp. Everyone slept but the two or three who
remained on watch to keep the camp-fires burning.
It was in the midst of this silence that the English girl came slowly to
herself. Up to this she had been in a dream. All she had distinctly
realised was that she might rest—that the strain, which had tried her
to the utmost limit of endurance, was over. Now, as she opened her
eyes and, by the light that stole in through the canvas walls and
closed chicks, saw the curtains of rose and amber, and the pretty
camp-furniture, and the fresh garments, and the bowls of clear
water, she began dimly to understand that this was not a dream,
such as those that had visited her in her wanderings, but a reality.
The gates of the dear old life—the life of safety, and love, and
reverence—were opening to her once more. It was the horror she
and Kit had lived through that was the dream. This was true.
For the first few moments her mind was too weak to be able to take
in anything more than this: she was with her own people: she was
travelling back into the past: some day, if God was gracious to her,
she might see her mother and her sisters again: she might give up
her darling Kit to his friends. Then, gradually, as her mind grew
stronger, the events of the night, and of the days that had preceded
it, shaped themselves before her.
They had been on their way to Nepaul. The good Rungya, who had
rescued them one night from a horde of brutal villagers, had
promised to take them thither, and place them under the protection
of the minister, Jung Bahadoor. They had crossed the plains and
entered one of the great sâal-forests of the Terai together. Then
their cart broke down, and the animals sickened, and word came to
them that a party of fugitive sepoys, who had taken up robbery as a
profession, were haunting the great highway. So they turned aside,
walking painfully on foot through the jungle, till they reached the
Aswalia village. They had scarcely left it before Kit sickened with the
fever. They carried him on between them, hoping to reach opener