Search

Two permutations of $[n]=\{1,2 \ldots n\}$ are \textit{$k$-neighbor separated} if there are two elements that are neighbors in one of the permutations and that are separated by exactly $k-2$ other elements in the other permutation. Let the maximal number of pairwise $k$-neighbor separated permutations of $[n]$ be denoted by $P(n,k)$. In a previous paper, the authors have determined $P(n,3)$ for every $n$, answering a question of K\"orner, Messuti and Simonyi affirmatively. In this paper we prove that for every fixed positive integer $\ell $, $$P(n,2^\ell+1) = 2^{n-o(n)}. $$ We conjecture that for every fixed even $k$, $P(n,k)=2^{n-o(n)}$. We also show that this conjecture is asymptotically true in the following sense $$\lim_{k \rightarrow \infty} \lim_{n \rightarrow \infty} \sqrt[n]{P(n,k)}=2.$$ Finally, we show that for even $n$, $P(n,n)= 3n/2$.

For any symplectic manifold $${(M,\omega )}$$ , the set of Hamiltonian diffeomorphisms $${{\text {Ham}}^c(M,\omega )}$$ forms a group and $${{\text {Ham}}^c(M,\omega )}$$ contains an important subset $${{\text {Aut}}(M,\omega )}$$ which consists of time one flows of autonomous(time-independent) Hamiltonian vector fields on M. One might expect that $${{\text {Aut}}(M,\omega )}$$ is a very small subset of $${{\text {Ham}}^c(M,\omega )}$$ . In this paper, we estimate the size of the subset $${{\text {Aut}}(M,\omega )}$$ in $${C^{\infty }}$$ -topology and Hofer’s metric which was introduced by Hofer. Polterovich and Shelukhin proved that the complement $${{\text {Ham}}^c\backslash {\text {Aut}}(M,\omega )}$$ is a dense subset of $${{\text {Ham}}^c(M,\omega )}$$ in $${C^{\infty }}$$ -topology and Hofer’s metric if $${(M,\omega )}$$ is a closed symplectically aspherical manifold where Conley conjecture is established (Polterovich and Schelukhin in Sel Math 22(1):227–296, 2016). In this paper, we generalize above theorem to general closed symplectic manifolds and general conv! ex symplectic manifolds. So, we prove that the set of all non-autonomous Hamiltonian diffeomorphisms $${{\text {Ham}}^c\backslash {\text {Aut}}(M,\omega )}$$ is a dense subset of $${{\text {Ham}}^c(M,\omega )}$$ in $${C^{\infty }}$$ -topology and Hofer’s metric if $${(M,\omega )}$$ is a closed or convex symplectic manifold without relying on the solution of Conley conjecture.

The aim of this note is to provoke discussion concerning arithmetic properties of function $p_{d}(n)$ counting partitions of an positive integer $n$ into $d$-th powers, where $d\geq 2$. Besides results concerning the asymptotic behavior of $p_{d}(n)$ a little is known. In the first part of the paper, we prove certain congruences involving functions counting various types of partitions into $d$-th powers. The second part of the paper has experimental nature and contains questions and conjectures concerning arithmetic behavior of the sequence $(p_{d}(n))_{n\in\N}$. They based on our computations of $p_{d}(n)$ for $n\leq 10^5$ in case of $d=2$, and $n\leq 10^{6}$ for $d=3, 4, 5$., 8 pages, revised version will appear in Bull. Aust. Math. Society

Recently, Lutz and Stull used methods from algorithmic information theory to prove two new Marstrand-type projection theorems, concerning subsets of Euclidean space which are not assumed to be Borel, or even analytic. One of the theorems states that if $K \subset \mathbb{R}^{n}$ is any set with equal Hausdorff and packing dimensions, then $$ \dim_{\mathrm{H}} π_{e}(K) = \min\{\dim_{\mathrm{H}} K,1\} $$ for almost every $e \in S^{n - 1}$. Here $π_{e}$ stands for orthogonal projection to $\mathrm{span}(e)$. The primary purpose of this paper is to present proofs for Lutz and Stull's projection theorems which do not refer to information theoretic concepts. Instead, they will rely on combinatorial-geometric arguments, such as discretised versions of Kaufman's "potential theoretic" method, the pigeonhole principle, and a lemma of Katz and Tao. A secondary purpose is to slightly generalise Lutz and Stull's theorems: the versions in this paper apply to orthogonal projections to $m$-planes in $\mathbb{R}^{n}$, for all $0 < m < n$., 11 pages. v2: Incorporated referee suggestions

In 1970, Chou showed there are $|\mathbb{N}^*| = 2^{2^\mathbb{N}}$ topologically invariant means on $L_\infty(G)$ for any noncompact, $\sigma$-compact amenable group. Over the following 25 years, the sizes of the sets of topologically invariant means on $L_\infty(G)$ and $VN(G)$ were determined for any locally compact group. Each paper on a new case reached the same conclusion -- "the cardinality is as large as possible" -- but a unified proof never emerged. In this paper, I show $L_1(G)$ and $A(G)$ always contain orthogonal nets converging to invariance. An orthogonal net indexed by $\Gamma$ has $|\Gamma^*|$ accumulation points, where $|\Gamma^*|$ is determined by ultrafilter theory. Among a smattering of other results, I prove Paterson's conjecture that left and right topologically invariant means on $L_\infty(G)$ coincide iff $G$ has precompact conjugacy classes., Comment: 10 pages, completely rewritten from v2

In part I of this paper we studied additive decomposability of the set F y of the y -smooth numbers and the multiplicative decomposability of the shifted set G y = F y + { 1 } . In this paper, focusing on the case of ’large’ functions y , we continue the study of these problems. Further, we also investigate a problem related to the m-decomposability of k -term sumsets, for arbitrary k .

In this paper, we study the spectrality and frame-spectrality of exponential systems of the type $$E(\Lambda ,\varphi ) = \{e^{2\pi i \lambda \cdot \varphi (x)}: \lambda \in \Lambda \}$$ where the phase function $$\varphi $$ is a Borel measurable which is not necessarily linear. A complete characterization of pairs $$(\Lambda ,\varphi )$$ for which $$E(\Lambda ,\varphi )$$ is an orthogonal basis or a frame for $$L^{2}(\mu )$$ is obtained. In particular, we show that the middle-third Cantor measures and the unit disc, each admits an orthogonal basis with a certain non-linear phase. Under a natural regularity condition on the phase functions, when $$\mu $$ is the Lebesgue measure on [0, 1] and $$\Lambda = {{\mathbb {Z}}},$$ we show that only the standard phase functions $$\varphi (x) = \pm x$$ are the only possible functions that give rise to orthonormal bases. Surprisingly, however we prove that there exist a greater degree of flexibility, even for continuously differentiable phase functions in higher dimensions. For instance, we were able to describe a large class of functions $$\varphi $$ defined on $${{\mathbb {R}}}^{d}$$ such that the system $$E(\Lambda ,\varphi )$$ is an orthonormal basis for $$L^{2}[0,1]^{d}$$ when $$d\ge 2.$$ Moreover, we discuss how our results apply to the discretization problem of unitary representations of locally compact groups for the construction of orthonormal bases. Finally, we conclude the paper by stating several open problems.

In this paper, we study large $m$ asymptotics of the $l^1$ minimal $m$-partition problem for Dirichlet eigenvalue. For any smooth domain $\Omega\in \mathbb{R}^n$ such that $|\Omega|=1$, we prove that the limit $\lim\limits_{m\rightarrow\infty}l_m^1(\Omega)=c_0$ exists, and the constant $c_0$ is independent of the shape of $\Omega$. Here $l_m^1(\Omega)$ denotes the minimal value of the normalized sum of the first Laplacian eigenvalues for any $m$-partition of $\Omega$., Comment: This paper has been accepted for publication in SCIENCE CHINA Mathematics

In the following paper, one studies, given a bounded, connected open set $\Omega$ $\subseteq$ R n , $\kappa$ > 0, a positive Radon measure $\mu$ 0 in $\Omega$ and a (signed) Radon measure $\mu$ on $\Omega$ satisfying $\mu$($\Omega$) = 0 and |$\mu$| $\kappa$$\mu$ 0 , the possibility of solving the equation div u = $\mu$ by a vector field u satisfying |u| $\kappa$w on $\Omega$ (where w is an integrable weight only related to the geometry of $\Omega$ and to $\mu$ 0), together with a mild boundary condition. This extends results obtained in [4] for the equation div u = f , improving them on two aspects: one works here with the divergence equation with measure data, and also construct a weight w that relies in a softer way on the geometry of $\Omega$, improving its behavior (and hence the a priori behavior of the solution we construct) substantially in some instances. The method used in this paper follows a constructive approach of Bogovskii type.

We use hypergeometric sheaves on $G_m/F_q$, which are particular sorts of rigid local systems, to construct explicit local systems whose arithmetic and geometric monodromy groups are the finite general linear groups $GL_n(q)$ for any $n \ge 2$ and and any prime power $q$, so long as $q > 3$ when $n=2$. This paper continues a program of finding simple (in the sense of simple to remember) families of exponential sums whose monodromy groups are certain finite groups of Lie type, cf. [Gr], [KT1], [KT2], [KT3] for (certain) finite symplectic and unitary groups, or certain sporadic groups, cf. [KRL], [KRLT1], [KRLT2], [KRLT3]. The novelty of this paper is obtaining $GL_n(q)$ in this hypergeometric way. A pullback construction then yields local systems on $A^1/F_q$ whose geometric monodromy groups are $SL_n(q)$. These turn out to recover a construction of Abhyankar., 26 pages

In our Novi Sad conference paper (1999) we described Dehn type surgeries of the famous Gieseking (1912) hyperbolic ideal simplex manifold $\mathcal{S}$, leading to compact fundamental domain $\mathcal{S}(k)$, $k = 2, 3, \dots$ with singularity geodesics of rotation order $k$, but as later turned out with cone angle $2(k-1)/k$. We computed also the volume of $S(k)$, tending to zero if $k$ goes to infinity. That time we naively thought that we obtained orbifolds with the above surprising property. As the reviewer of Math. Rev., Kevin P. Scannell (MR1770996 (2001g:57030)) rightly remarked, "this is in conflict with the well-known theorem of D. A. Kazhdan and G. A. Margulis (1968) and with the work of Thurston, describing the geometric convergence of orbifolds under large Dehn fillings". In this paper we refresh our previous publication. Correctly, we obtained cone manifolds (for $k > 2$), as A. D. Mednykh and V. S. Petrov (2006) kindly pointed out. We complete our discussion and derive the above cone manifold series (Gies.1 and Gies.2) in two geometrically equivalent form, by the half turn symmetry of any ideal simplex. Moreover we obtain a second orbifold series (Gies.3 and 4), tending to the regular ideal simplex as the original Gieseking manifold., 19 pages, 9 figures

In 1900, at the international congress of mathematicians, Hilbert claimed that the Riemann zeta function $\zeta(s)$ is not the solution of any algebraic ordinary differential equations on its region of analyticity. In 2015, Van Gorder considered the question of whether $\zeta(s)$ satisfies a non-algebraic differential equation and showed that it formally satisfies an infinite order linear differential equation. Recently, Prado and Klinger-Logan extended Van Gorder's result to show that the Hurwitz zeta function $\zeta(s,a)$ is also formally satisfies a similar differential equation \begin{equation*}\label{HurDE} T\left[\zeta (s,a) - \frac{1}{a^s}\right] = \frac{1}{(s-1)a^{s-1}}. \end{equation*} But unfortunately in the same paper they proved that the operator $T$ applied to Hurwitz zeta function $\zeta(s,a)$ does not converge at any point in the complex plane $\mathbb{C}$. In this paper, by defining $T_{p}^{a}$, a $p$-adic analogue of Van Gorder's operator $T,$ we establish an analogue of Prado and Klinger-Logan's differential equation satisfied by $\zeta_{p,E}(s,a)$ which is the $p$-adic analogue of the Hurwitz-type Euler zeta functions \begin{equation*}\label{HEZ} \zeta_E(s,a)=\sum_{n=0}^\infty\frac{(-1)^n}{(n+a)^s}. \end{equation*} In contrast with the complex case, due to the non-archimedean property, the operator $T_{p}^{a}$ applied to the $p$-adic Hurwitz-type Euler zeta function $\zeta_{p,E}(s,a)$ is convergent $p$-adically in the area of $s\in\mathbb{Z}_{p}$ with $s\neq 1$ and $a\in K$ with $|a|_{p}>1,$ where $K$ is any finite extension of $\mathbb{Q}_{p}$ with ramification index over $\mathbb{Q}_{p}$ less than $p-1.$, Comment: 18 pages. Final version. Dedicated to the memory of Prof. David Goss (1952-2017)

