Search

Sendov’s conjecture states that if all the zeroes of a complex polynomial P(z) of degree at least two lie in the unit disk, then within a unit distance of each zero lies a critical point of P(z). In a paper that appeared in 2014, Degot proved that, for each a ∈ (0, 1), there exists an integer N such that for any polynomial P(z) with degree greater than N, if P(a) = 0 and all zeroes lie inside the unit disk, the disk |z − a| ≤ 1 contains a critical point of P(z). Based on this result, we derive an explicit formula N(a) for each a ∈ (0, 1) and, consequently obtain a uniform bound N for all a ∈ [α, β] where 0 < α < β < 1. This (partially) addresses the questions posed in Degot’s paper.

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

Let l be a Banach sequence space with a monotone norm in which the canonical system (e_{n}) is an unconditional basis. We show that if there exists a continuous linear unbounded operator between l-K\"{o}the spaces, then there exists a continuous unbounded quasi-diagonal operator between them. Using this result, we study in terms of corresponding K\"{o}the matrices when every continuous linear operator between l-K\"{o}the spaces is bounded. As an application, we observe that the existence of an unbounded operator between l-K\"{o}the spaces, under a splitting condition, causes the existence of a common basic subspace.

We give common generalizations of the Menon-type identities by Sivaramakrishnan (1969) and Li, Kim, Qiao (2019). Our general identities involve arithmetic functions of several variables, and also contain, as special cases, identities for gcd-sum type functions. We point out a new Menon-type identity concerning the lcm function. We present a simple character free approach for the proof., Comment: 14 pages

This expository paper presents known results on distribution functions g(x) of the sequence of blocks where xn is an increasing sequence of positive integers. Also presents results of the set G(Xn) of all distribution functions g(x). Specially: - continuity of g(x); - connectivity of G(Xn); - singleton of G(Xn); - one-step g(x); - uniform distribution of Xn, n = 1, 2, . . . ; - lower and upper bounds of g(x); - applications to bounds of ; - many examples, e.g., , where pn is the nth prime, is uniformly distributed. The present results have been published by 25 papers of several authors between 2001-2013.

The aim of this paper is to discuss the main result in the paper by D.Y. Gao and X. Lu [On the extrema of a nonconvex functional with double-well potential in 1D, Z. Angew. Math. Phys. (2016) 67:62]. More precisely we provide a detailed study of the problem considered in that paper, pointing out the importance of the norm on the space $C^{1}[a,b]$; because no norm (topology) is mentioned on $C^{1}[a,b]$ we look at it as being a subspace of $W^{1,p}(a,b)$ for $p\in [1,\infty]$ endowed with its usual norm. We show that the objective function has not local extrema with the mentioned constraints for $p\in [1,4)$, and has (up to an additive constant) only a local maximizer for $p=\infty$, unlike the conclusion of the main result of the discussed paper where it is mentioned that there are (up to additive constants) two local minimizers and a local maximizer. We also show that the same conclusions are valid for the similar problem treated in the preprint by X. Lu and D.Y. Gao [On the extrema of a nonconvex functional with double-well potential in higher dimensions, arXiv:1607.03995]., 12 pages; in this version we added the forgotten condition $F(x) \ne 0$ for $x\in (a,b)$ on page 3

In 1935, Erdos proved that all natural numbers can be written as a sum of a square of a prime and a square-free number. In 1939, Pillai derived an asymptotic formula for the number of such representations. The mathematical review of Pillai’s paper stated that the proof of the above result contained inaccuracies, thus casting a doubt on the correctness of the paper. In this paper, we re-examine Pillai’s paper and show that his argument was essentially correct. Afterwards, we improve the error term in Pillai’s theorem using the Bombieri–Vinogradov theorem.

Let G = (V,E) be a graph and k be a positive integer. A k-dominating set of G is a subset S ⊆ V such that each vertex in V \S has atleast k neighbors in S. A Roman k-dominating function on G is a functionf : V → {0,1,2} such that every vertex v with f(v) = 0 is adjacent toat least k vertices v 1 ,v 2 ,...,v k with f(v i ) = 2 for i = 1,2,...,k. In thepaper titled “Roman k-domination in graphs” (J. Korean Math. Soc. 46(2009), no. 6, 1309–1318) K. Kammerling and L. Volkmann showed thatfor any graph G with n vertices, γ kR (G) + γ kR (G) ≥ min {2n,4k + 1},and the equality holds if and only if n ≤ 2k or k ≥ 2 and n = 2k + 1or k = 1 and G or G has a vertex of degree n − 1 and its complementhas a vertex of degree n − 2. In this paper we find a counterexampleof Kammerling and Volkmann’s result and then give a correction to theresult. 1. IntroductionLet G = (V,E) be agraphwith vertexset V = V (G) andedge set E = E(G).A k-dominatingsetof G is a subset S ⊆ V such that every vertex in V \S has atleast k neighbors in S. The k-domination numberγ

In Variations on a theme in paper folding, Burkard Polster [6] discusses an itera tive construction due to Hilton and Pedersen [3] for approximating any acute rational angle (rational multiple of n radians) to any desired accuracy by folding a strip of paper. Hilton and Pedersen, motivated by the construction of regular polygons and star-polygons, focus on the construction of rational angles. The construction employs a periodic sequence composed of two types of folding moves, guided by number theoretic properties of the angle's fractional representation (in fact, analysis of the construction yields new results in number theory?see [4], [1], and [2]). This note generalizes this construction to any acute angle, rational or irrational. For irrational angles, the number-theoretic prescription must obviously be replaced by something new; we show how to derive the appropriate aperiodic sequence of folding moves, via a connection between the folding construction and a simple dynamical system. Hilton and Pedersen's construction recursively generates a sequence of angles a0, otx, ... by a pair of folding operations on a strip of paper which we term Folds and Switchfolds. The angles ak appear between an edge of the strip and a crease created by folding. The Fold operation generates ak+x by bisecting ak (Figure 1)

A record mentioned in the paper by Moree (Abh Math Sem Univ Hamburg 77:109–127, 2007) was recently improved on by Akbary and Scholten. However, the record mentioned was not the then record. The then record, due to Gallot (2004), actually slightly improves on that obtained recently by Akbary and Scholten.

In this note, we slightly generalize Theorem 2 in the paper by M. Tunç and point out that the assumption of Theorem 3 is not sufficient. A misuse of the term 'mean' is also discussed.

Fine and Wilf's theorem has recently been extended to words having three periods. Following the method of the authors we extend it to an arbitrary number of periods and deduce from that a characterization of generalized Arnoux-Rauzy sequences or episturmian infinite words.

This note is related to a nice short paper of M. Ochiai. We prove in a very fast way that the two-parameter family of Heegaard diagrams, constructed by Ochiai, encodes the genuine three-sphere. The result is obtained, up to isotopy, by using a sequence of only three moves in this order: a Whitehead–Zieschang reduction, a band sum and a cancellation of a handle.

Most of the known continued fraction expansions of special functions are limit periodic. This means that the classical approximants S n (0) are normally not the best ones to use for approximations. In this paper we suggest a number of approximants S n (w n ) which converge faster. The estimation of the improvement and bounds for the error |f - Sn(wn)| (which we still call the truncation error) are mainly obtained by means of Thron's parabola sequence theorem and the oval sequence theorem.

We generalize and give a simple proof of a Theorem of Blasco. For a topological space X , C(X) denotes the algebra of real valued continuous functions on X under the operation (αf + gh)(x) := αf(x) + h(x)g(x) for each f, g, h ∈ C(X) and α ∈ R. An algebra A on X means a subalgebra of C(X) which contains the constant functions. By a ∗-algebra A on X we mean an algebra on X and all bounded functions in A separate points from the closed sets. Let A be an algebra on X and π : A −→ R be a (algebra) homomorphism and α be a cardinal number. π is said to be α-evaluating if for each subset B of A with cardinality at most α there exits xB ∈ X such that π(f) = f(xB) for each f ∈ B. If α = |N|(=the cardinal number of the set of the natural numbers N), the α-evaluating homomorphism is called countable evaluating. Let α be a cardinal number. Recall that a topological space X is called αLindelof if for each open cover U has a subcover V such that the cardinality of V is at most α. A lindelof space means a |N|-Lindelof space. The following theorem is given in [1] as one of the main results. Theorem 1. Let X be a completely regular Hausdorff space. Then X is Lindelof if and only if each countable evaluating homomorphism π on a ∗-algebra A on X is point evaluating. Received June 9, 2004; accepted June 30, 2004. Communicated by Bor-Luh Lin. 2000 Mathematics Subject Classification: Primary 54C35, 46E25.

