Béla Bollobás

  • University of Cambridge, UK

According to our database1, Béla Bollobás authored at least 292 papers between 1973 and 2021.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


Counting independent sets in regular hypergraphs.
J. Comb. Theory, Ser. A, 2021

Nucleation and growth in two dimensions.
Random Struct. Algorithms, 2020

Dense subgraphs in random graphs.
Discret. Appl. Math., 2019

Counting dense connected hypergraphs via the probabilistic method.
Random Struct. Algorithms, 2018

Line percolation.
Random Struct. Algorithms, 2018

Eigenvalues of subgraphs of the cube.
Eur. J. Comb., 2018

Longest common extension.
Eur. J. Comb., 2018

Comb. Probab. Comput., 2018

Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers).
Proceedings of the 29th International Conference on Probabilistic, 2018

Exploring hypergraphs with martingales.
Random Struct. Algorithms, 2017

Packing random graphs and hypergraphs.
Random Struct. Algorithms, 2017

Catching a fast robber on the grid.
J. Comb. Theory, Ser. A, 2017

Jigsaw percolation on random hypergraphs.
J. Appl. Probab., 2017

Sentry selection in sensor networks: theory and algorithms.
Int. J. Sens. Networks, 2017

The Threshold for Jigsaw Percolation on Random Graphs.
Electron. J. Comb., 2017

On the Maximum Running Time in Graph Bootstrap Percolation.
Electron. J. Comb., 2017

Random Hypergraph Irregularity.
SIAM J. Discret. Math., 2016

Barrier Coverage.
Random Struct. Algorithms, 2016

On the stability of the Erdős-Ko-Rado theorem.
J. Comb. Theory, Ser. A, 2016

Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs.
Eur. J. Comb., 2016

Counting Connected Hypergraphs via the Probabilistic Method.
Comb. Probab. Comput., 2016

Catching a fast robber on the grid.
CoRR, 2016

The time of bootstrap percolation with dense initial sets for all thresholds.
Random Struct. Algorithms, 2015

Intersections of hypergraphs.
J. Comb. Theory, Ser. B, 2015

An old approach to the giant component problem.
J. Comb. Theory, Ser. B, 2015

Intersections of random hypergraphs and tournaments.
Eur. J. Comb., 2015

Disjoint induced subgraphs of the same order and size.
Eur. J. Comb., 2015

Monotone Cellular Automata in a Random Environment.
Comb. Probab. Comput., 2015

Partial Shadows of Set Systems.
Comb. Probab. Comput., 2015

Interference percolation.
Random Struct. Algorithms, 2014

A coding problem for pairs of subsets.
Proceedings of the Geometry, Structure and Randomness in Combinatorics, 2014

Cover-Decomposition and Polychromatic Numbers.
SIAM J. Discret. Math., 2013

Repeated Degrees in Random Uniform Hypergraphs.
SIAM J. Discret. Math., 2013

A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton's method.
Math. Comput., 2013

Cops and robbers in a random graph.
J. Comb. Theory, Ser. B, 2013

Union-closed families of sets.
J. Comb. Theory, Ser. A, 2013

Metric Dimension for Random Graphs.
Electron. J. Comb., 2013

Hereditary and Monotone Properties of Graphs.
Proceedings of the Mathematics of Paul Erdős II, 2013

The Dimension of Random Graph Orders.
Proceedings of the Mathematics of Paul Erdős II, 2013

Paul Erdős: Life and Work.
Proceedings of the Mathematics of Paul Erdős I, 2013

Turán Densities of Some Hypergraphs Related to K<sub>k+1</sub><sup>k</sup>.
SIAM J. Discret. Math., 2012

Asymptotic normality of the size of the giant component in a random hypergraph.
Random Struct. Algorithms, 2012

Graph bootstrap percolation.
Random Struct. Algorithms, 2012

Walks and paths in trees.
J. Graph Theory, 2012

Asymptotic normality of the size of the giant component via a random walk.
J. Comb. Theory, Ser. B, 2012

Linear algebra and bootstrap percolation.
J. Comb. Theory, Ser. A, 2012

