Search

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)$.

We correct some mistakes in the paper “A mass formula for negacyclic codes of length 2k and some good negacyclic codes over $\mathbb {Z}_{4}+u\mathbb {Z}_{4}$ ” (Bandi et al. Cryptogr. Commun. 9, 241–272, 2017).

Very recently Bordelles, Dai, Heyman, Pan and Shparlinski studied asymptotic behaviour of the quantity $$\begin{aligned} S_f(x) := \sum _{n\leqslant x} f\left( \left[ \frac{x}{n}\right] \right) , \end{aligned}$$and established some asymptotic formulas for $$S_f(x)$$ under three different types of assumptions on f. In this short note we improve some of their results.

Recently, metapopulation models for rock-paper-scissors games have been presented. Each subpopulation is represented by a node on a graph. An individual is either rock (R), scissors (S) or paper (P); it randomly migrates among subpopulations. In the present paper, we assume victory rates differ in different subpopulations. To investigate the dynamic state of each subpopulation (node), we numerically obtain the solutions of reaction-diffusion equations on the graphs with two and three nodes. In the case of homogeneous victory rates, we find each subpopulation has a periodic solution with neutral stability. However, when victory rates between subpopulations are heterogeneous, the solution approaches stable focuses. The heterogeneity of victory rates promotes the coexistence of species.

O. Einstein (2008) proved Bollob\'as-type theorems on intersecting families of ordered sets of finite sets and subspaces. Unfortunately, we report that the proof of a theorem on ordered sets of subspaces had a mistake. We prove two weaker variants., Comment: 6 pages. Improved bound for Theorem 4

In this short paper, we look into a conclusion drawn by Alzalg (J Optim Theory Appl 169:32---49, 2016). We think the conclusion drawn in the paper is incorrect by pointing out three things. First, we provide a counterexample that the proposed inner product does not satisfy bilinearity. Secondly, we offer an argument why a pth-order cone cannot be self-dual under any reasonable inner product structure on $$\mathbb {R}^n$$Rn. Thirdly, even under the assumption that all elements operator commute, the inner product becomes an official inner product and the arbitrary-order cone can be shown as a symmetric cone, we think this condition is still unreasonable and very stringent so that the result can only be applied to very few cases.

We present a silent self-stabilizing distributed algorithm computing a maximal p-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most \(12\varDelta m + \mathcal {O}(m+n)\) moves, where m is the number of edges, n is the number of nodes, and \(\varDelta \) is the maximum node degree. Regarding the move complexity, our algorithm outperforms the previously known best algorithm by a factor of \(\varDelta \). While the round complexity for the previous algorithm was unknown, we show a \(5\left\lfloor \frac{n}{p+1} \right\rfloor +5\) bound for our algorithm.

We study leader election in unidirectional rings of homonym processes that have no a priori knowledge on the number of processes. We show that message-terminating leader election is impossible for any class of rings \(\mathcal K_k\) with bounded multiplicity \(k \ge 2\). However, we show that process-terminating leader election is possible in the sub-class \(\mathcal U^* \cap \mathcal K_k\), where \(\mathcal U^*\) is the class of rings which contain a process with a unique label.

In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13---27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.

Let a(n) be the Fourier coefficient of a holomorphic cusp form on some discrete subgroup of \(SL_2({\mathbb R})\). This note is to refine a recent result of Hofmann and Kohnen on the non-positive (resp. non-negative) product of \(a(n)a(n+r)\) for a fixed positive integer r.

We consider the problem of constructing a matching in an n-nodes graph in a distributed and self-stabilizing manner. We prove that there exists a lower bound in space of \(\varOmega (n\log n)\) bits for universal maximal matching algorithms, and a lower bound in time of \(\varOmega (e)\) moves for universal and cautious 1-maximal matching algorithms. A side contribution of our result is the optimality in both time and space of the self-stabilizing 1-maximal matching algorithm of Inoue et al. [8].

