skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path
Abstract A graphGisH-freeif it has no induced subgraph isomorphic toH. We prove that a$$P_5$$ P 5 -free graph with clique number$$\omega \ge 3$$ ω 3 has chromatic number at most$$\omega ^{\log _2(\omega )}$$ ω log 2 ( ω ) . The best previous result was an exponential upper bound$$(5/27)3^{\omega }$$ ( 5 / 27 ) 3 ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for$$P_5$$ P 5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for$$P_5$$ P 5 -free graphs, and our result is an attempt to approach that.  more » « less
Award ID(s):
2154169
PAR ID:
10517553
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Link
Date Published:
Journal Name:
Combinatorica
Volume:
43
Issue:
5
ISSN:
0209-9683
Page Range / eLocation ID:
845 to 852
Subject(s) / Keyword(s):
Chromatic number, Induced subgraphs
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract In this paper we prove a higher dimensional analogue of Carleson’s$$\varepsilon ^{2}$$ ε 2 conjecture. Given two arbitrary disjoint Borel sets$$\Omega ^{+},\Omega ^{-}\subset \mathbb{R}^{n+1}$$ Ω + , Ω R n + 1 , and$$x\in \mathbb{R}^{n+1}$$ x R n + 1 ,$$r>0$$ r > 0 , we denote$$ \varepsilon _{n}(x,r) := \frac{1}{r^{n}}\, \inf _{H^{+}} \mathcal{H}^{n} \left ( ((\partial B(x,r)\cap H^{+}) \setminus \Omega ^{+}) \cup (( \partial B(x,r)\cap H^{-}) \setminus \Omega ^{-})\right ), $$ ε n ( x , r ) : = 1 r n inf H + H n ( ( ( B ( x , r ) H + ) Ω + ) ( ( B ( x , r ) H ) Ω ) ) , where the infimum is taken over all open affine half-spaces$$H^{+}$$ H + such that$$x \in \partial H^{+}$$ x H + and we define$$H^{-}= \mathbb{R}^{n+1} \setminus \overline{H^{+}}$$ H = R n + 1 H + . Our first main result asserts that the set of points$$x\in \mathbb{R}^{n+1}$$ x R n + 1 where$$ \int _{0}^{1} \varepsilon _{n}(x,r)^{2} \, \frac{dr}{r}< \infty $$ 0 1 ε n ( x , r ) 2 d r r < is$$n$$ n -rectifiable. For our second main result we assume that$$\Omega ^{+}$$ Ω + ,$$\Omega ^{-}$$ Ω are open and that$$\Omega ^{+}\cup \Omega ^{-}$$ Ω + Ω satisfies the capacity density condition. For each$$x \in \partial \Omega ^{+} \cup \partial \Omega ^{-}$$ x Ω + Ω and$$r>0$$ r > 0 , we denote by$$\alpha ^{\pm }(x,r)$$ α ± ( x , r ) the characteristic constant of the (spherical) open sets$$\Omega ^{\pm }\cap \partial B(x,r)$$ Ω ± B ( x , r ) . We show that, up to a set of$$\mathcal{H}^{n}$$ H n measure zero,$$x$$ x is a tangent point for both$$\partial \Omega ^{+}$$ Ω + and$$\partial \Omega ^{-}$$ Ω if and only if$$ \int _{0}^{1} \min (1,\alpha ^{+}(x,r) + \alpha ^{-}(x,r) -2) \frac{dr}{r} < \infty . $$ 0 1 min ( 1 , α + ( x , r ) + α ( x , r ) 2 ) d r r < . The first result is new even in the plane and the second one improves and extends to higher dimensions the$$\varepsilon ^{2}$$ ε 2 conjecture of Carleson. 
    more » « less
  2. Abstract We consider thed-dimensional MagnetoHydroDynamics (MHD) system defined on a sufficiently smooth bounded domain,$$d = 2,3$$ d = 2 , 3 with homogeneous boundary conditions, and subject to external sources assumed to cause instability. The initial conditions for both fluid and magnetic equations are taken of low regularity. We then seek to uniformly stabilize such MHD system in the vicinity of an unstable equilibrium pair, in the critical setting of correspondingly low regularity spaces, by means of explicitly constructed, static, feedback controls, which are localized on an arbitrarily small interior subdomain. In additional, they will be minimal in number. The resulting space of well-posedness and stabilization is a suitable product space$$\displaystyle \widetilde{\textbf{B}}^{2- ^{2}\!/_{p}}_{q,p}(\Omega )\times \widetilde{\textbf{B}}^{2- ^{2}\!/_{p}}_{q,p}(\Omega ), \, 1< p < \frac{2q}{2q-1}, \, q > d,$$ B ~ q , p 2 - 2 / p ( Ω ) × B ~ q , p 2 - 2 / p ( Ω ) , 1 < p < 2 q 2 q - 1 , q > d , of tight Besov spaces for the fluid velocity component and the magnetic field component (each “close” to$$\textbf{L}^3(\Omega )$$ L 3 ( Ω ) for$$d = 3$$ d = 3 ). Showing maximal$$L^p$$ L p -regularity up to$$T = \infty $$ T = for the feedback stabilized linear system is critical for the analysis of well-posedness and stabilization of the feedback nonlinear problem. 
    more » « less
  3. Abstract We prove that there are$$\gg \frac{X^{\frac{1}{3}}}{(\log X)^2}$$ X 1 3 ( log X ) 2 imaginary quadratic fieldskwith discriminant$$|d_k|\le X$$ | d k | X and an ideal class group of 5-rank at least 2. This improves a result of Byeon, who proved the lower bound$$\gg X^{\frac{1}{4}}$$ X 1 4 in the same setting. We use a method of Howe, Leprévost, and Poonen to construct a genus 2 curveCover$$\mathbb {Q}$$ Q such thatChas a rational Weierstrass point and the Jacobian ofChas a rational torsion subgroup of 5-rank 2. We deduce the main result from the existence of the curveCand a quantitative result of Kulkarni and the second author. 
    more » « less
  4. Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ [ 0 , 1 ] k where$$k \ge 2$$ k 2 . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ x 1 , x 2 , , x n through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ i = 1 n | x i - x i + 1 | k 1 / k c k , where$$|x-y|$$ | x - y | is the Euclidean distance betweenxandy, and$$c_k$$ c k is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ x n + 1 x 1 . From the other direction, for every$$k \ge 2$$ k 2 and$$n \ge 2$$ n 2 , there existnpoints in$$[0,1]^k$$ [ 0 , 1 ] k , such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · k . For the plane, the best constant is$$c_2=2$$ c 2 = 2 and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 9 2 3 1 / k · k for every$$k \ge 3$$ k 3 and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ c k = 2 1 / k · k , for every$$k \ge 2$$ k 2 . Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ c k = 3 5 2 3 1 / k · k or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ c k = 2.91 k ( 1 + o k ( 1 ) ) . Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ c 3 2 7 / 6 , which disproves the conjecture for$$k=3$$ k = 3 . Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 
    more » « less
  5. Abstract It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla $$ L β , γ = - div D d + 1 + γ - n associated to a domain$$\Omega \subset {\mathbb {R}}^n$$ Ω R n with a uniformly rectifiable boundary$$\Gamma $$ Γ of dimension$$d < n-1$$ d < n - 1 , the now usual distance to the boundary$$D = D_\beta $$ D = D β given by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$ D β ( X ) - β = Γ | X - y | - d - β d σ ( y ) for$$X \in \Omega $$ X Ω , where$$\beta >0$$ β > 0 and$$\gamma \in (-1,1)$$ γ ( - 1 , 1 ) . In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$ L β , γ , with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$ D 1 - γ , in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$ | D ( ln ( G D 1 - γ ) ) | 2 satisfies a Carleson measure estimate on$$\Omega $$ Ω . We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear). 
    more » « less