Monotone Graph Limits and Quasimonotone Graphs.
Internet Math., 2012

Degree Powers in Graphs: The Erdős-Stone Theorem.
Comb. Probab. Comput., 2012

Critical Probabilities of 1-Independent Percolation Models.
Comb. Probab. Comput., 2012

A Simple Branching Process Approach to the Phase Transition in G<sub>n, p</sub>.
Electron. J. Comb., 2012

Projections, entropy and sumsets.
Comb., 2012

Sparse graphs: Metrics and random models.
Random Struct. Algorithms, 2011

Sparse random graphs with clustering.
Random Struct. Algorithms, 2011

On covering by translates of a set.
Random Struct. Algorithms, 2011

Intersections of graphs.
J. Graph Theory, 2011

Shadows of ordered graphs.
J. Comb. Theory, Ser. A, 2011

The fine structure of octahedron-free graphs.
J. Comb. Theory, Ser. B, 2011

The structure of almost all graphs in a hereditary property.
J. Comb. Theory, Ser. B, 2011

Large joints in graphs.
Eur. J. Comb., 2011

Daisies and Other Turán Problems.
Comb. Probab. Comput., 2011

Multi-path Routing Metrics for Reliable Wireless Mesh Routing Topologies
CoRR, 2011

Energy-latency tradeoff for in-network function computation in random networks.
Proceedings of the INFOCOM 2011. 30th IEEE International Conference on Computer Communications, 2011

Random Graphs, Second Edition
Cambridge Studies in Advanced Mathematics 73, Cambridge University Press, ISBN: 978-0-51181406-8, 2011

Random majority percolation.
Random Struct. Algorithms, 2010

Bond percolation with attenuation in high dimensional Voronoi tilings.
Random Struct. Algorithms, 2010

The number of graphs with large forbidden subgraphs.
Eur. J. Comb., 2010

Max k-cut and judicious k-partitions.
Discret. Math., 2010

Bootstrap Percolation in High Dimensions.
Comb. Probab. Comput., 2010

Clique percolation.
Random Struct. Algorithms, 2009

The typical structure of graphs without given excluded subgraphs.
Random Struct. Algorithms, 2009

The unlabelled speed of a hereditary graph property.
J. Comb. Theory, Ser. B, 2009

Highly connected random geometric graphs.
Discret. Appl. Math., 2009

Line-of-Sight Percolation.
Comb. Probab. Comput., 2009

Majority Bootstrap Percolation on the Hypercube.
Comb. Probab. Comput., 2009

Comb. Probab. Comput., 2009

The distribution of the root degree of a random permutation.
Comb., 2009

Sequences with Changing Dependencies.
SIAM J. Discret. Math., 2008

Percolation on dual lattices with <i>k</i>-fold symmetry.
Random Struct. Algorithms, 2008

Packing d-degenerate graphs.
J. Comb. Theory, Ser. B, 2008

Connectivity of addable graph classes.
J. Comb. Theory, Ser. B, 2008

Connectivity of a Gaussian network.
Int. J. Ad Hoc Ubiquitous Comput., 2008

Graphs and Hermitian matrices: Exact interlacing.
Discret. Math., 2008

Joints in graphs.
Discret. Math., 2008

Pentagons vs. triangles.
Discret. Math., 2008

Highly connected monochromatic subgraphs.
Discret. Math., 2008

Eliminating Cycles in the Discrete Torus.
Algorithmica, 2008

Degree distribution of the FKP network model.
Theor. Comput. Sci., 2007

Spread-out percolation in R<sup>d</sup>.
Random Struct. Algorithms, 2007

The phase transition in inhomogeneous random graphs.
Random Struct. Algorithms, 2007

Hereditary properties of combinatorial structures: Posets and oriented graphs.
J. Graph Theory, 2007

The generalized Randic index of trees.
J. Graph Theory, 2007

Maximum directed cuts in acyclic digraphs.
J. Graph Theory, 2007

Separating systems and oriented graphs of diameter two.
J. Comb. Theory, Ser. B, 2007

Cliques and the spectral radius.
J. Comb. Theory, Ser. B, 2007

On separating systems.
Eur. J. Comb., 2007

