Improved FPT algorithms for weighted independent set in bull-free graphs

Very recently, Thomassé et al. (2017) have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time $2^{O\left(k^5\right)}?n^9$. In this article we improve this running time to $2^{O\left(k^2\right)}?n^7$. As a byproduct, we also improve the previous Turing-kernel for this problem from $O\left(k^5\right)$ to $O\left(k^2\right)$. Furthermore, for the subclass of bull-free graphs without holes of length at most $2p?1$ for $p\ge 3$, we speed up the running time to $2^{O(k?k^{\frac{1}{p?1}})}?n^7$. As $p$ grows, this running time is asymptotically tight in terms of $k$, since we prove that for each integer $p\ge 3$, Weighted Independent Set cannot be solved in time $2^{o\left(k\right)}?n^{O\left(1\right)}$ in the class of $\{\text{bull},C_4,\dots ,C_{2p?1}\}$-free graphs unless the ETH fails.     

Weak version of restriction estimates for spheres and paraboloids in finite fields

We study $L^p-L^r$ restriction estimates for algebraic varieties in d-dimensional vector spaces over finite fields. Unlike the Euclidean case, if the dimension d is even, then it is conjectured that the $L^{(2d+2)/(d+3)}-L^2$ Stein–Tomas restriction result can be improved to the $L^{(2d+4)/(d+4)}-L^2$ estimate for both spheres and paraboloids in finite fields. In this paper we show that the conjectured $L^p-L^2$ restriction estimate holds in the specific case when test functions under consideration are restricted to d-coordinate functions or homogeneous functions of degree zero. To deduce our result, we use the connection between the restriction phenomena for our varieties in d dimensions and those for homogeneous varieties in $(d+1)$ dimensions.     

Small Kakeya sets in non-prime order planes

The finite field analog of the classical Kakeya problem asks the smallest possible size for a set of points in the Desarguesian affine plane which contains a line in every direction. This problem has been definitively solved by Blokhuis and Mazzocca (2008), who show that in $AG(2,s)$, $s$ a prime power, the smallest possible size of such a set is $\frac{1}{2}s(s+1)$. In this paper we examine a new construction of an infinite family of sets in $AG(2,s)$ containing a line in every direction, where $s=q^e$ with $q$ a prime power and $e$ an integer with $e>1$. These sets have size $\frac{1}{2}{q}^{2e}+O\left(q^{2e-1}\right)$, which is small in the sense that the lower bound is also $\frac{1}{2}{q}^{2e}$ plus smaller order terms. In addition, we discuss the minimality of our sets, showing that they contain no proper subset containing a line in every direction.     

Powerful numbers in (1ℓ + qℓ)(2ℓ + qℓ)⋯(nℓ + qℓ)

Let q be a positive integer. Recently, Niu and Liu proved that, if $n\ge \max ?\{q,1198?q\}$, then the product $(1^3+q^3)(2^3+q^3)?(n^3+q^3)$ is not a powerful number. In this note, we prove (1) that, for any odd prime power ? and $n\ge \max ?\{q,11?q\}$, the product $(1^{?}+q^{?})(2^{?}+q^{?})?(n^{?}+q^{?})$ is not a powerful number, and (2) that, for any positive odd integer ?, there exists an integer $N_{q,?}$ such that, for any positive integer $n\ge N_{q,?}$, the product $(1^{?}+q^{?})(2^{?}+q^{?})?(n^{?}+q^{?})$ is not a powerful number.     

Unique continuation for first-order systems with integrable coefficients and applications to elasticity and plasticity

Let $\Omega ?{\mathbb{R}}^N$ be a Lipschitz domain and Γ be a relatively open and non-empty subset of its boundary ?Ω. We show that the solution to the linear first-order system:(1)$\mathrm{?}\zeta =G\zeta ,\zeta {|}_{\Gamma }=0,$ vanishes if $G\in {\mathsf{L}}^1(\Omega ;{\mathbb{R}}^{(N\times N)\times N})$ and $\zeta \in {\mathsf{W}}^{1,1}(\Omega ;{\mathbb{R}}^N)$. In particular, square-integrable solutions ζ of (1) with $G\in {\mathsf{L}}^1\cap {\mathsf{L}}^2(\Omega ;{\mathbb{R}}^{(N\times N)\times N})$ vanish. As a consequence, we prove that:$???:{\mathsf{C}}_{°}^{\infty }(\Omega ,\Gamma ;{\mathbb{R}}^3)\to [0,\infty ),u?6\mathrm{sym}\left(\mathrm{?}u{P}^{?1}\right)6_{{\mathsf{L}}^2(\Omega )}$ is a norm if $P\in {\mathsf{L}}^{\infty }(\Omega ;{\mathbb{R}}^{3\times 3})$ with $\mathrm{Curl}P\in {\mathsf{L}}^p(\Omega ;{\mathbb{R}}^{3\times 3})$, $\mathrm{Curl}{P}^{?1}\in {\mathsf{L}}^q(\Omega ;{\mathbb{R}}^{3\times 3})$ for some $p,q>1$ with $1/p+1/q=1$ as well as $\det P?c^{+}>0$. We also give a new and different proof for the so-called ‘infinitesimal rigid displacement lemma’ in curvilinear coordinates: Let $\Phi \in {\mathsf{H}}^1(\Omega ;{\mathbb{R}}^3)$, $\Omega ?{\mathbb{R}}^3$, satisfy $\mathrm{sym}(\mathrm{?}{\Phi }^{?}\mathrm{?}\Psi )=0$ for some $\Psi \in {\mathsf{W}}^{1,\infty }(\Omega ;{\mathbb{R}}^3)\cap {\mathsf{H}}^2(\Omega ;{\mathbb{R}}^3)$ with $\det \mathrm{?}\Psi ?c^{+}>0$. Then there exists a constant translation vector $a\in {\mathbb{R}}^3$ and a constant skew-symmetric matrix $A\in \mathfrak{so}(3)$, such that $\Phi =A\Psi +a$.