As early as the 16th century, Simon Jacob, a German reckoning master, noticed that the worst case in computing the greatest common divisor of two numbers by the Euclidean algorithm occurs if these numbers are equimultiples of two consecutive members of the Fibonacci sequence.

In the mentioned paper of Hadwiger an upper bound is given for α (A)·N(A), where α (A) is the density of covering ℝn by lattice translates ofA⊂ℝn andN(A) is the number of neighbours ofA. Using “dual” descriptions of α (A) andN(A), in the paper a sharpening of Hadwiger's inequality as well as a lower bound for α (A)·N(A) are proved.

iF(y)=( where G c R* is a bounded domain, y: G -» R , y'(x) = (dyydx), and F: M -> R is continuous. Here M denotes the linear space of real N X k matrices. We suppose throughout that K > 2, N > 2. In [7] F is called T-conυex if there exists a convex function /, defined on R, r = (t) ~ 1, such that F(p) = f(τ(p)) for all/? e M, where τ(p) denotes the minors of p of all orders j , 1 y uniformly on G with supx χGG\yj(x) ~ yj(x)\ < C < oo for ally. (Equivalently, if G has sufficiently regular boundary then IF is lsc if and only if IF is sequentially weak* lower semicontinuous on the Sobolev space W(G; R).) A consequence of [7? Theorem 3.6] is that IF lsc implies F polyconvex; that this conclusion is false was pointed out implicitly by Morrey [4, p. 26]. Morrey's remark is based on an example due to Terpstra [8] of a quadratic form

R. A. Brualdi [1] presents a construction yielding matrices whose Birkhoff representation consists of the maximum number of permutation matrices and having 0(2n2) line sum. In this note a counterexample to such a construction is given. Furthermore, a new construction is presented, yielding matrices with lower line sums.

By 350 B.C. the Greeks knew Euclidean constructions for the regular polygons of 4, 8, 16,... sides and for those of 3 and 5 sides-the equilateral triangle and the regular pentagon. From these it was easy to construct regular polygons of 2c x 3, 2c x 5, 2c x 3 x 5 sides, where c is any positive integer, and the Greeks in effect showed how. They got no farther. Young Gauss proved that if N is of the form 2c or 2c times a product of different Fermat primes F,,, then there is a Eucidean construction for a regular polygon of N sides. This form of N is both necessary and sufficient for the possibility of a Eucidean construction....

The object of this note is to point out and correct an error in the paper [21 of Fox, purporting to prove Fenchel's conjecture that a finitely generated. infinite Fuchsian group has a torsion-free normal subgroup of finite index. Fox divided the proof of the main result in his paper into four cases and an error occurs in the proofs of Cases (III) and (IV). A direct proof of Case (III) was given. While a direct proof of Case (IV) can be given, the author shows that it also follows indirectly from the result in the paper [1] of Burns and Solitar. Given any three integers a > 1, b > 1 and c > 1, there exist permutations A of order a and B of order b, such that AB has order c. Fox divided the proof of this lemma into the four cases: (I) ab 0 (mod 2) and max{a, b} ? c < a + b, (II) ab 0 (mod 2) and c : a + b, (III) a b c 1 (mod 2), (IV) a b 1 and c 0 (mod 2), and subcases. In the subcase m(a + b 2) + 2 ? c < (m + l)(b + 1) 1 of Case (III) where m is the largest integer not exceeding (c l)/(b + 1), and it is assumed that a ? b < c, the number of distinct symbols in the permutations [2, p. 64] nl~~~W B ( Wv-sI .. WI2 I7 (vWb B = (vl * *t*v W_ ***W P2) * (V W2 .. * ]Pi+]1)'

Let G be an abelian group. The aim of this short paper is to describe a way to identify pure subgroups H of G by looking only at how the subgroup lattice $$\mathcal {L}(H)$$ L ( H ) embeds in $$\mathcal {L}(G)$$ L ( G ) . It is worth noticing that all results are carried out in a local nilpotent context for a general definition of purity.

This short paper is motivated by the paper of Bu et al. [C. Bu, C. Feng, P. Dong, A note on computational formulas for the Drazin inverse of certain block matrices, J. Appl. Math. Comput.(38) (2012) 631-640], where the authors gave additive formula for Drazin inverse for matrices under new conditions, and two representations under some specific conditions. Here is shown that the additive formula is not valid for all matrices which satisfy given conditions. Also, here is proved that the representations which were given in mentioned paper do not extend the results given by Hartwig et al. [R. Hartwig, X. Li, Y. Wei, Representations for the Drazin inverse of a 2 _ 2 block matrix, SIAM J. Matrix. Anal. Appl. (27)(2006) 757-771 ], in fact they are equivalent.

In this short paper, we will show that the space of real valued uniformly continuous functions defined on a metric space (X,d) is a ring if and only if every subset A ? X has one of the following properties: ? A is Bourbaki-bounded, i.e., every uniformly continuous function on X is bounded on A. ? A contains an infinite uniformly isolated subset, i.e., there exist ? > 0 and an infinite subset F ? A such that d(a,x) ? ? for every a ? F, x ? X n \{a}.

A subset A of a topological space is said to be semi-open if there exists an open set U such that U C A C Cl(U) where Cl(U) denotes the closure of U. The class of semi-open sets of a given topological space (X, J) is denoted S.O. (X, J). In the paper Semi-open sets and semi-continuity in topological spaces, Amer. Math. Monthly 70 (1963), 36-41, Norman Levine states in Theorem 10 that if J and V* are two topologies for a set X such that S.O.(X, 3) C S.O.(X, J*), then 'J C P. In a corollary to this theorem, Levine states that if S.O.(X, if) = S.O.(X,Jf*), then _T= f*. An example is given which shows the above-mentioned theorem and its corollary are false. This paper shows how different topologies on a set which determine the same class of semi-open subse,ts can arise from functions, and points out some of the implications of two topologies being related in this manner. In [6] Norman Levine defines a set A in a topological space X to be semi-open if there exists an open set U such that U C A C Cl (U), where Cl(U) denotes the closure of U. The class of semi-open sets for a given topological space (X, i) is denoted S.O. (X, sT). Levine states in Theorem 10 of [6] that if Jf and * are two topologies for a set X such that S.O. (X, i) C S.O. (X, J9 then iT C *. In a corollary to this theorem, Levine states that if S.O. (X, ) = S.O. (X, iT*), then Jf = -" The following example which is due to S. Gene Crossley and S. K. Hildebrand [1, Example 1.1] shows the above-mentioned theorem and its corollary are false. Example. Let X = la, b, cl, J; = t0, sal, la, bl, la, cl, XI, ;* = 10, sal, la, bl, XI. An exhaustion of all possibilities shows that S.O. (X, ) = S.O. (x, 5j*). Crossley and Hildebrand [3] defined two topologies iT and T* on a set X to be semi-correspondent if S.O. (X, J) = S.O. (X, 5f*). It is shown in [3] that semi-correspondence is an equivalence relation on the collection of Received by the editors March 3, 1974. AMS (MOS) subject classifications (1970). Primary 54B99; Secondary 54C10.

(1988). An Algebraic Approach to Some Number-Theoretic Problems Arising from Paper-Folding Regular Polygons. The American Mathematical Monthly: Vol. 95, No. 4, pp. 289-307.

Among other results, it is proved that if a sequence {t 1l) of regular measures on a Hausdorff space, with values in a normed group, is convergent to zero for all a-compact sets or all open sets, then there exists a maximal open set U such that ft,1 ( U) O-* { f t,) being the associated submeasures. In [5], J. D. Stein, Jr. considers some versions of Phillip's lemma and the Vitali-Hahn-Saks theorem for sequences of regular scalar-valued Borel measures on Hausdorff spaces. The measures he considers are bounded, regular, and finitely additive Borel measures which are easily seen to be countably additive (to prove this, first note that I pi, the variation of such a measure /L, is regular, bounded, and finitely additive [5, Lemma 1]) and so for a sequence {Bi) of Borel sets, B1j0, and > 0, C a sequence of compact sets (Ki), Ki c Bi and vi(Bi \ K1) some no and so I til(BiWO), an observation which enables one to prove his results easily, in more general forms, and under weaker conditions. Theory of submeasures developed in [1] will be used. Let G be an Abelian Hausdorff topological group, X a Hausdorff topological space, and yt a countably additive, regular, G-valued measure on X (by regularity we mean that for any Borel set B in X and a 0-nbd U in G, there exists a compact set C c B such that tt(K) C U, VK c B \ C, K Borel). If G is normed [1, p. 270], we have an associated submeasure ft, AK(B) = sup{14(A)I:A c B,A Borel) = sup{ I(C)I: C c B, Ccompact), which is finite [1, p. 279, Corollary 4.1 1], exhaustive, a-subadditive, and order-continuous [1, II]. It is also regular in the sense that given E > 0 and a Borel set B, 3 a compact set K c B such that i(B \ K) < (proof by contradiction, using exhaustivity). For a collection of measures or subReceived by the editors August 25, 1976. AMS (MOS) subject classifications (1970). Primary 28A25; Secondary 46G10.

This short paper concerns the existence of curves with low gonality on smooth hypersurfaces $$X\subset \mathbb {P}^{n+1}$$ . After reviewing a series of results on this topic, we report on a recent progress we achieved as a product of the Workshop Birational geometry of surfaces, held at University of Rome “Tor Vergata” on January 11th–15th, 2016. In particular, we obtained that if $$X\subset \mathbb {P}^{n+1}$$ is a very general hypersurface of degree $$d\geqslant 2n+2$$ , the least gonality of a curve $$C\subset X$$ passing through a general point of X is $$\mathrm {gon}(C)=d-\left\lfloor \frac{\sqrt{16n+1}-1}{2}\right\rfloor $$ , apart from some exceptions we list.

In this short paper we study the d-Hermite condition about stably free modules for skew $$\textit{PBW}$$ extensions. For this purpose, we estimate the stable rank of these non-commutative rings. In addition, and closely related with these questions, we will prove Kronecker’s theorem about the radical of finitely generated ideals for some particular types of skew $$\textit{PBW}$$ extensions.

We study the classical \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\varOmega (\sqrt{\log n})}}$$\end{document}2Ω(logn), assuming \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}\not \subseteq \mathsf {DTIME}(n^{\mathcal {O}(\log n)})}$$\end{document}NP⊈DTIME(nO(logn)). This constitutes a significant gap to the best known approximation upper bound of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al. (Theory Comput 2:137–146, 2006), and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica 7(4):365–374, 1987) introduce the technique of randomized rounding for LPs; their technique gives an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(1)}$$\end{document}O(1)-approximation when edges (or nodes) may be used by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}\left( \log n/\log \log n\right) }$$\end{document}Ologn/loglogn paths. In this paper, we strengthen the fundamental results above. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following results:For MaxEDP, we give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{r} \log ({k}r))}$$\end{document}O(rlog(kr))-approximation algorithm. Up to a logarithmic factor, our result strengthens the best known ratio \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al., as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r\le n}$$\end{document}r≤n.Further, we show how to route \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varOmega ({\text {OPT}}^{*})}$$\end{document}Ω(OPT∗) pairs with congestion bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\log (kr)/\log \log (kr))}$$\end{document}O(log(kr)/loglog(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson.For MaxNDP, we give an algorithm that gives the optimal answer in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(k+r)^{\mathcal {O}(r)}\cdot n}$$\end{document}(k+r)O(r)·n. This is a substantial improvement on the run time of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^kr^{\mathcal {O}(r)}\cdot n}$$\end{document}2krO(r)·n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MaxEDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard even for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r=1}$$\end{document}r=1, and MaxNDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {W}[1]}$$\end{document}W[1]-hard when r is the parameter. This shows that neither problem is fixed-parameter tractable in r unless \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {FPT}= \mathsf {W}[1]}$$\end{document}FPT=W[1] and that our approximability results are relevant even for very small constant values of r.

