Chvátal–Erdös Type Conditions for Hamiltonicity of Claw-Free Graphs

For a graph H, let \(\alpha (H)\) and \(\alpha ^{\prime }(H)\) denote the independence number and the matching number, respectively. Let \(k\ge 2\) and \(r>0\) be given integers. We prove that if H is a k-connected claw-free graph with \(\alpha (H)\le r\), then either H is Hamiltonian or the Ryjá c? ek’s closure \(cl(H)=L(G)\) where G can be contracted to a k-edge-connected \(K_3\)-free graph \(G_0^{\prime }\) with \(\alpha ^{\prime }(G_0^{\prime })\le r\) and \(|V(G_0^{\prime })|\le \max \{3r-5, 2r+1\}\) if \(k\ge 3\) or \(|V(G_0^{\prime })|\le \max \{4r-5, 2r+1\}\) if \(k=2\) and \(G_0^{\prime }\) does not have a dominating closed trail containing all the vertices that are obtained by contracting nontrivial subgraphs. As corollaries, we prove the following:

1. (a)
   A 2-connected claw-free graph H with \(\alpha (H)\le 3\) is either Hamiltonian or \(cl(H)=L(G)\) where G is obtained from \(K_{2,3}\) by adding at least one pendant edge on each degree 2 vertex;
    
2. (b)
   A 3-connected claw-free graph H with \(\alpha (H)\le 7\) is either Hamiltonian or \(cl(H)=L(G)\) where G is a graph with \(\alpha ^{\prime }(G)=7\) that is obtained from the Petersen graph P by adding some pendant edges or subdividing some edges of P.
    

Case (a) was first proved by Xu et al. [19]. Case (b) is an improvement of a result proved by Flandrin and Li [12]. For a given integer \(r>0\), the number of graphs of order at most \(\max \{4r-5, 2r+1\}\) is fixed. The main result implies that improvements to case (a) or (b) by increasing the value of r and by enlarging the collection of exceptional graphs can be obtained with the help of a computer. Similar results involved degree or neighborhood conditions are also discussed.

     

Brownian Paths Homogeneously Distributed in Space: Percolation Phase Transition and Uniqueness of the Unbounded Cluster

We consider a continuum percolation model on \(\mathbb {R}^d\), \(d\ge 1\). For \(t,\lambda \in (0,\infty )\) and \(d\in \{1,2,3\}\), the occupied set is given by the union of independent Brownian paths running up to time t whose initial points form a Poisson point process with intensity \(\lambda >0\). When \(d\ge 4\), the Brownian paths are replaced by Wiener sausages with radius \(r>0\). We establish that, for \(d=1\) and all choices of t, no percolation occurs, whereas for \(d\ge 2\), there is a non-trivial percolation transition in t, provided \(\lambda \) and r are chosen properly. The last statement means that \(\lambda \) has to be chosen to be strictly smaller than the critical percolation parameter for the occupied set at time zero (which is infinite when \(d\in \{2,3\}\), but finite and dependent on r when \(d\ge 4\)). We further show that for all \(d\ge 2\), the unbounded cluster in the supercritical phase is unique. Along the way a finite box criterion for non-percolation in the Boolean model is extended to radius distributions with an exponential tail. This may be of independent interest. The present paper settles the basic properties of the model and should be viewed as a springboard for finer results.     

Dimensions of fibers of generic continuous maps

In an earlier paper Buczolich, Elekes, and the author described the Hausdorff dimension of the level sets of a generic real-valued continuous function (in the sense of Baire category) defined on a compact metric space K by introducing the notion of topological Hausdorff dimension. Later on, the author extended the theory for maps from K to \({\mathbb {R}}^n\). The main goal of this paper is to generalize the relevant results for topological and packing dimensions and to obtain new results for sufficiently homogeneous spaces K even in the case case of Hausdorff dimension. Let K be a compact metric space and let us denote by \(C(K,{\mathbb {R}}^n)\) the set of continuous maps from K to \({\mathbb {R}}^n\) endowed with the maximum norm. Let \(\dim _{*}\) be one of the topological dimension \(\dim _T\), the Hausdorff dimension \(\dim _H\), or the packing dimension \(\dim _P\). Define