Assume that A and G are finite groups of coprime orders such that A acts on G via automorphisms. Let p be a prime. The following coprime action version of a well-known theorem of Ito about the structure of a minimal non-p-nilpotent groups is proved: if every maximal A-invariant subgroup of G is p-nilpotent, then G is p-soluble. If, moreover, G is not p-nilpotent, then G must be soluble. Some earlier results about coprime action are consequences of this theorem.

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

We note a simple algebraic proof of Frolkina’s result that [Formula: see text] does not contain uncountably many pairwise disjoint copies of the Möbius band, and of a similar result in higher dimensions.

Given a convex body $$K$$K, consider the smallest number $$N$$N so that there is a point $$P\in \partial K$$PźźK such that every circle centred at $$P$$P intersects $$\partial K$$źK in at most $$N$$N points. In 1946 Erdźs conjectured that $$N=2$$N=2 for all $$K$$K, but there are convex bodies for which this is not the case. As far as we know there is no known global upper bound. We show that no convex body has $$N=\infty $$N=ź and that there are convex bodies for which $$N = 6$$N=6.

We point out that the proof of Theorem 3.3 of Bagchi and Sastry (2013) contains a serious flaw. Accordingly, this theorem needs to be modified. In consequence, we also have to retract Corollary 3.4, Corollary 3.6 and Theorem 3.8 of Bagchi and Sastry (2013).

Congruences mod p for a prime p and partial products of the numbers 1,…, p − 1 are obtained. Bibliography: 2 titles.

In Vukicevic and Stevanovic (2013), Theorem 2 is erroneous when m = 3 k + 1 for some integer k . The correct one is given now. That is, P I ( G ) ≥ m 2 − 3 m + 2 when m = 3 k + 1 for some integer k , where G is a connected bicyclic graph with m edges.

In this short note we point to an error in the proof of a theorem stated in [L. Balková, E. Pelantová, Š. Starosta, On Brlek-Reutenauer conjecture, Theoret. Comput. Sci. 412 (2011) 5649–5655]. By constructing a counterexample, we show that the assertion of the theorem is actually incorrect. Although this theorem is of a technical character, it was used in an argument leading to a corollary of a general interest to the Brlek-Reutenauer conjecture, and thus as a consequence of this note we have that the proof of the mentioned corollary is also flawed.

For a connected graph G and a vertex v in G , let d G ( v ) , e G ( v ) and D G ( v ) be the degree, eccentricity and distance sum of v , respectively. The eccentric connectivity index of G , denoted by ξ c ( G ) , is defined to be ξ c ( G ) = ∑ v ∈ V ( G ) d G ( v ) e G ( v ) , and the eccentric distance sum of G , denoted by ξ d ( G ) , is defined to be ξ d ( G ) = ∑ v ∈ V ( G ) e G ( v ) D G ( v ) . Denote by G n 2 the set of connected graphs of order n and diameter two. More recently, Zhang et al. (2019) investigated the relationship between the eccentric connectivity index and eccentric distance sum, and posed the problem to determine sharp upper and lower bounds on ξ c ( G ) ξ d ( G ) for graph in G n 2 . In this short paper, we solve this problem. Sharp upper and lower bounds on ξ c ( G ) ξ d ( G ) for graph in G n 2 are determined, and the corresponding extremal graphs are characterized as well.

A well known observation of Lov\'asz is that if a hypergraph is not $2$-colorable, then at least one pair of its edges intersect at a single vertex. %This very simple criterion turned out to be extremly useful . In this short paper we consider the quantitative version of Lov\'asz's criterion. That is, we ask how many pairs of edges intersecting at a single vertex, should belong to a non $2$-colorable $n$-uniform hypergraph? Our main result is an {\em exact} answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollob\'as's two families theorem with Pluhar's randomized coloring algorithm., Comment: A note on Property B

