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.
more »
« less
On Weak Flexibility in Planar Graphs
Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable.
more »
« less
- Award ID(s):
- 1855653
- NSF-PAR ID:
- 10382200
- Date Published:
- Journal Name:
- Graphs and Combinatorics
- Volume:
- 38
- Issue:
- 6
- ISSN:
- 0911-0119
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $ \Sigma $ of genus $ g$ and let $ L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $ \phi $ with domain $ V(G)$ such that $ \phi (v)\in L(v)$ for every $ v\in V(G)$ and $ \phi (v)\ne \phi (u)$ for every pair of adjacent vertices $ u,v\in V(G)$. We prove if every non-null-homotopic cycle in $ G$ has length $ \Omega (\log g)$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $ \vert V(G)\vert=O(g)$, if every non-null-homotopic cycle in $ G$ has length $ \Omega (g)$, and a set $ X\subseteq V(G)$ of vertices that are pairwise at distance $ \Omega (1)$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $ \Omega (g)$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $ \Omega (1)$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $ 2^{\Omega (\vert V(G)\vert)}$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities.more » « less
-
Abstract This paper studies the structure and stability of boundaries in noncollapsed $${{\,\mathrm{RCD}\,}}(K,N)$$ RCD ( K , N ) spaces, that is, metric-measure spaces $$(X,{\mathsf {d}},{\mathscr {H}}^N)$$ ( X , d , H N ) with Ricci curvature bounded below. Our main structural result is that the boundary $$\partial X$$ ∂ X is homeomorphic to a manifold away from a set of codimension 2, and is $$N-1$$ N - 1 rectifiable. Along the way, we show effective measure bounds on the boundary and its tubular neighborhoods. These results are new even for Gromov–Hausdorff limits $$(M_i^N,{\mathsf {d}}_{g_i},p_i) \rightarrow (X,{\mathsf {d}},p)$$ ( M i N , d g i , p i ) → ( X , d , p ) of smooth manifolds with boundary, and require new techniques beyond those needed to prove the analogous statements for the regular set, in particular when it comes to the manifold structure of the boundary $$\partial X$$ ∂ X . The key local result is an $$\varepsilon $$ ε -regularity theorem, which tells us that if a ball $$B_{2}(p)\subset X$$ B 2 ( p ) ⊂ X is sufficiently close to a half space $$B_{2}(0)\subset {\mathbb {R}}^N_+$$ B 2 ( 0 ) ⊂ R + N in the Gromov–Hausdorff sense, then $$B_1(p)$$ B 1 ( p ) is biHölder to an open set of $${\mathbb {R}}^N_+$$ R + N . In particular, $$\partial X$$ ∂ X is itself homeomorphic to $$B_1(0^{N-1})$$ B 1 ( 0 N - 1 ) near $$B_1(p)$$ B 1 ( p ) . Further, the boundary $$\partial X$$ ∂ X is $$N-1$$ N - 1 rectifiable and the boundary measure "Equation missing" is Ahlfors regular on $$B_1(p)$$ B 1 ( p ) with volume close to the Euclidean volume. Our second collection of results involve the stability of the boundary with respect to noncollapsed mGH convergence $$X_i\rightarrow X$$ X i → X . Specifically, we show a boundary volume convergence which tells us that the $$N-1$$ N - 1 Hausdorff measures on the boundaries converge "Equation missing" to the limit Hausdorff measure on $$\partial X$$ ∂ X . We will see that a consequence of this is that if the $$X_i$$ X i are boundary free then so is X .more » « less
-
null (Ed.)Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k, s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with |ni−n/k|≤s , each of which induces a connected subgraph (when s=0 , the k parts are perfectly balanced, and we call it k-BCP for short). A recombination is an operation that takes a (k, s)-BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s≥0 , we wish to determine whether there exists a sequence of recombinations that transform A into B via (k, s)-BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k , and (3) we provide negative instances for s≤n/(3k) . (4) We show that the problem is PSPACE-complete when k∈O(nε) and s∈O(n1−ε) , for any constant 0<ε≤1 , even for restricted settings such as when G is an edge-maximal planar graph or when k≥3 and G is planar.more » « less
-
null (Ed.)Abstract We show how to construct a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner over a set $${P}$$ P of n points in $${\mathbb {R}}^d$$ R d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $${\vartheta },\varepsilon \in (0,1)$$ ϑ , ε ∈ ( 0 , 1 ) , the computed spanner $${G}$$ G has $$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$ O ( ε - O ( d ) ϑ - 6 n ( log log n ) 6 log n ) edges. Furthermore, for any k , and any deleted set $${{B}}\subseteq {P}$$ B ⊆ P of k points, the residual graph $${G}\setminus {{B}}$$ G \ B is a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner for all the points of $${P}$$ P except for $$(1+{\vartheta })k$$ ( 1 + ϑ ) k of them. No previous constructions, beyond the trivial clique with $${{\mathcal {O}}}(n^2)$$ O ( n 2 ) edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, $$\vartheta |B|$$ ϑ | B | , lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s00373-022-02564-1