A note on the Harris-Kesten Theorem.
Eur. J. Comb., 2007

Hereditary Properties of Tournaments.
Electron. J. Comb., 2007

Reliable density estimates for coverage and connectivity in thin strips of finite length.
Proceedings of the 13th Annual International Conference on Mobile Computing and Networking, 2007

Proving Integrality Gaps without Knowing the Linear Program.
Theory Comput., 2006

Sharp thresholds and percolation in the plane.
Random Struct. Algorithms, 2006

Regular subgraphs of random graphs.
Random Struct. Algorithms, 2006

Large deviations for mean field models of probabilistic cellular automata.
Random Struct. Algorithms, 2006

How many graphs are unions of <i>k</i>-cliques?
J. Graph Theory, 2006

The Angel and the Devil in three dimensions.
J. Comb. Theory, Ser. A, 2006

Ramsey-type theorems for metric spaces with applications to online problems.
J. Comput. Syst. Sci., 2006

Hereditary properties of partitions, ordered graphs and ordered hypergraphs.
Eur. J. Comb., 2006

Pair dominating graphs.
Eur. J. Comb., 2006

Set colourings of graphs.
Discret. Math., 2006

The Art of Mathematics - Coffee Time in Memphis.
Cambridge University Press, ISBN: 978-0-521-69395-0, 2006

Cambridge University Press, ISBN: 978-0-521-87232-4, 2006

Sparse Distance Preservers and Additive Spanners.
SIAM J. Discret. Math., 2005

Slow emergence of the giant component in the growing <i>m</i>-out graph.
Random Struct. Algorithms, 2005

The phase transition in the uniformly grown random graph has infinite order.
Random Struct. Algorithms, 2005

Continuum percolation with steps in the square or the disc.
Random Struct. Algorithms, 2005

Percolation in Voronoi tilings.
Random Struct. Algorithms, 2005

A jump to the bell number for hereditary graph properties.
J. Comb. Theory, Ser. B, 2005

Hereditary properties of words.
RAIRO Theor. Informatics Appl., 2005

Integer sets with prescribed pairwise differences being distinct.
Eur. J. Comb., 2005

Books in graphs.
Eur. J. Comb., 2005

The Sum of Degrees in Cliques.
Electron. J. Comb., 2005

Unavoidable Traces Of Set Systems.
Comb., 2005

Phase transitions in the neuropercolation model of neural populations with mixed local and non-local interactions.
Biol. Cybern., 2005

Judicious partitions of bounded-degree graphs.
J. Graph Theory, 2004

Multicoloured extremal problems.
J. Comb. Theory, Ser. A, 2004

The number of graphs without forbidden subgraphs.
J. Comb. Theory, Ser. B, 2004

The interlace polynomial of a graph.
J. Comb. Theory, Ser. B, 2004

Graphs and Hermitian matrices: eigenvalue interlacing.
Discret. Math., 2004

Hermitian matrices and graphs: singular values and discrepancy.
Discret. Math., 2004

Max Cut for Random Graphs with a Planted Partition.
Comb. Probab. Comput., 2004

Isoperimetric Problems for r-sets.
Comb. Probab. Comput., 2004

How Sharp is the Concentration of the Chromatic Number?
Comb. Probab. Comput., 2004

Degree Powers in Graphs with Forbidden Subgraphs.
Electron. J. Comb., 2004

The Diameter of a Scale-Free Random Graph.
Comb., 2004

On the Value of a Random Minimum Weight Steiner Tree.
Comb., 2004

A Two-Variable Interlace Polynomial.
Comb., 2004

The Phase Transition and Connectedness in Uniformly Grown Random Graphs.
Proceedings of the Algorithms and Models for the Web-Graph: Third International Workshop, 2004

Fast transmission in ad hoc networks.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Neuropercolation: A Random Cellular Automata Approach to Spatio-temporal Neurodynamics.
Proceedings of the Cellular Automata, 2004

Union of shadows.
Theor. Comput. Sci., 2003

The number of k-SAT functions.
Random Struct. Algorithms, 2003

Disjointly representing set systems.
J. Comb. Theory, Ser. A, 2003