In this short paper, we derive an alternative proof for some known (van den Berg & Gilkey 2015) short-time asymptotics of the heat content in a compact full-dimensional submanifolds S with smooth boundary. This includes formulae like $$\begin{aligned} \int _{S} \exp (t\Delta ) (f \mathbb {1}_{S}) \,\mathrm {d}V= \int _S f \,\mathrm {d}V- \sqrt{\frac{t}{\pi }} \int _{\partial S} f \,\mathrm {d}A+ o(\sqrt{t}),\quad t \rightarrow 0^+, \end{aligned}$$ ∫ S exp ( t Δ ) ( f 1 S ) d V = ∫ S f d V - t π ∫ ∂ S f d A + o ( t ) , t → 0 + , and explicit expressions for similar expansions involving other powers of $$\sqrt{t}$$ t . By the same method, we also obtain short-time asymptotics of $$\int _S \exp (t^m\Delta ^m)(f \mathbb {1}_S)\,\mathrm {d}V$$ ∫ S exp ( t m Δ m ) ( f 1 S ) d V , $$m \in \mathbb N$$ m ∈ N , and more generally for one-parameter families of operators $$t \mapsto k(\sqrt{-t\Delta })$$ t ↦ k ( - t Δ ) defined by an even Schwartz function k.

In this short paper, we reduce the proof of the Leopoldt Conjecture to the proof of the fact that Iwasawa’s \(\mu \)-constant vanishes for all CM \(\mathbb {Z}_p\)-extensions, an assumption that will be proved in a separate paper.

It is proved that the coordination sequence of the graph obtained from a crystal is of quasi-polynomial type, as had been postulated by Grosse-Kunstleve et al. [Acta Cryst. (1996), A52, 879–889] in their study of coordination sequences of zeolites., The coordination sequence of a graph measures how many vertices the graph has at each distance from a fixed vertex and is a generalization of the coordination number. Here it is proved that the coordination sequence of the graph obtained from a crystal is of quasi-polynomial type, as had been postulated by Grosse-Kunstleve et al. [Acta Cryst. (1996), A52, 879–889].

The chord-length distribution function [γ′′(r)] of any bounded polyhedron has a closed analytic expression which changes in the different subdomains of the r range. In each of these, the γ′′(r) expression only involves, as transcendental contributions, inverse trigonometric functions of argument equal to R[r, Δ1], Δ1 being the square root of a second-degree r polynomial and R[x, y] a rational function. As r approaches δ, one of the two end points of an r subdomain, the derivative of γ′′(r) can only show singularities of the forms |r − δ|−n and |r − δ|−m+1/2, with n and m appropriate positive integers. Finally, the explicit analytic expressions of the primitives are also reported.

Let G and H be two discrete groups of Mobius transformations of R n = R n ∪ {∞} and let Φ : G → H be an isomorphism. The question to what extent Φ can be realized geometrically has been the subject of many studies. Many of these have been based on the observation that under certain circumstances there is always a map f : L(G) → L(H) of the limit sets inducing Φ. That is, we have $$fg(x)\, = \,\Phi (g)f(x)$$ (1) for all x ∊ L(G) and g ∊ G.

This short paper characterizes strictly convex sets by the uniqueness of support points (such points are called unique support points or exposed points) under appropriate assumptions. A class of so...

A (3,6)-fullerene is a plane cubic graph whose faces are only triangles and hexagons. A connected graph G with at least $$2n+2$$ vertices is said to be n-extendable if it has n independent edges and every set of n independent edges extends to a perfect matching of G. A graph G is said to be bicritical if for every pair of distinct vertices u and v, $$G-u-v$$ has a perfect matching. It is known that every (3,6)-fullerene is 1-extendable, but not 2-extendable. In this short paper, we show that a (3,6)-fullerene G is bicritical if and only if G has the connectivity 3 and is not isomorphic to one graph (2,4,2). As a surprising consequence we have that a (3,6)-fullerene is bicritical if and only if each hexagonal face is resonant.

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}.

