Search

Given a finite poset $\mathcal P$, we call a family $\mathcal F$ of subsets of $[n]$ $\mathcal P$-saturated if $\mathcal F$ does not contain an induced copy of $\mathcal P$, but adding any other set to $\mathcal F$ creates an induced copy of $\mathcal P$. The induced saturated number of $\mathcal P$, denoted by $\text{sat}^*(n,\mathcal P)$, is the size of the smallest $\mathcal P$-saturated family with ground set $[n]$. In this paper we are mainly interested in the four-point poset called the butterfly. Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan showed that the saturation number for the butterfly lies between $\log_2{n}$ and $n^2$. We give a linear lower bound of $n+1$. We also prove some other results about the butterfly and the poset $\mathcal N$., Comment: 13 pages

The aim of this paper is to describe the structure of the finitely generated subgroups of a family of branch groups, which includes the first Grigorchuk group and the Gupta-Sidki 3-group. This description is made via the notion of block subgroup. We then use this to show that all groups in the above family are subgroup separable (LERF). These results are obtained as a corollary of a more general structural statement on subdirect products of just infinite groups., 22 pages, 2 figures; V3: Final version, to appear in Izvestiya: Mathematics

In this paper we investigate Ramanujan’s inequality concerning the prime counting function, asserting that π ( x 2 ) < e x log x π ( x e ) \pi \left( {{x^2}} \right) < {{ex} \over {\log x}}\pi \left( {{x \over e}} \right) for x sufficiently large. First, we study its sharpness by giving full asymptotic expansions of its left and right hand sides expressions. Then, we discuss the structure of Ramanujan’s inequality, by replacing the factor x log x {x \over {\log x}} on its right hand side by the factor x log x - h {x \over {\log x - h}} for a given h, and by replacing the numerical factor e by a given positive α. Finally, we introduce and study inequalities analogous to Ramanujan’s inequality.

The notion of best approximation mapping (BAM) with respect to a closed affine subspace in finite-dimensional space was introduced by Behling, Bello Cruz and Santos to show the linear convergence of the block-wise circumcentered-reflection method. The best approximation mapping possesses two critical properties of the circumcenter mapping for linear convergence. Because the iteration sequence of BAM linearly converges, the BAM is interesting in its own right. In this paper, we naturally extend the definition of BAM from closed affine subspace to nonempty closed convex set and from $\mathbb{R}^{n}$ to general Hilbert space. We discover that the convex set associated with the BAM must be the fixed point set of the BAM. Hence, the iteration sequence generated by a BAM linearly converges to the nearest fixed point of the BAM. Connections between BAMs and other mappings generating convergent iteration sequences are considered. Behling et al.\ proved that the finite composition of BAMs associated with closed affine subspaces is still a BAM in $\mathbb{R}^{n}$. We generalize their result from $\mathbb{R}^{n}$ to general Hilbert space and also construct a new constant associated with the composition of BAMs. This provides a new proof of the linear convergence of the method of alternating projections. Moreover, compositions of BAMs associated with general convex sets are investigated. In addition, we show that convex combinations of BAMs associated with affine subspaces are BAMs. Last but not least, we connect BAM with circumcenter mapping in Hilbert spaces., 31 pages and 2 figures

In this paper we develop a method to transfer density results for primitive automatic sequences to logarithmic-density results for general automatic sequences. As an application we show that the logarithmic densities of any automatic sequence along squares $(n^2)_{n\geq 0}$ and primes $(p_n)_{n\geq 1}$ exist and are computable. Furthermore, we give for these subsequences a criterion to decide whether the densities exist, in which case they are also computable. In particular in the prime case these densities are all rational. We also deduce from a recent result of the third author and Lema\'nczyk that all subshifts generated by automatic sequences are orthogonal to any bounded multiplicative aperiodic function., Comment: 35 pages. We added an Appendix concerning upper densities of subsequences of automatic sequences