In this short paper, we characterise graphs of order $pq$ with $p, q$ prime which are self-complementary and vertex-transitive.

‡ Abstract. In this short paper we study the game of cops and robbers, which is played on the vertices of some fixed graph G. Cops and a robber are allowed to move along the edges of G, and the goal of cops is to capture the robber. The cop number cðGÞ of G is the minimum number of cops required to win the game. Meyniel conjectured a long time ago that Oð ffiffiffi p Þ cops are enough for any connected G on n vertices. Improving several previous results, we prove that the cop number of an n-vertex graph is at most n2 −ð1þoð1ÞÞ ffiffiffiffiffiffiffiffi log n p .A similar result independently and slightly before us was also obtained by Lu and Peng.

0.1. How it all began. When the second author translated a result on algebraic sur faces into the language of lattice polygons using toric geometry, he got a simple inequality for lattice polygons. This inequality had originally been discovered by Scott [12]. The first author then found a third proof. Subsequently, both authors went through a phase of polygon addiction. Once you get started drawing lattice polygons on graph paper and discovering relations between their numerical invariants, it is not so easy to stop! (The gentle reader has been warned.) Thus, it was just unavoidable that the authors came up with new inequalities: Scott's inequality can be sharpened if one takes into account another invariant, which is de fined by peeling off the skins of the polygons like an onion (see Section 3).