Graphs with large maximum degree containing no odd cycles of a given length.
J. Comb. Theory, Ser. B, 2003

Maximum cuts and judicious partitions in graphs without short cycles.
J. Comb. Theory, Ser. B, 2003

Coupling Scale-Free and Classical Random Graphs.
Internet Math., 2003

Robustness and Vulnerability of Scale-Free Random Graphs.
Internet Math., 2003

Paths of length four.
Discret. Math., 2003

The Oberwolfach Meeting On Combinatorics, Probability And Computing.
Comb. Probab. Comput., 2003

Frank Ramsey.
Comb. Probab. Comput., 2003

Special Issue on Ramsey Theory.
Comb. Probab. Comput., 2003

Set Systems with few Disjoint Pairs.
Comb., 2003

Directed scale-free graphs.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Analytic Graph Theory.
Proceedings of the Handbook of Graph Theory., 2003

Problems and results on judicious partitions.
Random Struct. Algorithms, 2002

Girth of sparse graphs.
J. Graph Theory, 2002

Evaluations of the Circuit Partition Polynomial.
J. Comb. Theory, Ser. B, 2002

The Interlace Polynomial of Graphs at - 1.
Eur. J. Comb., 2002

Random induced graphs.
Discret. Math., 2002

Vertex distinguishing colorings of graphs with Delta(G)=2.
Discret. Math., 2002

Game domination number.
Discret. Math., 2002

Measures on monotone properties of graphs.
Discret. Appl. Math., 2002

Proving Integrality Gaps without Knowing the Linear Program.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Modern Graph Theory.
Graduate Texts in Mathematics 184, Springer, ISBN: 978-1-4612-0619-4, 2002

The degree sequence of a scale-free random graph process.
Random Struct. Algorithms, 2001

The scaling window of the 2-SAT transition.
Random Struct. Algorithms, 2001

Time-Series Similarity Problems and Well-Separated Geometric Sets.
Nord. J. Comput., 2001

Ramsey minimal graphs.
J. Braz. Comput. Soc., 2001

The Penultimate Rate of Growth for Graph Properties.
Eur. J. Comb., 2001

Alternating Knot Diagrams, Euler Circuits and the Interlace Polynomial.
Eur. J. Comb., 2001

A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least <i>k</i>.
J. Graph Theory, 2000

Contraction-Deletion Invariants for Graphs.
J. Comb. Theory, Ser. B, 2000

Local and Mean Ramsey Numbers for Trees.
J. Comb. Theory, Ser. B, 2000

The Speed of Hereditary Properties of Graphs.
J. Comb. Theory, Ser. B, 2000

Judicious Partitions of 3-uniform Hypergraphs.
Eur. J. Comb., 2000

A note on generalized chromatic number and generalized girth.
Discret. Math., 2000

Polychromatic polynomials.
Discret. Math., 2000

Euler circuits and DNA sequencing by hybridization.
Discret. Appl. Math., 2000

Constrained Graph Processes.
Electron. J. Comb., 2000

The Structure of Hereditary Properties and Colourings of Random Graphs.
Comb., 2000

On a conjecture involving cycle-complete graph Ramsey numbers.
Australas. J Comb., 2000

The interlace polynomial: a new graph polynomial.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Counting Boundary Paths for Oriented Percolation Clusters.
Random Struct. Algorithms, 1999

Weakly Pancyclic Graphs.
J. Comb. Theory, Ser. B, 1999

Turán's Theorem and Maximal Degrees.
J. Comb. Theory, Ser. B, 1999

Geometrical Techniques for Estimating Numbers of Linear Extensions.
Eur. J. Comb., 1999

Closure and Hamiltonian-connectivity of claw-free graphs.
Discret. Math., 1999

Extremal graphs for weights.
Discret. Math., 1999

Exact Bounds for Judicious Partitions of Graphs.
Comb., 1999

Colorings generated by monotone properties.
Random Struct. Algorithms, 1998

Paul Erdös and probability theory.
Random Struct. Algorithms, 1998

Proof of a Conjecture of Mader, Erdös and Hajnal on Topological Complete Subgraphs.
Eur. J. Comb., 1998