The first named author is supported in part by NSF grant DMS-1855464, ISF grant 281/17, and the Simons Foundation. The second named author is supported in part by an OTKA NK 104183 grant. The third named author is supported in part by a NSERC and an OTKA NK 104183 grant. In their seminal paper Erdös and Szemerédi formulated conjectures on the size of sumset and product set of integers. The strongest form of their conjecture is about sums and products along the edges of a graph. In this paper we show that this strong form of the Erdös-Szemerédi conjecture does not hold. We give upper and lower bounds on the cardinalities of sumsets, product sets, and ratio sets along the edges of graphs.

This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollob\'as independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the `ordered' complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural `unordered' analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Kor\'andi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{s,t}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Kor\'andi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$., Comment: Reflected minor suggestions from reviewers

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) $A = (A_{\alpha \beta} x_{\alpha \beta})$, where $A_{\alpha \beta}$ is a $2 \times 2$ matrix over a field $\mathbf{F}$ and $x_{\alpha \beta}$ is an indeterminate for $\alpha = 1,2,\dots, \mu$ and $\beta = 1,2, \dots, \nu$. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (1995). Recent interests in this problem lie in the connection with non-commutative Edmonds' problem by Ivanyos, Qiao, and Subrahamanyam (2018) and Garg, Gurvits, Oliveiva, and Wigderson (2019), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial $O((\mu \nu)^2 \min \{ \mu, \nu \})$-time algorithm for computing the symbolic rank of a $(2 \times 2)$-type generic partitioned matrix of size $2\mu \times 2\nu$. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos, Qiao, and Subrahamanyam for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of $A$ for an arbitrary field $\mathbf{F}$., Comment: This is a post-peer-review, pre-copyedit version of an article published in Mathematical Programming. The final authenticated version is available online at: https://doi.org/10.1007/s10107-021-01676-5

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as "tractable cases" of a general theory. As an outcome of this, we provide extensions of known results. We believe that this put these into next context and perspective. For example, we prove that the sparse--dense dichotomy exactly corresponds to random free graphons. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be "almost" studied component-wise. We also propose the structure of limits objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of {\em modeling} we introduce here. Our example is also the first "intermediate class" with explicitly defined limit structures., Comment: added journal reference

Amdeberhan's conjectures on the enumeration, the average size, and the largest size of $(n,n+1)$-core partitions with distinct parts have motivated many research on this topic. Recently, Straub and Nath-Sellers obtained formulas for the numbers of $(n, dn-1)$ and $(n, dn+1)$-core partitions with distinct parts, respectively. Let $X_{s,t}$ be the size of a uniform random $(s,t)$-core partition with distinct parts when $s$ and $t$ are coprime to each other. Some explicit formulas for the $k$-th moments $\mathbb{E} [X_{n,n+1}^k]$ and $\mathbb{E} [X_{2n+1,2n+3}^k]$ were given by Zaleski and Zeilberger when $k$ is small. Zaleski also studied the expectation and higher moments of $X_{n,dn-1}$ and conjectured some polynomiality properties concerning them in arXiv:1702.05634. Motivated by the above works, we derive several polynomiality results and asymptotic formulas for the $k$-th moments of $X_{n,dn+1}$ and $X_{n,dn-1}$ in this paper, by studying the beta sets of core partitions. In particular, we show that these $k$-th moments are asymptotically some polynomials of n with degrees at most $2k$, when $d$ is given and $n$ tends to infinity. Moreover, when $d=1$, we derive that the $k$-th moment $\mathbb{E} [X_{n,n+1}^k]$ of $X_{n,n+1}$ is asymptotically equal to $\left(n^2/10\right)^k$ when $n$ tends to infinity. The explicit formulas for the expectations $\mathbb{E} [X_{n,dn+1}]$ and $\mathbb{E} [X_{n,dn-1}]$ are also given. The $(n,dn-1)$-core case in our results proves several conjectures of Zaleski on the polynomiality of the expectation and higher moments of $X_{n,dn-1}$., Comment: This paper has been accepted for publication in SCIENCE CHINA Mathematics

In this paper, using computations done through the LiE software, we compare the tensor product of irreducible selfdual representations of the special linear group with those of classical groups to formulate some conjectures relating the two. In the process a few other phenomenon present themselves which we record as questions. More precisely, under the natural correspondence of irreducible finite dimensional selfdual representations of ${\rm SL}_{2n}({\mathbb C})$ with those of ${\rm Spin}_{2n+1}({\mathbb C})$, it is easy to see that if the tensor product of three irreducible representations of ${\rm Spin}_{2n+1}({\rm C})$ contains the trivial representation, then so does the tensor product of the corresponding representations of ${\rm SL}_{2n}({\rm C})$. The paper formulates a conjecture in the reverse direction. We also deal with the pair $({\rm SL}_{2n+1}({\rm C}), {\rm Sp}_{2n}({\rm C}))$., Comment: Revised version!

This paper considers random processes of the form $$X_{n+1}=a_nX_n+b_n\pmod p$$ where p is odd, $$X_0=0$$ , $$(a_0,b_0), (a_1,b_1), (a_2,b_2),\ldots $$ are i.i.d., and $$a_n$$ and $$b_n$$ are independent with $$P(a_n=2)=P(a_n=(p+1)/2)=1/2$$ and $$P(b_n=1)=P(b_n=0)=P(b_n=-1)=1/3$$ . This can be viewed as a multiplicatively symmetrized version of a random process of Chung, Diaconis, and Graham. This paper shows that order $$(\log p)^2$$ steps suffice for $$X_n$$ to be close to uniformly distributed on the integers mod p for all odd p while order $$(\log p)^2$$ steps are necessary for $$X_n$$ to be close to uniformly distributed on the integers mod p.

This paper studies zeta functions of the form $\sum_{n=1}^{\infty} \chi(n) n^{-s}$, with $\chi$ a completely multiplicative function taking only unimodular values. We denote by $\sigma(\chi)$ the infimum of those $\alpha$ such that the Dirichlet series $\sum_{n=1}^{\infty} \chi(n) n^{-s}$ can be continued meromorphically to the half-plane $\operatorname{Re} s>\alpha$, and denote by $\zeta_{\chi}(s)$ the corresponding meromorphic function in $\operatorname{Re} s>\sigma(\chi)$. We construct $\zeta_{\chi}(s)$ that have $\sigma(\chi)\le 1/2$ and are universal for zero-free analytic functions on the half-critical strip $1/21$. Finally, we show that there exists $\zeta_{\chi}(s)$ with $\sigma(\chi) \le 1/2$ and zeros at any discrete multiset in the strip $1/21/2$; on the Riemann hypothesis, this strip may be replaced by the half-critical strip $1/2 < \operatorname{Re} s < 1$., Comment: This is the final version of the paper which has been accepted for publication in Journal d'Analyse Math\'{e}matique

Given a graph $G$, a probability measure $\mu$ on the subsets of the edge set of $G$ is said to be $1$-independent if events determined by edge sets that are at graph distance at least $1$ apart in $G$ are independent. Call such a probability measure a $1$-ipm on $G$, and denote by $\mathbf{G}_{\mu}$ the associated random spanning subgraph of $G$. Let $\mathcal{M}_{1,\geqslant p}(G)$ (resp. $\mathcal{M}_{1,\leqslant p}(G)$) denote the collection of $1$-ipms $\mu$ on $G$ for which each edge is included in $\mathbf{G}_{\mu}$ with probability at least $p$ (resp. at most $p$). Let $\mathbb{Z}^2$ denote the square integer lattice. Balister and Bollob\'as raised the question of determining the critical value $p_{\star}=p_{1,c}(\mathbb{Z}^2)$ such that for all $p>p_{\star}$ and all $\mu \in \mathcal{M}_{1,\geqslant p}(\mathbb{Z}^2)$, $\left(\mathbf{\mathbb{Z}^2}\right)_{\mu}$ almost surely contains an infinite component. This can be thought of as asking for a $1$-independent analogue of the celebrated Harris--Kesten theorem. In this paper we investigate both this problem and connectivity problems for $1$-ipms more generally. We give two lower bounds on $p_{\star}$ that significantly improve on the previous bounds. Furthermore, motivated by the Russo--Seymour--Welsh lemmas, we define a $1$-independent critical probability for long paths and determine its value for the line and ladder lattices. Finally, for finite graphs $G$ we study $f_{1,G}(p)$ (respectively $F_{1,G}(p)$), the infimum (resp. supremum) over all $\mu\in \mathcal{M}_{1,\geqslant p}(G)$ (resp. all $\mu \in \mathcal{M}_{1,\leqslant p}(G)$) of the probability that $\mathbf{G}_{\mu}$ is connected. We determine $f_{1,G}(p)$ and $F_{1,G}(p)$ exactly when $G$ is a path, a complete graph and a cycle of length at most $5$. Many new problems arise from our work, which are discussed in the final section of the paper., Comment: 43 pages, 3 figures

The circular descent of a permutation $\sigma$ is a set $\{ \sigma(i) \mid \sigma(i) \gt \sigma(i+1) \}$. In this paper, we focus on the enumerations of permutations by the circular descent set. Let $\operatorname{cdes}_n(S)$ be the number of permutations of length $n$ which have the circular descent set $S$. We derive the explicit formula for $\operatorname{cdes}_n(S)$. We describe a class of generating binary trees $T_k$ with weights. We find that the number of permutations in the set $\operatorname{CDES}_n(S)$ corresponds to the weights of $T_k$. As a application of the main results in this paper, we also give the enumeration of permutation tableaux according to their shape.

The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give the first polynomial-time algorithm for the weighted T-free 2-matching problem under the assumption that T is a set of edge-disjoint triangles. In our algorithm, a key ingredient is to give an extended formulation representing the solution set, that is, we introduce new variables and represent the convex hull of the feasible solutions as a projection of another polytope in a higher dimensional space. Although our extended formulation has exponentially many inequalities, we show that the separation problem can be solved in polynomial time, which leads to a polynomial-time algorithm for the weighted T-free 2-matching problem., A preliminary version of this paper appears in [Kobayashi, Y.: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles. In: Integer Programming and Combinatorial Optimization, pp. 280–293. Springer, New York (2020).].

Variants of the coordinate descent approach for minimizing a nonlinear function are distinguished in part by the order in which coordinates are considered for relaxation. Three common orderings are cyclic (CCD), in which we cycle through the components of $x$ in order; randomized (RCD), in which the component to update is selected randomly and independently at each iteration; and random-permutations cyclic (RPCD), which differs from CCD only in that a random permutation is applied to the variables at the start of each cycle. Known convergence guarantees are weaker for CCD and RPCD than for RCD, though in most practical cases, computational performance is similar among all these variants. There is a certain type of quadratic function for which CCD is significantly slower than for RCD; a recent paper by Sun & Ye (2016, Worst-case complexity of cyclic coordinate descent: $O(n^2)$ gap with randomized version. Technical Report. Stanford, CA: Department of Management Science and Engineering, Stanford University. arXiv:1604.07130) has explored the poor behavior of CCD on functions of this type. The RPCD approach performs well on these functions, even better than RCD in a certain regime. This paper explains the good behavior of RPCD with a tight analysis.

We say that a complete nonsingular toric variety (called a toric manifold in this paper) is over $P$ if its quotient by the compact torus is homeomorphic to $P$ as a manifold with corners. Bott manifolds (or Bott towers) are toric manifolds over an $n$-cube $I^n$ and blowing them up at a fixed point produces toric manifolds over $\mathrm{vc}(I^n)$ an $n$-cube with one vertex cut. They are all projective. On the other hand, Oda's $3$-fold, the simplest non-projective toric manifold, is over $\mathrm{vc}(I^n)$. In this paper, we classify toric manifolds over $\mathrm{vc}(I^n)$ $(n\ge 3)$ as varieties and also as smooth manifolds. As a consequence, it turns out that (1) there are many non-projective toric manifolds over $\mathrm{vc}(I^n)$ but they are all diffeomorphic, and (2) toric manifolds over $\mathrm{vc}(I^n)$ in some class are determined by their cohomology rings as varieties among toric manifolds., Comment: 37 pages, 1 figure

The motivating question of this paper is roughly the following: given a group scheme $G$ over $\mathbb{Z}_p$, $p$ prime, with semisimple generic fiber $G_{\mathbb{Q}_p}$, how far are open subgroups of $G(\mathbb{Z}_p)$ from subgroups of the form $X(\mathbb{Z}_p)\mathbf{K}_p(p^n)$, where $X$ is a subgroup scheme of $G$ and $\mathbf{K}_p(p^n)$ is the principal congruence subgroup $\operatorname{Ker} (G(\mathbb{Z}_p)\rightarrow G(\mathbb{Z}/p^n\mathbb{Z}))$? More precisely, we will show that for $G_{\mathbb{Q}_p}$ simply connected there exist constants $J\ge1$ and $\varepsilon>0$, depending only on $G$, such that any open subgroup of $G (\mathbb{Z}_p)$ of level $p^n$ admits an open subgroup of index $\le J$ which is contained in $X(\mathbb{Z}_p)\mathbf{K}_p(p^{\lceil \varepsilon n\rceil})$ for some proper connected algebraic subgroup $X$ of $G$ defined over $\mathbb{Q}_p$. Moreover, if $G$ is defined over $\mathbb{Z}$, then $\varepsilon$ and $J$ can be taken independently of $p$. We also give a correspondence between natural classes of $\mathbb{Z}_p$-Lie subalgebras of $\mathfrak{g}_{\mathbb{Z}_p}$ and of closed subgroups of $G(\mathbb{Z}_p)$ that can be regarded as a variant over $\mathbb{Z}_p$ of Nori's results on the structure of finite subgroups of $\operatorname{GL}(N_0,\mathbb{F}_p)$ for large $p$. As an application we give a bound for the volume of the intersection of a conjugacy class in the group $G (\hat{\mathbb{Z}}) = \prod_p G (\mathbb{Z}_p)$, for $G$ defined over $\mathbb{Z}$, with an arbitrary open subgroup. In a future paper, this result will be applied to the limit multiplicity problem for arbitrary congruence subgroups of the arithmetic lattice $G (\mathbb{Z})$., fixed a few inaccuracies and made some stylistic changes to appear in JEMS

This paper develops an abstract theory for subdifferential operators to give existence and uniqueness of solutions to the initial-boundary problem (P) for the nonlinear diffusion equation in an unbounded domain $\Omega\subset\mathbb{R}^N$ ($N\in{\mathbb N}$), written as \[ \frac{\partial u}{\partial t} + (-\Delta+1)\beta(u) = g \quad \mbox{in}\ \Omega\times(0, T), \] which represents the porous media, the fast diffusion equations, etc., where $\beta$ is a single-valued maximal monotone function on $\mathbb{R}$, and $T>0$. Existence and uniqueness for (P) were directly proved under a growth condition for $\beta$ even though the Stefan problem was excluded from examples of (P). This paper completely removes the growth condition for $\beta$ by confirming Cauchy's criterion for solutions of the following approximate problem (P)$_{\varepsilon}$ with approximate parameter $\varepsilon>0$: \[ \frac{\partial u_{\varepsilon}}{\partial t} + (-\Delta+1)(\varepsilon(-\Delta+1)u_{\varepsilon} + \beta(u_{\varepsilon}) + \pi_{\varepsilon}(u_{\varepsilon})) = g \quad \mbox{in}\ \Omega\times(0, T), \] which is called the Cahn--Hilliard system, even if $\Omega \subset \mathbb{R}^N$ ($N \in \mathbb{N}$) is an unbounded domain. Moreover, it can be seen that the Stefan problem is covered in the framework of this paper.

We extend our result on the convergence of double recurrence Wiener-Wintner averages to the case where we have a polynomial exponent. We will show that there exists a single set of full measure for which the averages \[ \frac{1}{N} \sum_{n=1}^N f_1(T^{an}x)f_2(T^{bn}x)\phi(p(n)) \] converge for any polynomial $p$ with real coefficients, and any continuous function $\phi$ from the torus to the set of complex numbers . We also show that if either function belongs to an orthogonal complement of an appropriate Host-Kra-Ziegler factor that depends on the degree of the polynomial $p$, then the averages converge to zero uniformly for all polynomials. This paper combines the authors' previously announced work., Comment: This is the final version to appear in Journal d'Analyse mathematique. This latest version combines the previously posted papers on the arxiv website as arXiv:1408.3064 and arXiv:1409.0463

In this paper, we study zero-one laws for the Erd\H{o}s--R\'{e}nyi random graph model $G(n,p)$ in the case when $p = n^{-\alpha}$ for $\alpha>0$. For a given class $\mathcal{K}$ of logical sentences about graphs and a given function $p=p(n)$, we say that $G(n,p)$ obeys the zero-one law (w.r.t. the class $\mathcal{K}$) if each sentence $\varphi\in\mathcal{K}$ either a.a.s. true or a.a.s. false for $G(n,p)$. In this paper, we consider first order properties and monadic second order properties of bounded \textit{quantifier depth} $k$, that is, the length of the longest chain of nested quantifiers in the formula expressing the property. Zero-one laws for properties of quantifier depth $k$ we call the \textit{zero-one $k$-laws}. The main results of this paper concern the zero-one $k$-laws for monadic second order properties (MSO properties). We determine all values $\alpha>0$, for which the zero-one $3$-law for MSO properties does not hold. We also show that, in contrast to the case of the $3$-law, there are infinitely many values of $\alpha$ for which the zero-one $4$-law for MSO properties does not hold. To this end, we analyze the evolution of certain properties of $G(n,p)$ that may be of independent interest.

This paper is aimed at presenting a systematic survey of the existing now different formulations for the problem of projection of the origin of the Euclidean space onto the convex polyhedron (PPOCP). In the present paper, there are investigated the reduction of the projection program to the problems of quadratic programming, maximin, linear complementarity, and nonnegative least squares. Such reduction justifies the opportunity of utilizing a much more broad spectrum of powerful tools of mathematical programming for solving PPOCP. The paper's goal is to draw the attention of a wide range of research at the different formulations of the projection problem, which remain largely unknown due to the fact that the papers (addressing the subject of concern) are published even though on the adjacent, but other topics, or only in the conference proceedings., 19 pages

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the graph. Suppose also that $r < m$, where $2m$ is the average degree. We determine a critical function $a_c(t)$ such that when $a(t) \gg a_c(t)$, complete infection occurs with high probability as $t \rightarrow \infty$, but when $a(t) \ll a_c (t)$, then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to $a(t)$., This paper is significantly different to the previous version

For a sequence of integers $\{a(x)\}_{x \geq 1}$ we show that the distribution of the pair correlations of the fractional parts of $\{ \langle \alpha a(x) \rangle \}_{x \geq 1}$ is asymptotically Poissonian for almost all $\alpha$ if the additive energy of truncations of the sequence has a power savings improvement over the trivial estimate. Furthermore, we give an estimate for the Hausdorff dimension of the exceptional set as a function of the density of the sequence and the power savings in the energy estimate. A consequence of these results is that the Hausdorff dimension of the set of $\alpha$ such that $\{\langle \alpha x^d \rangle\}$ fails to have Poissonian pair correlation is at most $\frac{d+2}{d+3} < 1$. This strengthens a result of Rudnick and Sarnak which states that the exceptional set has zero Lebesgue measure. On the other hand, classical examples imply that the exceptional set has Hausdorff dimension at least $\frac{2}{d+1}$. An appendix by Jean Bourgain was added after the first version of this paper was written. In this appendix two problems raised in the paper are solved., Comment: 22 pages. Version 2 contains an appendix by Jean Bourgain. Version 3 with corrections suggested by the referee. The paper will be published in the Israel Journal of Mathematics

George Birkhoff proved in 1912 that the number of proper colorings of a finite graph G with n colors is a polynomial in n, called the chromatic polynomial of G. Read conjectured in 1968 that for any graph G, the sequence of absolute values of coefficients of the chromatic polynomial is unimodal: it goes up, hits a peak, and then goes down. Read's conjecture was proved by June Huh in a 2012 paper making heavy use of methods from algebraic geometry. Huh's result was subsequently refined and generalized by Huh and Katz, again using substantial doses of algebraic geometry. Both papers in fact establish log-concavity of the coefficients, which is stronger than unimodality. The breakthroughs of Huh and Huh-Katz left open the more general Rota-Welsh conjecture where graphs are generalized to (not necessarily representable) matroids and the chromatic polynomial of a graph is replaced by the characteristic polynomial of a matroid. The Huh and Huh-Katz techniques are not applicable in this level of generality, since there is no underlying algebraic geometry to which to relate the problem. But in 2015 Adiprasito, Huh, and Katz announced a proof of the Rota-Welsh conjecture based on a novel approach motivated by but not making use of any results from algebraic geometry. The authors first prove that the Rota-Welsh conjecture would follow from combinatorial analogues of the Hard Lefschetz Theorem and Hodge-Riemann relations in algebraic geometry. They then implement an elaborate inductive procedure to prove the combinatorial Hard Lefschetz Theorem and Hodge-Riemann relations using purely combinatorial arguments. We will survey these developments., Comment: 22 pages. This is an expository paper to accompany my lecture at the 2017 AMS Current Events Bulletin. v2: Numerous minor corrections

This paper studies a higher dimensional generalization of Frieze's $\zeta(3)$-limit theorem in the Erd\"os-R\'enyi graph process. Frieze's theorem states that the expected weight of the minimum spanning tree converges to $\zeta(3)$ as the number of vertices goes to infinity. In this paper, we study the $d$-Linial-Meshulam process as a model for random simplicial complexes, where $d=1$ corresponds to the Erd\"os-R\'enyi graph process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in $O(n^{d-1})$., Comment: 24 pages

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

The closest infinite dimensional relatives of compact Lie algebras are Hilbert-Lie algebras, i.e. real Hilbert spaces with a Lie algebra structure for which the scalar product is invariant. Locally affine Lie algebras (LALAs) correspond to double extensions of (twisted) loop algebras over simple Hilbert-Lie algebras $\mathfrak{k}$, also called affinisations of $\mathfrak{k}$. They possess a root space decomposition whose corresponding root system is a locally affine root system of one of the $7$ families $A_J^{(1)}$, $B_J^{(1)}$, $C_J^{(1)}$, $D_J^{(1)}$, $B_J^{(2)}$, $C_J^{(2)}$ and $BC_J^{(2)}$ for some infinite set $J$. To each of these types corresponds a "minimal" affinisation of some simple Hilbert-Lie algebra $\mathfrak{k}$, which we call standard. In this paper, we give for each affinisation $\mathfrak{g}$ of a simple Hilbert-Lie algebra $\mathfrak{k}$ an explicit isomorphism from $\mathfrak{g}$ to one of the standard affinisations of $\mathfrak{k}$. The existence of such an isomorphism could also be derived from the classification of locally affine root systems, but for representation theoretic purposes it is crucial to obtain it explicitely as a deformation between two twists which is compatible with the root decompositions. We illustrate this by applying our isomorphism theorem to the study of positive energy highest weight representations of $\mathfrak{g}$. In subsequent work, the present paper will be used to obtain a complete classification of the positive energy highest weight representations of affinisations of $\mathfrak{k}$., Comment: 22 pages; Minor corrections

Let $V$ be a projective subvariety of $\mathbb P^n(\mathbb C)$. A family of hypersurfaces $\{Q_i\}_{i=1}^q$ in $\mathbb P^n(\mathbb C)$ is said to be in $N$-subgeneral position with respect to $V$ if for any $1\le i_1, Comment: This paper is a revised version of the manuscript "Second main theorem and unicity of meromorphic mappings for hypersurfaces of projective varieties in subgeneral position, arXiv:1302.1261" of the first author. This paper is accepted for publication in Acta Mathematica Vietnamica (2016)

We consider consecutive random subdivision of polygons described as follows. Given an initial convex polygon with $d\ge 3$ edges, we choose a point at random on each edge, such that the proportions in which these points divide edges are i.i.d. copies of some random variable $\xi$. These new points form a new (smaller) polygon. By repeatedly implementing this procedure we obtain a sequence of random polygons. The aim of this paper is to show that under very mild non-degenerateness conditions on $\xi$, the shapes of these polygons eventually become "flat" The convergence rate to flatness is also investigated; in particular, in the case of triangles ($d=3$), we show how to calculate the exact value of the rate of convergence, connected to Lyapunov exponents. Using the theory of products of random matrices our paper greatly generalizes the results of Volkov (2013) which are achieved mostly by using ad hoc methods., Comment: 35 pages, 2 figures

The (un)weighted stability for some matrices on a graph is one of essential hypotheses in time-frequency analysis and applied harmonic analysis. In the first part of this paper, we show that for a localized matrix in a Beurling algebra, its weighted stabilities for different exponents and Muckenhoupt weights are equivalent to each other, and reciprocal of its optimal lower stability bound for one exponent and weight is controlled by a polynomial of reciprocal of its optimal lower stability bound for another exponent and weight. Banach algebras of matrices with certain off-diagonal decay is of great importance in many mathematical and engineering fields, and its inverse-closed property can be informally interpreted as localization preservation. Let $${{\mathcal {B}}}(\ell ^p_w)$$ be the Banach algebra of bounded linear operators on the weighted sequence space $$\ell ^p_w$$ on a graph. In the second part of this paper, we prove that Beurling algebras of localized matrices on a connected simple graph are inverse-closed in $${{\mathcal {B}}}(\ell ^p_w)$$ for all $$1\le p

The speed of a class of graphs counts the number of graphs on the vertex set $\lbrace 1,\dots, n\rbrace$ inside the class as a function of $n$. In this paper, we investigate this function for many classes of graphs that naturally arise in discrete geometry, for example intersection graphs of segments or disks in the plane. While upper bounds follow from Warren's theorem (a variant of a theorem of Milnor and Thom), all the previously known lower bounds were obtained from ad hoc constructions for very specific classes. We prove a general theorem giving an essentially tight lower bound for the number of graphs on $\lbrace 1,\dots, n\rbrace$ whose edges are defined using the signs of a given finite list of polynomials, assuming these polynomials satisfy some reasonable conditions. This in particular implies lower bounds for the speed of many different classes of intersection graphs, which essentially match the known upper bounds. Our general result also gives essentially tight lower bounds for counting containment orders of various families of geometric objects, including circle orders and angle orders. Some of the applications presented in this paper are new, whereas others recover results of Alon-Scheinerman, Fox, McDiarmid-M\"{u}ller and Shi. For the proof of our result we use some tools from algebraic geometry and differential topology., Comment: 38 pages, improved exposition

We denote the local "little" and "big" Lipschitz functions of a function $f: {{\mathbb R}}\to {{\mathbb R}}$ by $ {\mathrm {lip}}f$ and $ {\mathrm {Lip}}f$. In this paper we continue our research concerning the following question. Given a set $E {\subset} {{\mathbb R}}$ is it possible to find a continuous function $f$ such that $ {\mathrm {lip}}f=\mathbf{1}_E$ or $ {\mathrm {Lip}}f=\mathbf{1}_E$? In giving some partial answers to this question uniform density type (UDT) and strong uniform density type (SUDT) sets play an important role. In this paper we show that modulo sets of zero Lebesgue measure any measurable set coincides with a ${\mathrm {Lip}} 1$ set. On the other hand, we prove that there exists a measurable SUDT set $E$ such that for any $G_\delta$ set $\widetilde{E}$ satisfying $|E\Delta\widetilde{E}|=0$ the set $\widetilde{E}$ does not have UDT. Combining these two results we obtain that there exists ${\mathrm {Lip}} 1$ sets not having UDT, that is, the converse of one of our earlier results does not hold., Comment: This is the version accepted to appear in Mathematica Slovaca

This thesis consists of the following papers.I J. Larsson, The Minimum Matching in Pseudo-dimension 0 0.The second paper lives in a more general setting. There we search for any cover of the ground set V, for general families F. Each set f ∈ F receives weight w(f) uniformly at random from [0,1]. The cost of a cover f_1,f_2,...f_m is then taken to be max_i w(f_i). This is equivalent (after a rescaling) to drawing sets from F at Poisson times, and the cost of a cover is the first time V is covered. This problem is known under a number of names, perhaps most famously the coupon collector problem. In the classical formulation, single elements of V are drawn, not sets. The classical coupon collector thus corresponds to the family F consisting of singleton sets, and we call the version allowing larger sets structured coupon collector problems. The main concern of this paper is to identify relevant properties of F that affect the covering time (i.e. minimal cost of a cover), and to provide (easily checkable) sufficient conditions for concentration of the covering time.For the third paper we narrow the scopes once more, and study the biased random k-SAT problem. The random k-SAT problem can be seen as a special case of the structured coupon collector, but a special case that has far richer structure than the generic case. The ground set is the hypercube Σ_n = {0, 1}^n, and the coupons are all the k-codimensional subcubes of Σ_n. We study a slight variation on this problem: subcubes are drawn with a constant bias towards 0, so that vertices in Σ_n with fewer 1's and more 0's are easier to cover.

In this paper we consider the existence of Hamilton cycles in the random graph $G=G_{n,m}^{��\geq 3}$. This a random graph chosen uniformly from the set of graphs with vertex set $[n]$, $m$ edges and minimum degree at least 3. Our ultimate goal is to prove that if $m=cn$ and $c>3/2$ is constant then $G$ is Hamiltonian w.h.p. In an earlier paper the second author showed that $c\geq 10$ is sufficient for this and in this paper we reduce the lower bound to $c>2.662...$. This new lower bound is the same lower bound found in Frieze and Pittel \cite{FP} for the expansion of so-called P��sa sets., arXiv admin note: text overlap with arXiv:1107.4947

In this paper, we study the Khovanov homology of an alternating virtual link $L$ and show that it is supported on $g+2$ diagonal lines, where $g$ equals the virtual genus of $L$. Specifically, we show that $Kh^{i,j}(L)$ is supported on the lines $j=2i-\sigma_{\xi}+2k-1$ for $0\leq k\leq g+1$ where $\sigma_{\xi^*}(L)+2g= \sigma_{\xi}(L)$ are the signatures of $L$ for a checkerboard coloring $\xi$ and its dual $\xi^*$. Of course, for classical links, the two signatures are equal and this recovers Lee's $H$-thinness result for $Kh^{*,*}(L)$. Our result applies more generally to give an upper bound for the homological width of the Khovanov homology of any checkerboard virtual link $L$. The bound is given in terms of the alternating genus of $L$, which can be viewed as the virtual analogue of the Turaev genus. The proof rests on associating, to any checkerboard colorable link $L$, an alternating virtual link diagram with the same Khovanov homology as $L$. In the process, we study the behavior of the signature invariants under vertical and horizontal mirror symmetry. We also compute the Khovanov homology and Rasmussen invariants in numerous cases and apply them to show non-sliceness and determine the slice genus for several virtual knots. Table 6 at the end of the paper lists the signatures, Khovanov polynomial, and Rasmussen invariant for alternating virtual knots up to six crossings.

Let $(X,h)$ be a compact and irreducible Hermitian complex space. This paper is devoted to various questions concerning the analytic K-homology of $(X,h)$. In the fist part, assuming either $\mathrm{dim}(\mathrm{sing}(X))=0$ or $\mathrm{dim}(X)=2$, we show that the rolled-up operator of the minimal $L^2$-$\overline{\partial}$ complex, denoted here $\overline{\eth}_{\mathrm{rel}}$, induces a class in $K_0 (X)\equiv KK_0(C(X),\mathbb{C})$. A similar result, assuming $\mathrm{dim}(\mathrm{sing}(X))=0$, is proved also for $\overline{\eth}_{\mathrm{abs}}$, the rolled-up operator of the maximal $L^2$-$\overline{\partial}$ complex. We then show that when $\mathrm{dim}(\mathrm{sing}(X))=0$ we have $[\overline{\eth}_{\mathrm{rel}}]=\pi_*[\overline{\eth}_M]$ with $\pi:M\rightarrow X$ an arbitrary resolution and with $[\overline{\eth}_M]\in K_0 (M)$ the analytic K-homology class induced by $\overline{\partial}+\overline{\partial}^t$ on $M$. In the second part of the paper we focus on complex projective varieties $(V,h)$ endowed with the Fubini-Study metric. First, assuming $\dim(V)\leq 2$, we compare the Baum-Fulton-MacPherson K-homology class of $V$ with the class defined analytically through the rolled-up operator of any $L^2$-$\overline{\partial}$ complex. We show that there is no $L^2$-$\overline{\partial}$ complex on $(\mathrm{reg}(V),h)$ whose rolled-up operator induces a K-homology class that equals the Baum-Fulton-MacPherson class. Finally in the last part of the paper we prove that under suitable assumptions on $V$ the push-forward of $[\overline{\eth}_{\mathrm{rel}}]$ in the K-homology of the classifying space of the fundamental group of $V$ is a birational invariant., Comment: Final version. To appear on Int. Math. Res. Not

Let $R$ be a commutative Noetherian ring and $\alpha$ an automorphism of $R$. This paper addresses the question: when does the skew polynomial ring $S = R[\theta; \alpha]$ satisfy the property $(\diamond)$, that for every simple $S$-module $V$ the injective hull $E_S(V)$ of $V$ has all its finitely generated submodules Artinian. The question is largely reduced to the special case where $S$ is primitive, for which necessary and sufficient conditions are found, which however do not between them cover all possibilities. Nevertheless a complete characterisation is found when $R$ is an affine algebra over a field $k$ and $\alpha$ is a $k$-algebra automorphism - in this case $(\diamond)$ holds if and only if all simple $S$-modules are finite dimensional over $k$. This leads to a discussion, involving close study of some families of examples, of when this latter condition holds for affine $k$-algebras $S = R[\theta;\alpha]$. The paper ends with a number of open questions., Comment: 23 pages; comments welcome

This paper deals with a complex third order linear measure differential equation \begin{equation*} i\mathrm{d}\left( y^{\prime }\right) ^{\bullet }+2iq\left( x\right) y^{\prime }\mathrm{d}x+y\left( i\mathrm{d}q\left( x\right) +\mathrm{d}p\left( x\right) \right) = \lambda y\mathrm{d}x \end{equation*} on a bounded interval with boundary conditions presenting a mixed aspect of the Dirichlet and the periodic problems. The dependence of eigenvalues on the coefficients $p$, $q$ is investigated. We prove that the $n$-th eigenvalue is continuous in $p$, $q$ when the norm topology of total variation and the weak$^*$ topology are considered. Moreover, the Fr\'{e}chet differentiability of the $n$-th eigenvalue in $p$, $q$ with the norm topology of total variation is also considered. To deduce these conclusions, we investigate the dependence of solutions of the above equation on the coefficients $p$, $q$ with different topologies and establish the counting lemma of eigenvalues according to the estimates of solutions., Comment: This paper has been accepted for publication in SCIENCE CHINA Mathematics

Chen et al. (2004) strongly conjectured that R(Tn,Wm)=2n-1 if the maximum degree of Tn is small and m is even. Related to the conjecture, it is interesting to know for which tree Tn, we have R(Tn,Wm) > 2n-1 for even m. In this paper, we find the Ramsey number R(Tn,W8) for tree Tn with the maximum degree of Tn is at least n-3, namely R(Tn,W8) > 2n-1 for almost all such tree Tn. We also prove that if the maximum degree of Tn is large, then R(Tn,Wm) is a function of both m and n. In the end, we refine the conjecture of Chen et al. by giving the condition of small maximum degree. For a tree Tn with large maximum degree and even m, the R(Tn,Wm) is also unknown in general. In this paper, we shall determine the Ramsey number R(Tn,W8) for all trees Tn of order n with the maximum degree of Tn is at least n-3., 7 pages

In this paper we are interested in lifting a prescribed group of automorphisms of a finite graph via regular covering projections. Here we describe with an example the problems we address and refer to the introductory section for the correct statements of our results. Let $P$ be the Petersen graph, say, and let $\wp:\tilde{P}\to P$ be a regular covering projection. With the current covering machinery, it is straightforward to find $\wp$ with the property that every subgroup of $\Aut(P)$ lifts via $\wp$. However, for constructing peculiar examples and in applications, this is usually not enough. Sometimes it is important, given a subgroup $G$ of $\Aut(P)$, to find $\wp$ along which $G$ lifts but no further automorphism of $P$ does. For instance, in this concrete example, it is interesting to find a covering of the Petersen graph lifting the alternating group $A_5$ but not the whole symmetric group $S_5$. (Recall that $\Aut(P)\cong S_5$.) Some other time it is important, given a subgroup $G$ of $\Aut(P)$, to find $\wp$ with the property that $\Aut(\tilde{P})$ is the lift of $G$. Typically, it is desirable to find $\wp$ satisfying both conditions. In a very broad sense, this might remind wallpaper patterns on surfaces: the group of symmetries of the dodecahedron is $S_5$, and there is a nice colouring of the dodecahedron (found also by Escher) whose group of symmetries is just $A_5$. In this paper, we address this problem in full generality., Comment: 10 pages

In this paper, we address the minimum-cost node-capacitated multiflow problem in an undirected network. For this problem, Babenko and Karzanov (2012) showed strongly polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial weakly polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in $O(m \log(nCD)\mathrm{SF}(kn, m, k))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $C$ is the maximum node capacity, $D$ is the maximum edge cost, and $\mathrm{SF}(n', m', \eta)$ is the time complexity of solving the submodular flow problem in a network of $n'$ nodes, $m'$ edges, and a submodular function with $\eta$-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows., Comment: A preliminary version of this paper was presented in at the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2019