In this short paper we establish a (non-trivial) lower bound on the degree two entry h 2 of a Gorenstein h-vector of any given socle degree e and any codimension r. In particular, when e = 4, that is, for Gorenstein h-vectors of the form h = (1, r, h 2 , r, 1), our lower bound allows us to prove a conjecture of Stanley on the order of magnitude of the minimum value, say f(r), that h 2 may assume. In fact, we show that limr→∞ f(r) r 2/3 =6 2/3 . In general, we wonder whether our lower bound is sharp for all integers e > 4 and r > 2.

In this short paper, we extend the classical Hoffman-Meeks Halfspace Theorem [Hoffman and Meeks, 'The strong halfspace theorem for minimal surfaces', Invent. Math. 101 (1990) 373-377] to self-shrinkers, that is: Let $P$ be a hyperplane passing through the origin. The only properly immersed self-shrinker $\Sigma $ contained in one of the closed half-space determined by $P$ is $\Sigma = P$. Our proof is geometric and uses a catenoid type hypersurface discovered by Kleene-Moller [Kleene and Moller, 'Self-shrinkers with a rotational symmetry', Trans. Amer. Math. Soc. 366 (2014) 3943-3963]. Also, using a similar geometric idea, we obtain that the only self-shrinker properly immersed in an closed cylinder $ \overline {B^{k+1} (R)} \times {\mathbb R}^{n-k}\subset {\mathbb R}^{n+1}$, for some $k\in \{1, \ldots, n\}$ and radius $R$, $R \leqslant \sqrt {2k}$, is the cylinder ${\mathbb S}^k (\sqrt {2k}) \times {\mathbb R}^{n-k}$. We also extend the above results for $\lambda $-hypersurfaces.

In this short paper, we consider the functional density on sets of uniformly bounded triangulations with fixed sets of vertices. We prove that if a functional attains its minimum on the Delaunay triangulation, for every finite set in the plane, then for infinite sets the density of this functional attains its minimum also on the Delaunay triangulations.

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the primal problem is nondegenerate, it becomes a bound for the number of iterations. We show some basic results when it is applied to special linear programming problems. The results include strongly polynomiality of the simplex method for Markov Decision Problem by Ye and utilize its analysis., Comment: Keywords: Simplex method, Linear programming, Iteration bound, Strong polynomiality, Basic feasible solutions

We shall present partial solutions to the conjecture such that $(q^{p}-1)/(q-1)$ does not divide $(p^{q}-1)/(p-1)$ for distinct primes $p < q$.