The oriented cycle game.
Discret. Math., 1998

On some conjectures of Graffiti.
Discret. Math., 1998

Graphs of Extremal Weights.
Ars Comb., 1998

The Structure of Random Graph Orders.
SIAM J. Discret. Math., 1997

On the girth of hamiltonian weakly pancyclic graphs.
J. Graph Theory, 1997

Judicious Partitions of Hypergraphs.
J. Comb. Theory, Ser. A, 1997

Independent sets and repeated degrees.
Discret. Math., 1997

On a problem of Erdös and Graham.
Discret. Math., 1997

Matchings and Paths in the Cube.
Discret. Appl. Math., 1997

Random Walks and Electrical Resistances in Products of Graphs.
Discret. Appl. Math., 1997

A Proof of a Conjecture of Bondy Concerning Paths in Weighted Digraphs.
J. Comb. Theory, Ser. B, 1996

On the Best Case of Heapsort.
J. Algorithms, 1996

Sums in the grid.
Discret. Math., 1996

Degree multiplicities and independent sets in K<sub>4</sub>-free graphs.
Discret. Math., 1996

Turán-Ramsey problems.
Discret. Math., 1996

Highly Linked Graphs.
Comb., 1996

Generalized Chromatic Numbers of Random Graphs.
Random Struct. Algorithms, 1995

Connectivity Properties of Random Subgraphs of the Cube.
Random Struct. Algorithms, 1995

Defect Sauer Results.
J. Comb. Theory, Ser. A, 1995

The maximal number of induced<i>r</i>-partite subgraphs.
Graphs Comb., 1995

On the Diameter and Radius of Random Subgraphs of the Cube.
Random Struct. Algorithms, 1994

Improved Upper Bounds for the Critical Probability of Oriented Percolation in Two Dimensions.
Random Struct. Algorithms, 1994

Percolation in High Dimensions.
Eur. J. Comb., 1994

An Extension of the Erdös-Stone Theorem.
Comb., 1994

Probabilistic Analysis of Disjoint Set Union Algorithms.
SIAM J. Comput., 1993

Maximal sets of given diameter in the grid and the torus.
Discret. Math., 1993

Clique coverings of the edges of a random graph.
Comb., 1993

Cycles through specified vertices.
Comb., 1993

The Evaluation of Random Subgraphs of the Cube.
Random Struct. Algorithms, 1992

A travelling salesman problem in the k-dimensional unit cube.
Oper. Res. Lett., 1992

Spanning Maximal Planar Subgraphs of Random Graphs.
Random Struct. Algorithms, 1991

Isoperimetric inequalities and fractional set systems.
J. Comb. Theory, Ser. A, 1991

Compressions and isoperimetric inequalities.
J. Comb. Theory, Ser. A, 1991

Graphs without large triangle free subgraphs.
Discret. Math., 1991

Edge-isoperimetric inequalities in the grid.
Comb., 1991

An extremal function for the achromatic number.
Proceedings of the Graph Structure Theory, 1991

The Cost Distribution of Clustering in Random Probing
J. ACM, April, 1990

An Isoperimetric Inequality on the Discrete Torus.
SIAM J. Discret. Math., 1990

Parallel Selection with High Probability.
SIAM J. Discret. Math., 1990

Complete Matchings in Random Subgraphs on the Cube.
Random Struct. Algorithms, 1990

Almost every graph has reconstruction number three.
J. Graph Theory, 1990

Powers of Hamilton cycles in tournaments.
J. Comb. Theory, Ser. B, 1990

Isoperimetric Inequalities for Faces of the Cube and the Grid.
Eur. J. Comb., 1990

Exact Face-isoperimetric Inequalities.
Eur. J. Comb., 1990

On generalised minimal domination parameters for paths.
Discret. Math., 1990

First cycles in random directed graph processes.
Discret. Math., 1989

A new upper bound for the list chromatic number.
Discret. Math., 1989

Long cycles in graphs with no subgraphs of minimal degree 3.
Discret. Math., 1989

Paul Erdös at seventy-five.
Discret. Math., 1989