A graph $X$ is defined inductively to be $(a_0,\dots,a_{n-1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius $1$ around $v$ is an $(a_1,\dots,a_{n-1})$-regular graph. Such a graph $X$ is said to be highly regular (HR) of level $n$ if $a_{n-1}\neq 0$. Chapman, Linial and Peled studied HR-graphs of level 2 and provided several methods to construct families of graphs which are expanders "globally and locally". They ask whether such HR-graphs of level 3 exist. In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can lead to such graphs. Given a Coxeter system $(W,S)$ and a subset $M$ of $S$, we construct highly regular quotients of the 1-skeleton of the associated Wythoffian polytope $\mathcal{P}_{W,M}$, which form an infinite family of expander graphs when $(W,S)$ is indefinite and $\mathcal{P}_{W,M}$ has finite vertex links. The regularity of the graphs in this family can be deduced from the Coxeter diagram of $(W,S)$. The expansion stems from applying superapproximation to the congruence subgroups of the linear group $W$. This machinery gives a rich collection of families of HR-graphs, with various interesting properties, and in particular answers affirmatively the question asked by Chapman, Linial and Peled., Comment: 22 pages, 2 tables. Dedicated to the memory of John Conway and Ernest Vinberg

A partial flag variety P K of a Kac–Moody group G has a natural stratification into projected Richardson varieties. When G is a connected reductive group, a Bruhat atlas for P K was constructed in He et al. (2013): P K is locally modelled with Schubert varieties in some Kac–Moody flag variety as stratified spaces. The existence of Bruhat atlases implies some nice combinatorial and geometric properties on the partial flag varieties and the decomposition into projected Richardson varieties. A Bruhat atlas does not exist for partial flag varieties of an arbitrary Kac–Moody group due to combinatorial and geometric reasons. To overcome obstructions, we introduce the notion of Birkhoff–Bruhat atlas. Instead of the Schubert varieties used in a Bruhat atlas, we use the J -Schubert varieties for a Birkhoff–Bruhat atlas. The notion of the J -Schubert varieties interpolates Birkhoff decomposition and Bruhat decomposition of the full flag variety (of a larger Kac–Moody group). The main result of this paper is the construction of a Birkhoff–Bruhat atlas for any partial flag variety P K of a Kac–Moody group. We also construct a combinatorial atlas for the index set Q K of the projected Richardson varieties in P K . As a consequence, we show that Q K has some nice combinatorial properties. This gives a new proof and generalizes the work of Williams (2007) in the case where the group G is a connected reductive group.

Assume E is an imaginary quadratic field and O is its ring of integers. For each positive integer m, let I m be the free Hermitian lattice of rank m over O having an orthonormal basis. For each positive integer n, let S O ( n ) be the set of all Hermitian lattices of rank n over O that can be represented by some I m . Denote by g O ( n ) the smallest positive integer g such that each Hermitian lattice in S O ( n ) can be represented by I g . In this paper, we shall provide an explicit upper bound for g O ( n ) for all imaginary quadratic fields E and all positive integers n.

We show in this paper that the VC-dimension of the family of d-dimensional axis-parallel boxes and cubes on the d-dimensional torus are both asymptotically d log 2 ⁡ d . This is especially surprising as in most other examples the VC-dimension usually grows linearly with d in similar settings.

This paper presents various functional-geometric aspects of the logarithmic Sobolev capacity Cap log ⁡ , γ , p - a capacity generated by the logarithmic Sobolev space W p log ⁡ , γ , where ( γ , p ) ∈ ( 0 , ∞ ) × [ 1 , ∞ ) . This new nonlinear-inhomogeneous-nontrivial capacity is closely related to the logarithmic Hausdorff capacity. Not only continuously sharp embedding property of W p log ⁡ , γ into certain logarithmic weighted Lebesgue space and the tracing inequalities are established, but also the logarithmic perimeter and the Lebesgue measure are utilized to: reformulate Cap log ⁡ , γ , p ; find the first variation of the logarithmic perimeter via the corresponding logarithmic mean curvature; characterize the hypersurface of a constant logarithmic mean curvature.

The maximum weighted independent set (MWIS) problem is important since it occurs in various applications, such as facility location, selection of non-overlapping time slots, labeling of digital maps, etc. However, in real-life situations, input parameters within those models are often loosely defined or subject to change. For such reasons, this paper studies robust variants of the MWIS problem. The study is restricted to cases where the involved graph is a tree. Uncertainty of vertex weights is represented by intervals. First, it is observed that the max–min variant of the problem can be solved in linear time. Next, as the most important original contribution, it is proved that the min–max regret variant is NP-hard. Finally, two mutually related approximation algorithms for the min–max regret variant are proposed. The first of them is already known, but adjusted to the considered situation, while the second one is completely new. Both algorithms are analyzed and evaluated experimentally.