More Like this

1. Independent dominating sets in graphs of girth five

   https://doi.org/10.1017/s0963548320000279  

   Harutyunyan, Ararat; Horn, Paul; Verstraete, Jacques (May 2021, Combinatorics, Probability and Computing)

   Abstract Let $$\gamma(G)$$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n -vertex graph of minimum degree at least d , then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n -vertex d -regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d . This result is sharp in the sense that as $$d \rightarrow \infty$$ , almost all d -regular n -vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of $${n}/{(2d)}$$ complete bipartite graphs $$K_{d,d}$$ , then $${\gamma_\circ}(G) = \frac{n}{2}$$ . We also prove that there are n -vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that $${\gamma_\circ}(G) \sim {n}/{2}$$ as $$d \rightarrow \infty$$ . Therefore both the girth and regularity conditions are required for the main result. 

   more » « less
2. Rates of convergence in $$W^2_p$$-norm for the Monge-Amp\`ere equation.

   Neilan, Michael; Zhang, Wujun (October 2018, SIAM journal on numerical analysis)

   We develop discrete $$W^2_p$$-norm error estimates for the Oliker--Prussner method applied to the Monge--Ampère equation. This is obtained by extending discrete Alexandroff estimates and showing that the contact set of a nodal function contains information on its second-order difference. In addition, we show that the size of the complement of the contact set is controlled by the consistency of the method. Combining both observations, we show that the error estimate $$\| u - u_h \|_{W^2_{f,p}} (\mathcal{N}^I_h)$$ converges in order $$O(h^{1/p})$$ if $p > d$ and converges in order $$O(h^{1/d} \ln (\frac 1 h)^{1/d})$$ if $$p \leq d$$, where $$\|\cdot\|_{W^2_{f,p}(\mathcal{N}^I_h)}$$ is a weighted $$W^2_p$$-type norm, and the constant $C>0$ depends on $$\|{u}\|_{C^{3,1}(\bar\Omega)}$$, the dimension $$d$$, and the constant $$p$$. Numerical examples are given in two space dimensions and confirm that the estimate is sharp in several cases. 

   more » « less
3. Affine Stresses, Inverse Systems, and Reconstruction Problems

   https://doi.org/10.1093/imrn/rnad294  

   Murai, Satoshi; Novik, Isabella; Zheng, Hailun (December 2023, International Mathematics Research Notices)

   Abstract A conjecture of Kalai asserts that for $$d\geq 4$$, the affine type of a prime simplicial $$d$$-polytope $$P$$ can be reconstructed from the space of affine $$2$$-stresses of $$P$$. We prove this conjecture for all $$d\geq 5$$. We also prove the following generalization: for all pairs $(i,d)$ with $$2\leq i\leq \lceil \frac d 2\rceil -1$$, the affine type of a simplicial $$d$$-polytope $$P$$ that has no missing faces of dimension $$\geq d-i+1$$ can be reconstructed from the space of affine $$i$$-stresses of $$P$$. A consequence of our proofs is a strengthening of the Generalized Lower Bound Theorem: it was proved by Nagel that for any simplicial $(d-1)$-sphere $$\Delta $$ and $$1\leq k\leq \lceil \frac {d}{2}\rceil -1$$, $$g_{k}(\Delta )$$ is at least as large as the number of missing $(d-k)$-faces of $$\Delta $$; here we show that, for $$1\leq k\leq \lfloor \frac {d}{2}\rfloor -1$$, equality holds if and only if $$\Delta $$ is $$k$$-stacked. Finally, we show that for $$d\geq 4$$, any simplicial $$d$$-polytope $$P$$ that has no missing faces of dimension $$\geq d-1$$ is redundantly rigid, that is, for each edge $$e$$ of $$P$$, there exists an affine $$2$$-stress on $$P$$ with a non-zero value on $$e$$. 

   more » « less
4. Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare

   https://doi.org/10.1093/qmath/haz022  

   Basu, Saugata; Lerario, Antonio; Natarajan, Abhiram (October 2019, The Quarterly Journal of Mathematics)

   Abstract Given a sequence $$\{Z_d\}_{d\in \mathbb{N}}$$ of smooth and compact hypersurfaces in $${\mathbb{R}}^{n-1}$$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$ such that each manifold $$Z_d$$ is diffeomorphic to a component of the zero set on $$\Gamma$$ of some polynomial of degree $$d$$. (This is in sharp contrast with the case when $$\Gamma$$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $$p$$ on $$\Gamma$$ is bounded by a polynomial in $$\deg (p)$$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$$ containing a subset $$D$$ homeomorphic to a disk, and a family of polynomials $$\{p_m\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that $$(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$$ i.e. the zero set of $$p_m$$ in $$D$$ is isotopic to $$Z_{d_m}$$ in $${\mathbb{R}}^{n-1}$$. This says that, up to extracting subsequences, the intersection of $$\Gamma$$ with a hypersurface of degree $$d$$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $$0 \leq k \leq n-2$$ and every sequence of natural numbers $$a=\{a_d\}_{d\in \mathbb{N}}$$ there is a regular, compact semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$, a subsequence $$\{a_{d_m}\}_{m\in \mathbb{N}}$$ and homogeneous polynomials $$\{p_{m}\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $$b_k$$ denotes the $$k$$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $$\Gamma$$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $$d$$, of the set $$\Sigma _{d_m,a, \Gamma }$$ of polynomials verifying (0.1) is positive, but there exists a constant $$c_\Gamma$$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $$a$$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $$\Gamma$$, for most polynomials a Bézout-type bound holds for the intersection $$\Gamma \cap Z(p)$$: for every $$0\leq k\leq n-2$$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$ 

   more » « less
5. Energy Harvesting Performance of a Flapping Foil with Leading Edge Motion

   Prier, M. (April 2019, Dissertation)

   F or c e d at a f or a fl a p pi n g f oil e n er g y h ar v e st er wit h a cti v e l e a di n g e d g e m oti o n o p er ati n g i n t h e l o w r e d u c e d fr e q u e n c y r a n g e i s c oll e ct e d t o d et er mi n e h o w l e a di n g e d g e m oti o n aff e ct s e n er g y h ar v e sti n g p erf or m a n c e. T h e f oil pi v ot s a b o ut t h e mi dc h or d a n d o p er at e s i n t h e l o w r e d u c e d fr e q u e n c y r a n g e of 𝑓𝑓 𝑓𝑓 / 𝑈𝑈 ∞ = 0. 0 6 , 0. 0 8, a n d 0. 1 0 wit h 𝑅𝑅 𝑅𝑅 = 2 0 ,0 0 0 − 3 0 ,0 0 0 , wit h a pit c hi n g a m plit u d e of 𝜃𝜃 0 = 7 0 ∘ , a n d a h e a vi n g a m plit u d e of ℎ 0 = 0. 5 𝑓𝑓 . It i s f o u n d t h at l e a di n g e d g e m oti o n s t h at r e d u c e t h e eff e cti v e a n gl e of att a c k e arl y t h e str o k e w or k t o b ot h i n cr e a s e t h e lift f or c e s a s w ell a s s hift t h e p e a k lift f or c e l at er i n t h e fl a p pi n g str o k e. L e a di n g e d g e m oti o n s i n w hi c h t h e eff e cti v e a n gl e of att a c k i s i n cr e a s e d e arl y i n t h e str o k e s h o w d e cr e a s e d p erf or m a n c e. I n a d diti o n a di s cr et e v ort e x m o d el wit h v ort e x s h e d di n g at t h e l e a di n g e d g e i s i m pl e m e nt f or t h e m oti o n s st u di e d; it i s f o u n d t h at t h e m e c h a ni s m f or s h e d di n g at t h e l e a di n g e d g e i s n ot a d e q u at e f or t hi s p ar a m et er r a n g e a n d t h e m o d el c o n si st e ntl y o v er pr e di ct s t h e a er o d y n a mi c f or c e s. 

   more » « less