Graphs with a small number of distinct induced subgraphs.
Discret. Math., 1989

The Diameter of a Cycle Plus a Random Matching.
SIAM J. Discret. Math., 1988

Transitive Orientations of Graphs.
SIAM J. Comput., 1988

The number of unrelated partitions.
J. Comb. Theory, Ser. A, 1988

The Isoperimetric Number of Random Regular Graphs.
Eur. J. Comb., 1988

Sorting in rounds.
Discret. Math., 1988

The chromatic number of random graphs.
Comb., 1988

Threshold functions.
Comb., 1987

An algorithm for finding Hamilton cycles in a random graph.
Comb., 1987

The number of matchings in random regular graphs and bipartite graphs.
J. Comb. Theory, Ser. B, 1986

The maximal number of induced complete bipartite graphs.
Discret. Math., 1986

Extremal graph theory with emphasis on probabilistic methods.
CBMS-NSF regional conference series in applied mathematics 62, American Mathematical Society, ISBN: 978-0-8218-0712-5, 1986

Regular factors of regular graphs.
J. Graph Theory, 1985

Repeated Random Insertion into a Priority Queue.
J. Algorithms, 1985

List-colourings of graphs.
Graphs Comb., 1985

On the Expected Behaviour of Disjoint Set Union Algorithms
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Rotation numbers for unions of circuits.
J. Graph Theory, 1984

The irredundance number and maximum degree of a graph.
Discret. Math., 1984

Diameters of random bipartite graphs.
Comb., 1984

On 4-cycles in random bipartite tournaments.
J. Graph Theory, 1983

Equitable and proportional coloring of trees.
J. Comb. Theory, Ser. B, 1983

Almost all Regular Graphs are Hamiltonian.
Eur. J. Comb., 1983

Some remarks on packing trees.
Discret. Math., 1983

Parallel sorting.
Discret. Appl. Math., 1983

More rotation numbers for complete bipartite graphs.
J. Graph Theory, 1982

Vertices of given degree in a random graph.
J. Graph Theory, 1982

The diameter of random regular graphs.
Comb., 1982

Long paths in sparse random graphs.
Comb., 1982

The size of connected hypergraphs with prescribed covering number.
J. Comb. Theory, Ser. B, 1981

Dense neighbourhoods and Turán's theorem.
J. Comb. Theory, Ser. B, 1981

Indestructive deletions of edges from graphs.
J. Comb. Theory, Ser. B, 1981

Topological cliques of random graphs.
J. Comb. Theory, Ser. B, 1981

Graphs which Contain all Small Graphs.
Eur. J. Comb., 1981

Degree sequences of random graphs.
Discret. Math., 1981

Hadwiger's Conjecture is True for Almost Every Graph.
Eur. J. Comb., 1980

A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs.
Eur. J. Comb., 1980

The distribution of the maximum degree of a random graph.
Discret. Math., 1980

Graph-theoretic parameters concerning domination, independence, and irredundance.
J. Graph Theory, 1979

Helly Families of Maximal Size.
J. Comb. Theory, Ser. A, 1979

On graphs with equal edge connectivity and minimum degree.
Discret. Math., 1979

Packings of graphs and applications to computational complexity.
J. Comb. Theory, Ser. B, 1978

The number of 1-factors in 2k-connected graphs.
J. Comb. Theory, Ser. B, 1978

Uniquely colorable graphs.
J. Comb. Theory, Ser. B, 1978

Chromatic number, girth and maximal degree.
Discret. Math., 1978

Extremal problems in graph theory.
J. Graph Theory, 1977

Semi-topological subgraphs.
Discret. Math., 1977

On graphs with diameter 2.
J. Comb. Theory, Ser. B, 1976

On a Ramsey-Turán type problem.
J. Comb. Theory, Ser. B, 1976

Complete subgraphs are elusive.
J. Comb. Theory, Ser. B, 1976

On complete subgraphs of r-chromatic graphs.
Discret. Math., 1975

Three-graphs without two triples whose symmetric difference is contained in a third.
Discret. Math., 1974

Sperner Systems Consisting of Pairs of Complementary Subsets.
J. Comb. Theory, Ser. A, 1973