An official website of the United States government
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
Shortest paths in arbitrary plane domains
Abstract Let $$\Omega $$ be a connected open set in the plane and $$\gamma : [0,1] \to \overline {\Omega }$$ a path such that $$\gamma ((0,1)) \subset \Omega $$ . We show that the path $$\gamma $$ can be “pulled tight” to a unique shortest path which is homotopic to $$\gamma $$ , via a homotopy h with endpoints fixed whose intermediate paths $$h_t$$ , for $$t \in [0,1)$$ , satisfy $$h_t((0,1)) \subset \Omega $$ . We prove this result even in the case when there is no path of finite Euclidean length homotopic to $$\gamma $$ under such a homotopy. For this purpose, we offer three other natural, equivalent notions of a “shortest” path. This work generalizes previous results for simply connected domains with simple closed curve boundaries.
more »
« less
- Award ID(s):
- 1807558
- PAR ID:
- 10348024
- Date Published:
- Journal Name:
- Canadian Journal of Mathematics
- Volume:
- 74
- Issue:
- 2
- ISSN:
- 0008-414X
- Page Range / eLocation ID:
- 349 to 367
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $$\Gamma$$ of the given semi-algebraic set $$S$$, such that $$\HH_q(S,\Gamma) = 0$$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $$X$$ of dimension $$n$$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with $$\dim_\C Z^{(i)} \leq i$, and $$\HH_q(X,Z^{(i)}) = 0$$ for $$0 \leq q \leq i$$. We conjecture a quantitative version of this result in the semi-algebraic category, with $$X$$ and $$Z^{(i)}$$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $$Z^{(0)}$$ and $$Z^{(1)}$$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $$Z^{(0)}$$).more » « less
-
We can view the Lipschitz constant as a height function on the space of maps between two manifolds and ask (as Gromov did nearly 30 years ago) what its ``Morse landscape'' looks like: are there high peaks, deep valleys and mountain passes? A simple and relatively well-studied version of this question: given two points in the same component (homotopic maps), does a path between them (a homotopy) have to pass through maps of much higher Lipschitz constant? Now we also consider similar questions for higher-dimensional cycles in the space. We make this precise using the language of persistent homology and give some first results.more » « less
-
null (Ed.)Abstract We consider the 𝑑-dimensional Boussinesq system defined on a sufficiently smooth bounded domain and subject to a pair { v , u } \{v,\boldsymbol{u}\} of controls localized on { Γ ~ , ω } \{\widetilde{\Gamma},\omega\} .Here, 𝑣 is a scalar Dirichlet boundary control for the thermal equation, acting on an arbitrarily small connected portion Γ ~ \widetilde{\Gamma} of the boundary Γ = ∂ Ω \Gamma=\partial\Omega .Instead, 𝒖 is a 𝑑-dimensional internal control for the fluid equation acting on an arbitrarily small collar 𝜔 supported by Γ ~ \widetilde{\Gamma} .The initial conditions for both fluid and heat equations are taken of low regularity.We then seek to uniformly stabilize such Boussinesq system in the vicinity of an unstable equilibrium pair, in the critical setting of correspondingly low regularity spaces, by means of an explicitly constructed, finite-dimensional feedback control pair { v , u } \{v,\boldsymbol{u}\} localized on { Γ ~ , ω } \{\widetilde{\Gamma},\omega\} .In addition, they will be minimal in number and of reduced dimension; more precisely, 𝒖 will be of dimension ( d - 1 ) (d-1) , to include necessarily its 𝑑-th component, and 𝑣 will be of dimension 1.The resulting space of well-posedness and stabilization is a suitable, tight Besov space for the fluid velocity component (close to L 3 ( Ω ) \boldsymbol{L}^{3}(\Omega) for d = 3 d=3 ) and a corresponding Besov space for the thermal component, q > d q>d .Unique continuation inverse theorems for suitably over-determined adjoint static problems play a critical role in the constructive solution.Their proof rests on Carleman-type estimates, a topic pioneered by M. V. Klibanov since the early 80s.more » « less
-
Mulzer, Wolfgang; Phillips, Jeff M (Ed.)Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of ℝ² and let 𝒟 = {D_1,…,D_n} be a set of geodesic disks with respect to the metric d. We prove that 𝒢^×(𝒟), the intersection graph of the disks in 𝒟, has a clique-based separator consisting of O(n^{3/4+ε}) cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.4153/S0008414X20000784