$$\begin{aligned} d_{*}^n(K)=\inf \left\{ \dim _{*}(K{\setminus } F): F\subset K \text { is } \sigma \text {-compact with } \dim _T F<n\right\} . \end{aligned}$$

We prove that \(d^n_{*}(K)\) is the right notion to describe the dimensions of the fibers of a generic continuous map \(f\in C(K,{\mathbb {R}}^n)\). In particular, we show that \(\sup \{\dim _{*}f^{-1}(y): y\in {\mathbb {R}}^n\} =d^n_{*}(K)\) provided that \(\dim _T K\ge n\), otherwise every fiber is finite. Proving the above theorem for packing dimension requires entirely new ideas. Moreover, we show that the supremum is attained on the left hand side of the above equation. Assume \(\dim _T K\ge n\). If K is sufficiently homogeneous, then we can say much more. For example, we prove that \(\dim _{*}f^{-1}(y)=d^n_{*}(K)\) for a generic \(f\in C(K,{\mathbb {R}}^n)\) for all \(y\in {{\mathrm{int}}}f(K)\) if and only if \(d^n_{*}(U)=d^n_{*}(K)\) or \(\dim _T U<n\) for all open sets \(U\subset K\). This is new even if \(n=1\) and \(\dim _{*}=\dim _H\). It is known that for a generic \(f\in C(K,{\mathbb {R}}^n)\) the interior of f(K) is not empty. We augment the above characterization by showing that \(\dim _T \partial f(K)=\dim _H \partial f(K)=n-1\) for a generic \(f\in C(K,{\mathbb {R}}^n)\). In particular, almost every point of f(K) is an interior point. In order to obtain more precise results, we use the concept of generalized Hausdorff and packing measures, too.

     

Metacyclic groups as automorphism groups of compact Riemann surfaces

Let X be a compact Riemann surface of genus \(g\ge 2\), and let G be a subgroup of \(\mathrm{Aut}(X)\). We show that if the Sylow 2-subgroups of G are cyclic, then \(|G|\le 30(g-1)\). If all Sylow subgroups of G are cyclic, then, with two exceptions, \(|G|\le 10(g-1)\). More generally, if G is metacyclic, then, with one exception, \(|G|\le 12(g-1)\). Each of these bounds is attained for infinitely many values of g.     

Packing Chromatic Number of Base-3 Sierpiński Graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least \(i+1\). Let \(S^n\) be the base-3 Sierpiński graph of dimension n. It is proved that \(\chi _{\rho }(S^1) = 3\), \(\chi _{\rho }(S^2) = 5\), \(\chi _{\rho }(S^3) = \chi _{\rho }(S^4) = 7\), and that \(8\le \chi _\rho (S^n) \le 9\) holds for any \(n\ge 5\).     

Finite 2-Geodesic Transitive Abelian Cayley Graphs

In this paper, we first give a classification of the family of 2-geodesic transitive abelian Cayley graphs. Let \(\Gamma \) be such a graph which is not 2-arc transitive. It is shown that one of the following holds: (1) \(\Gamma \cong \mathrm{K}_{m[b]}\) for some \(m\ge 3\) and \(b\ge 2\); (2) \(\Gamma \) is a normal Cayley graph of an elementary abelian group; (3) \(\Gamma \) is a cover of Cayley graph \(\Gamma _K\) of an abelian group T / K, where either \(\Gamma _K\) is complete arc transitive or \(\Gamma _K\) is 2-geodesic transitive of girth 3, and A / K acts primitively on \(V(\Gamma _K)\) of type Affine or Product Action. Second, we completely determine the family of 2-geodesic transitive circulants.     

Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs

Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).     

The crank moments weighted by the parity of cranks

In this note, we introduce the 2kth crank moment \(\mu _{2k}(-1,n)\) weighted by the parity of cranks and show that \((-1)^n \mu _{2k}(-1,n)>0\) for \(n\ge k \ge 0\). When \(k=0\), the inequality \((-1)^n \mu _{2k}(-1,n)>0\) reduces to Andrews and Lewis’s inequality \((-1)^n(M_e(n)-M_o(n))>0\) for \(n\ge 0\), where \(M_e(n)\) (resp. \(M_o(n)\)) denotes the number of partitions of n with even (resp. odd) crank. Several generating functions of \(\mu _{2k}(-1,n)\) are also studied in order to show the positivity of \((-1)^n\mu _{2k}(-1,n)\).     

Spectral density estimates with partial symmetries and an application to Bahri–Lions-type results

We are concerned with the existence of infinitely many solutions for the problem \(-\Delta u=|u|^{p-2}u+f\) in \(\Omega \), \(u=u_0\) on \(\partial \Omega \), where \(\Omega \) is a bounded domain in \(\mathbb {R}^N\), \(N\ge 3\). This can be seen as a perturbation of the problem with \(f=0\) and \(u_0=0\), which is odd in u. If \(\Omega \) is invariant with respect to a closed strict subgroup of O(N), then we prove infinite existence for all functions f and \(u_0\) in certain spaces of invariant functions for a larger range of exponents p than known before. In order to achieve this, we prove Lieb–Cwikel–Rosenbljum-type bounds for invariant potentials on \(\Omega \), employing improved Sobolev embeddings for spaces of invariant functions.     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

A new theorem on the prime-counting function

For \(x>0\), let \(\pi (x)\) denote the number of primes not exceeding x. For integers a and \(m>0\), we determine when there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). In particular, we show that, for any integers \(m>2\) and \(a\leqslant \lceil e^{m-1}/(m-1)\rceil \), there is an integer \(n>1\) with \(\pi (n)=(n+a)/m\). Consequently, for any integer \(m>4\), there is a positive integer n with \(\pi (mn)=m+n\). We also pose several conjectures for further research; for example, we conjecture that, for each \(m=1,2,3,\ldots \), there is a positive integer n such that \(m+n\) divides \(p_m+p_n\), where \(p_k\) denotes the k-th prime.     

Sandwich semigroups in locally small categories I: foundations

Fix (not necessarily distinct) objects i and j of a locally small category S, and write \(S_{ij}\) for the set of all morphisms \(i\rightarrow j\). Fix a morphism \(a\in S_{ji}\), and define an operation \(\star _a\) on \(S_{ij}\) by \(x\star _ay=xay\) for all \(x,y\in S_{ij}\). Then \((S_{ij},\star _a)\) is a semigroup, known as a sandwich semigroup, and denoted by \(S_{ij}^a\). This article develops a general theory of sandwich semigroups in locally small categories. We begin with structural issues such as regularity, Green’s relations and stability, focusing on the relationships between these properties on \(S_{ij}^a\) and the whole category S. We then identify a natural condition on a, called sandwich regularity, under which the set \({\text {Reg}}(S_{ij}^a)\) of all regular elements of \(S_{ij}^a\) is a subsemigroup of \(S_{ij}^a\). Under this condition, we carefully analyse the structure of the semigroup \({\text {Reg}}(S_{ij}^a)\), relating it via pullback products to certain regular subsemigroups of \(S_{ii}\) and \(S_{jj}\), and to a certain regular sandwich monoid defined on a subset of \(S_{ji}\); among other things, this allows us to also describe the idempotent-generated subsemigroup \(\mathbb E(S_{ij}^a)\) of \(S_{ij}^a\). We also study combinatorial invariants such as the rank (minimal size of a generating set) of the semigroups \(S_{ij}^a\), \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\); we give lower bounds for these ranks, and in the case of \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\) show that the bounds are sharp under a certain condition we call MI-domination. Applications to concrete categories of transformations and partial transformations are given in Part II.     

Packing chromatic number versus chromatic and clique number

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in [k]\), where each \(V_i\) is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that \(\omega (G) = a\), \(\chi (G) = b\), and \(\chi _{\rho }(G) = c\). If so, we say that (a, b, c) is realizable. It is proved that \(b=c\ge 3\) implies \(a=b\), and that triples \((2,k,k+1)\) and \((2,k,k+2)\) are not realizable as soon as \(k\ge 4\). Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on \(\chi _{\rho }(G)\) in terms of \(\Delta (G)\) and \(\alpha (G)\) is also proved.     

On the eigenvalues and spectral radius of starlike trees

Let \(k\ge 1\) and \(n_1,\ldots ,n_k\ge 1\) be some integers. Let \(S(n_1,\ldots ,n_k)\) be a tree T such that T has a vertex v of degree k and \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1},\ldots ,P_{n_k}\), that is \(T{\setminus } v\cong P_{n_1}\cup \cdots \cup P_{n_k}\) so that every neighbor of v in T has degree one or two. The tree \(S(n_1,\ldots ,n_k)\) is called starlike tree, a tree with exactly one vertex of degree greater than two, if \(k\ge 3\). In this paper we obtain the eigenvalues of starlike trees. We find some bounds for the largest eigenvalue (for the spectral radius) of starlike trees. In particular we prove that if \(k\ge 4\) and \(n_1,\ldots ,n_k\ge 2\), then \(\frac{k-1}{\sqrt{k-2}}<\lambda _1(S(n_1,\ldots ,n_k))<\frac{k}{\sqrt{k-1}}\), where \(\lambda _1(T)\) is the largest eigenvalue of T. Finally we characterize all starlike trees that all of whose eigenvalues are in the interval \((-2,2)\).     

A generalization of the normal rational curve in $$\mathop {\mathrm{PG}}(d,q^n)$$ and its associated non-linear MRD codes

Let A and B be two points of \(\mathop {\mathrm{PG}}(d,q^n)\) and let \(\Phi \) be a collineation between the stars of lines with vertices A and B, that does not map the line AB into itself. In this paper we prove that if \(d=2\) or \(d\ge 3\) and the lines \(\Phi ^{-1}(AB), AB, \Phi (AB) \) are not in a common plane, then the set \(\mathcal{C}\) of points of intersection of corresponding lines under \(\Phi \) is the union of \(q-1\) scattered \({\mathbb {F}}_{q}\)-linear sets of rank n together with \(\{A,B\}\). As an application we will construct, starting from the set \(\mathcal{C}\), infinite families of non-linear \((d+1, n, q;d-1)\)-MRD codes, \(d\le n-1\), generalizing those recently constructed in Cossidente et al. (Des Codes Cryptogr 79:597–609, 2016) and Durante and Siciliano (Electron J Comb, 2017).     

Few associative triples,isotopisms and groups

Let Q be a quasigroup. For \(\alpha ,\beta \in S_Q\) let \(Q_{\alpha ,\beta }\) be the principal isotope \(x*y = \alpha (x)\beta (y)\). Put \(\mathbf a(Q)= |\{(x,y,z)\in Q^3;\) \(x(yz)) = (xy)z\}|\) and assume that \(|Q|=n\). Then \(\sum _{\alpha ,\beta }\mathbf a(Q_{\alpha ,\beta })/(n!)^2 = n^2(1+(n-1)^{-1})\), and for every \(\alpha \in S_Q\) there is \(\sum _\beta \mathbf a(Q_{\alpha ,\beta })/n! = n(n-1)^{-1}\sum _x(f_x^2-2f_x+n)\ge n^2\), where \(f_x=|\{y\in Q;\) \( y = \alpha (y)x\}|\). If G is a group and \(\alpha \) is an orthomorphism, then \(\mathbf a(G_{\alpha ,\beta })=n^2\) for every \(\beta \in S_Q\). A detailed case study of \(\mathbf a(G_{\alpha ,\beta })\) is made for the situation when \(G = \mathbb Z_{2d}\), and both \(\alpha \) and \(\beta \) are “natural” near-orthomorphisms. Asymptotically, \(\mathbf a(G_{\alpha ,\beta })>3n\) if G is an abelian group of order n. Computational results: \(\mathbf a(7) = 17\) and \(\mathbf a(8) \le 21\), where \(\mathbf a(n) = \min \{\mathbf a(Q);\) \( |Q|=n\}\). There are also determined minimum values for \(\mathbf a(G_{\alpha ,\beta })\), G a group of order \(\le 8\).     

Monochromatic Solutions for Multi-Term Unknowns

Given integers \(k\ge 2\), \(n \ge 2\), \(m \ge 2\) and \( a_1,a_2,\ldots ,a_m \in {\mathbb {Z}}{\backslash }{\{0\}}\), and let \(f(z)= \sum _{j=0}^{n}c_jz^j\) be a polynomial of integer coefficients with \(c_n>0\) and \((\sum _{i=1}^ma_i)|f(z)\) for some integer z. For a k-coloring of \([N]=\{1,2,\ldots ,N\}\), we say that there is a monochromatic solution of the equation \(a_1x_1+a_2x_2+\cdots +a_mx_m=f(z)\) if there exist pairwise distinct \(x_1,x_2,\ldots ,x_m\in [N]\) all of the same color such that the equation holds for some \(z\in \mathbb {Z}\). Problems of this type are often referred to as Ramsey-type problems. In this paper, it is shown that if \(a_i>0\) for \(1\le i\le m\), then there exists an integer \(N_0=N(k,m,n)\) such that for \(N\ge N_0\), each k-coloring of [N] contains a monochromatic solution \(x_1,x_2,\ldots ,x_m\) of the equation \(a_1x_1+a_2x_2+ \cdots +a_mx_m= f(z)\). Moreover, if n is odd and there are \(a_i\) and \(a_j\) such that \(a_ia_j<0\) for some \(1 \le i\ne j\le m\), then the assertion holds similarly.     

Solvability of Minimal Graph Equation Under Pointwise Pinching Condition for Sectional Curvatures

We study the asymptotic Dirichlet problem for the minimal graph equation on a Cartan–Hadamard manifold M whose radial sectional curvatures outside a compact set satisfy an upper bound

$$\begin{aligned} K(P)\le - \frac{\phi (\phi -1)}{r(x)^2} \end{aligned}$$

and a pointwise pinching condition

$$\begin{aligned} |K(P) |\le C_K|K(P') | \end{aligned}$$

for some constants \(\phi >1\) and \(C_K\ge 1\), where P and \(P'\) are any 2-dimensional subspaces of \(T_xM\) containing the (radial) vector \(\nabla r(x)\) and \(r(x)=d(o,x)\) is the distance to a fixed point \(o\in M\). We solve the asymptotic Dirichlet problem with any continuous boundary data for dimensions \(n=\dim M>4/\phi +1\).

     

A generalization of the Dedekind–MacNeille completion

In this paper we introduce the notion of \(Z_{\delta }\)-continuity as a generalization of precontinuity, complete continuity and \(s_{2}\)-continuity, where Z is a subset selection. And for each poset P, a closure space \(Z^{c}_{\delta }(P)\) arises naturally. For any subset system Z, we define a new type of completion, called \(Z_{\delta }\)-completion, extending each poset P to a Z-complete poset. The main results are: (1) if a subset system Z is subset-hereditary, then \(cl_{Z}(\Psi (P))\), the Z-closure of all principal ideals \(\Psi (P)\) of poset P in \(Z^{c}_{\delta }(P)\), is a \(Z_{\delta }\)-completion of P and \(Z^{c}_{\delta }(P) \cong Z^{c}_{\delta }(cl_{Z}(\Psi (P)))\); (2) let Z be an HUL-system and P a \(Z_{\delta }\)-continuous poset, then the \(Z_{\delta }\)-completion of P is also \(Z_{\delta }\)-continuous, and a Z-complete poset L is a \(Z_{\delta }\)-completion of P iff P is an embedded \(Z_{\delta }\)-basis of L; (3) the Dedekind–MacNeille completion is a special case of the \(Z_{\delta }\)-completion.     

The Best Mixing Time for Random Walks on Trees

We characterize the extremal structures for mixing walks on trees that start from the most advantageous vertex. Let \(G=(V,E)\) be a tree with stationary distribution \(\pi \). For a vertex \(v \in V\), let \(H(v,\pi )\) denote the expected length of an optimal stopping rule from v to \(\pi \). The best mixing time for G is \(\min _{v \in V} H(v,\pi )\). We show that among all trees with \(|V|=n\), the best mixing time is minimized uniquely by the star. For even n, the best mixing time is maximized by the uniquely path. Surprising, for odd n, the best mixing time is maximized uniquely by a path of length \(n-1\) with a single leaf adjacent to one central vertex.