Let $$ (T_{n})_{n\ge 0} $$ ( T n ) n ≥ 0 be the sequence of Tribonacci numbers defined by $$ T_0=0 $$ T 0 = 0 , $$ T_1=T_2=1$$ T 1 = T 2 = 1 , and $$ T_{n+3}= T_{n+2}+T_{n+1} +T_n$$ T n + 3 = T n + 2 + T n + 1 + T n for all $$ n\ge 0 $$ n ≥ 0 . In this note, we use of lower bounds for linear forms in logarithms of algebraic numbers and the Baker-Davenport reduction procedure to find all Tribonacci numbers that are concatenations of two repdigits.

For many tested cases of identical space-filling polyhedra, such as the space-group-specific asymmetric units or Dirichlet domains, the numbers of their faces (Fn), edges (En) and vertices (Vn), in each case normalized by division by the multiplicity of their (potentially special) symmetry position, fulfill a modified Euler’s formula Fn − En + Vn = 1., The famous Euler’s rule for three-dimensional polyhedra, F − E + V = 2 (F, E and V are the numbers of faces, edges and vertices, respectively), when extended to many tested cases of space-filling polyhedra such as the asymmetric unit (ASU), takes the form Fn − En + Vn = 1, where Fn, En and Vn enumerate the corresponding elements, normalized by their multiplicity, i.e. by the number of times they are repeated by the space-group symmetry. This modified formula holds for the ASUs of all 230 space groups and 17 two-dimensional planar groups as specified in the International Tables for Crystallography, and for a number of tested Dirichlet domains, suggesting that it may have a general character. The modification of the formula stems from the fact that in a symmetrical space-filling arrangement the polyhedra (such as the ASU) have incomplete bounding elements (faces, edges, vertices), since they are shared (in various degrees) with the space-filling neighbors.

The Wiener polarity index Wp(G) of a graph G is the number of unordered pairs of vertices {u,?v} in G such that the distance between u and v is equal to 3. Very recently, Zhang and Hu studied the Wiener polarity index in Y. Zhang, Y. Hu, 2016 38. In this short paper, we establish an upper bound on the Wiener polarity index in terms of Hosoya index and characterize the corresponding extremal graphs. Moreover, we obtain Nordhaus-Gaddum-type results for Wp(G). Our lower bound on W p ( G ) + W p ( G ? ) is always better than the previous lower bound given by Zhang and Hu.

In this short paper, we determine the minimal generating set of 1-generator generalized quasi-cyclic codes over ź4$\mathbb {Z}_{4}$. We also determine their rank and introduce a lower bound for the minimum distance of free 1-generator generalized quasi-cyclic codes. Further, we construct some new ź4$\mathbb {Z}_{4}$-linear codes and we obtain some good binary nonlinear codes using the usual Gray map.

A graph is edge-primitive if its automorphism group acts primitively on the edge set. In this short paper, we prove that a finite 2-arc-transitive edge-primitive graph has almost simple automorphism group if it is neither a cycle nor a complete bipartite graph. We also present two examples of such graphs, which are 3-arc-transitive and have faithful vertex-stabilizers.

Consider k-binomial equivalence: two finite words are equivalent if they share the same subwords of length at most k with the same multiplicities. With this relation, the k-binomial complexity of an infinite word x maps the integer n to the number of pairwise non-equivalent factors of length n occurring in x. In this paper based on the notion of template introduced by Currie et al., we show that, for all k ≥ 2 , the k-binomial complexity of the Tribonacci word coincides with its usual factor complexity p ( n ) = 2 n + 1 . A similar result was already known for Sturmian words, but the proof relies on completely different techniques that seemingly could not be applied for Tribonacci.

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.

Let H be a fixed forbidden graph and let f be a function of n. Denote by RT(n,H,f(n)) the maximum number of edges a graph G on n vertices can have without containing H as a subgraph and also without having at least f(n) independent vertices. The problem of estimating RT(n,H,f(n)) is one of the central questions of so-called Ramsey–Turán theory.In their recent paper (Discrete Math. 229 (2001) 293–340), Simonovits and Sós gave an excellent survey of this theory and mentioned some old and new interesting open questions. In this short paper we obtain some new bounds for Ramsey–Turán-type problems. These results give partial answers for some of the questions.

Let $G=(V,E)$ be a connected finite graph. In this short paper, we reinvestigate the Kazdan-Warner equation $$\Delta u=c-he^u$$ with $cc>c_-(h)$ and it is not solvable for $c-\infty$, then there exists at least one solution to the Kazdan-Warner equation with $c=c_-(h)$., Comment: 7 pages

A uniform geometric/algebraic approach to the Penrose and Taylor–Socolar hexagonal tilings is given, which clarifies their construction and the way in which they are inter-related., The intimate relationship between the Penrose and the Taylor–Socolar tilings is studied, within both the context of double hexagon tiles and the algebraic context of hierarchical inverse sequences of triangular lattices. This unified approach produces both types of tilings together, clarifies their relationship and offers straightforward proofs of their basic properties.

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 study the Sobolev function property of the Rayleigh 's quotient δ ( q ) = inf u ∈ E 1 , p ( U ) ⁡ ‖ u ‖ ∇ p ‖ u ‖ q , ∂ U p as a function of q ∈ [ 1 , p ⁎ ] for p ⁎ = p ( N − 1 ) N − p when p ∈ ( 1 , N ) , as well as the asymptotic behavior of positive solutions with minimal energy of the following problem − Δ p u = 0 in U , subject to | ∇ u | p − 2 ∂ u ∂ ν = λ | u | q − 2 u on ∂ U to the first p -harmonic Steklov eigenpair on an exterior region U ⊊ R N when N ≥ 3 .

A Boolean function in \begin{document}$ n $\end{document} variables is 2-rotation symmetric if it is invariant under even powers of \begin{document}$ \rho(x_1, \ldots, x_n) = (x_2, \ldots, x_n, x_1) $\end{document} , but not under the first power (ordinary rotation symmetry); we call such a function a 2-function. A 2-function is called monomial rotation symmetric (MRS) if it is generated by applying powers of \begin{document}$ \rho^2 $\end{document} to a single monomial. If the quartic MRS 2-function in \begin{document}$ 2n $\end{document} variables has a monomial \begin{document}$ x_1 x_q x_r x_s $\end{document} , then we use the notation \begin{document}$ {2-}(1,q,r,s)_{2n} $\end{document} for the function. A detailed theory of equivalence of quartic MRS 2-functions in \begin{document}$ 2n $\end{document} variables was given in a \begin{document}$ 2020 $\end{document} paper by Cusick, Cheon and Dougan. This theory divides naturally into two classes, called \begin{document}$ mf1 $\end{document} and \begin{document}$ mf2 $\end{document} in the paper. After describing the equivalence classes, the second major problem is giving details of the linear recursions that the Hamming weights for any sequence of functions \begin{document}$ {2-}(1,q,r,s)_{2n} $\end{document} (with \begin{document}$ q say), \begin{document}$ n = s, s+1, \ldots $\end{document} can be shown to satisfy. This problem was solved for the \begin{document}$ mf1 $\end{document} case only in the \begin{document}$ 2020 $\end{document} paper. Using new ideas about "short" functions, Cusick and Cheon found formulas for the \begin{document}$ mf2 $\end{document} weights in a \begin{document}$ 2021 $\end{document} sequel to the \begin{document}$ 2020 $\end{document} paper. In this paper the actual recursions for the weights in the \begin{document}$ mf2 $\end{document} case are determined.

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The Matching Cut problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H - Free Coloring if none of the color classes contain H as an induced subgraph. The H - Free Chromatic Number of G is the minimum number of colors required for an H - Free Coloring of G . Both The Matching Cut problem and the H - Free Coloring problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f ( | | φ | | , t ) n O ( 1 ) , where | | φ | | is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f ( | | φ | | , t ) on | | φ | | can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for Matching Cut problem and H - Free Coloring problem, parameterized by the tree-width of G . The single exponential FPT algorithm for the Matching Cut problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H -free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G .

An {\em orientation} of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The $n$-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The $n$-star graph $S_n$ consists of $n!$ vertices, each labelled with a distinct permutation of $[n]$. Two vertices are adjacent if their labels differ exactly in the first and one other position. $S_n$ is an $(n-1)$-regular, vertex-transitive graph with diameter $\lfloor 3(n-1)/2 \rfloor$. Orientations of $S_n$, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph $\overrightarrow{S_n}$ is at most $\lceil{5n/2}\rceil + 2$. In this paper, we propose a new distributed routing algorithm for the same $\overrightarrow{S_n}$ analysed by Fujita, which routes a packet from any node $s$ to any node $t$ at an undirected distance $d$ from $s$ using at most $\min\{4d+4, 2n+4\}$ hops. This shows that the (directed) diameter of $\overrightarrow{S_n}$ is at most $2n+4$. We also show that the diameter of $\overrightarrow{S_n}$ is at least $2n$ when $n \geq 7$, thereby showing that our upper bound is tight up to an additive factor., Full version of the paper to be presented in CALDAM 2020

cited By (since 1996)0; Article in Press; International audience; This paper deals with the implementation of an additive linear model for mixture of mixtures including major and minor components. Experimental designs, derived from designs for qualitative factors, are built for the two classical cases of type A or type B mixtures. With such designs the determination of the least square estimators of the model parameters or the determination of the D-efficiency can be achieved in an easy way. © 2014 Springer-Verlag Berlin Heidelberg.

For many algorithmic problems on graphs of treewidth t , a standard dynamic programming approach gives an algorithm with time and space complexity 2O(t)⋅nO(1) . It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form 2O(d)⋅nO(1) , where d is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity 2O(tlogt)⋅nO(1) on graphs of treewidth t , but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. (FOCS’11) introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity 2O(t)⋅nO(1) . Recently, Hegerfeld and Kratsch (STACS’20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time 2O(d)⋅nO(1) and polynomial space usage. However, a number of important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper we clarify the situation by showing that Hamiltonian Cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit 5d⋅nO(1) -time and polynomial space algorithms on graphs of treedepth d . The algorithms are randomized Monte Carlo with only false negatives.

It was shown by Mukai that the maximum order of a finite group acting faithfully and symplectically on a K3 surface is $960$ and that the group is isomorphic to the group $M\_{20}$. Then Kondo showed that the maximum order of a finite group acting faithfully on a K3 surface is $3\,840$ and this group contains the Mathieu group $M\_{20}$ with index four. Kondo also showed that there is a unique K3 surface on which this group acts faithfully, which is the Kummer surface $\Km(E\_i\times E\_i)$. In this paper we describe two more K3 surfaces admitting a big finite automorphism group of order $1\,920$, both groups contains $M\_{20}$ as a subgroup of index 2. We show moreover that these two groups and the two K3 surfaces are unique. This result was shown independently by S. Brandhorst and K. Hashimoto in a forthcoming paper, with the aim of classifying all the finite groups acting faithfully on K3 surfaces with maximal symplectic part., 15 pages

Carsten Thomassen and I proved that in any graph G , the number of cycles containing a specified edge as well as all the vertices of odd degree is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd degree it is Andrew Thomason’s extension of Smith’s Theorem. Our proof was not algorithmic. In this paper, I extend Thomason’s algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices. Kenneth Berman extended Thomason’s Theorem to spanning trees: he proved that if T is a spanning tree such that the degree of every vertex in G − E ( T ) is odd, then there is an even number of spanning trees of G with the same degree as T at each vertex. In this paper, I give a common generalization of all of these theorems to a parity theorem about “good” trees in general graphs. My proof provides an algorithm for finding a second “good” tree.