Search for: All records

A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph. 

Let $$x,y\in (0,1]$$, and let $A,B,C$ be disjoint nonempty stable subsets of a graph $$G$$, where every vertex in $$A$$ has at least $x|B|$ neighbours in $$B$$, and every vertex in $$B$$ has at least $y|C|$ neighbours in $$C$$, and there are no edges between $A,C$. We denote by $$\phi(x,y)$$ the maximum $$z$$ such that, in all such graphs $$G$$, there is a vertex $$v\in C$$ that is joined to at least $z|A|$ vertices in $$A$$ by two-edge paths. This function has some interesting properties: we show, for instance, that $$\phi(x,y)=\phi(y,x)$$ for all $x,y$, and there is a discontinuity in $$\phi(x,x)$$ when $1/x$ is an integer. For $z=1/2, 2/3,1/3,3/4,2/5,3/5$, we try to find the (complicated) boundary between the set of pairs $(x,y)$ with $$\phi(x,y)\ge z$$ and the pairs with $$\phi(x,y)1/3$. 

Abstract A family of vectors in [ k ] n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [ k ] n invariant under a transitive group of symmetries is o ( k n ), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets.