Almost cover-free codes and designs

An s-subset of codewords of a binary code X is said to be \((s,\,\ell )\) -bad in X if the code X contains a subset of \(\ell \) other codewords such that the conjunction of the \(\ell \) codewords is covered by the disjunctive sum of the s codewords. Otherwise, the s-subset of codewords of X is called \((s,\,\ell )\) -good in X. A binary code X is said to be a cover-free (CF) \((s,\,\ell )\)-code if the code X does not contain \((s,\,\ell )\)-bad subsets. In this paper, we introduce a natural probabilistic generalization of CF \((s,\,\ell )\)-codes, namely: a binary code X is said to be an almost CF \((s,\,\ell )\)-code if the relative number of its \((s,\,\ell )\)-good s-subsets is close to 1. We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes. Our main result shows that the capacity for almost CF \((s,\,\ell )\)-codes is essentially greater than the rate for ordinary CF \((s,\,\ell )\)-codes.     

Regularity of powers of bipartite graphs

Let G be a finite simple graph and I(G) denote the corresponding edge ideal. For all \(s \ge 1\), we obtain upper bounds for \({\text {reg}}(I(G)^s)\) for bipartite graphs. We then compare the properties of G and \(G'\), where \(G'\) is the graph associated with the polarization of the ideal \((I(G)^{s+1} : e_1\cdots e_s)\), where \(e_1,\cdots , e_s\) are edges of G. Using these results, we explicitly compute \({\text {reg}}(I(G)^s)\) for several subclasses of bipartite graphs.     

A spectra comparison theorem and its applications

We give a sharp comparison between the spectra of two Riemannian manifolds (Y, g) and \((X,g_0)\) under the following assumptions: \((X,g_0)\) has bounded geometry, (Y, g) admits a continuous Gromov–Hausdorff \(\varepsilon \)-approximation onto \((X,g_0)\) of non zero absolute degree, and the volume of (Y, g) is almost smaller than the volume of \((X,g_0)\). These assumptions imply no restrictions on the local topology or geometry of (Y, g) in particular no curvature assumption is supposed or inferred.     

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.     

Improved upper bounds for partial spreads

A partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) is a collection of \((k-1)\)-dimensional subspaces with trivial intersection. So far, the maximum size of a partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) was known for the cases \(n\equiv 0\pmod k\), \(n\equiv 1\pmod k\), and \(n\equiv 2\pmod k\) with the additional requirements \(q=2\) and \(k=3\). We completely resolve the case \(n\equiv 2\pmod k\) for the binary case \(q=2\).     

Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

A partial Latin square (PLS) is a partial assignment of n symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The PLS extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap , i.e., the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient \((p,\infty )\)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for \(p\in \{1,2,3\}\). The running time of the algorithm is \(O(n^{p+1})\). We then propose a novel swap operation, Trellis-swap, which is a generalization of (p, q)-swap with \(p\le 2\). The proposed Trellis-neighborhood search algorithm runs in \(O(n^{3.5})\) time. The iterated local search (ILS) algorithm with Trellis-neighborhood is more likely to deliver a high-quality solution than not only ILSs with \((p,\infty )\)-neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.     

On the existence of closed magnetic geodesics via symplectic reduction

Let (M, g) be a closed Riemannian manifold and \(\sigma \) be a closed 2-form on M representing an integer cohomology class. In this paper, using symplectic reduction, we show how the problem of existence of closed magnetic geodesics for the magnetic flow of the pair \((g,\sigma )\) can be interpreted as a critical point problem for a Rabinowitz-type action functional defined on the cotangent bundle \(T^*E\) of a suitable \(S^1\)-bundle E over M or, equivalently, as a critical point problem for a Lagrangian-type action functional defined on the free loopspace of E. We thenstudy the relation between the stability property of energy hypersurfacesin \((T^*M,dp\wedge dq+\pi ^*\sigma )\) and of the corresponding codimension2 coisotropic submanifolds in \((T^*E,dp\wedge dq)\) arising via symplecticreduction. Finally, we reprove the main result of Asselle and Benedetti (J Topol Anal 8(3):545–570, 2016) in this setting.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Critical Sets of Full <Emphasis Type="Italic">n</Emphasis>-Latin Squares

The full n-Latin square is the \(n\times n\) array with symbols \(1,2,\dots ,n\) in each cell. In a way that is analogous to critical sets of full designs, a critical set of the full n-Latin square can be used to find a defining set for any Latin square of order n. In this paper we study the size of the smallest critical set for a full n-Latin square, showing this to be somewhere between \((n^3-2n^2+2n)/2\) and \((n-1)^3+1\). In the case that each cell is either full or empty, we show the size of a critical set in the full n-Latin square is always equal to \(n^3-2n^2-n\).     

On the minimum-cost $$\lambda $$-edge-connected k-subgraph problem

In this paper, we propose several integer programming (IP) formulations to exactly solve the minimum-cost \(\lambda \)-edge-connected k-subgraph problem, or the \((k,\lambda )\)-subgraph problem, based on its graph properties. Special cases of this problem include the well-known k-minimum spanning tree problem (if \(\lambda =1\)), \(\lambda \)-edge-connected spanning subgraph problem (if \(k=|V|\)) and k-clique problem (if \(\lambda = k-1\) and there are exact k vertices in the subgraph). As a generalization of k-minimum spanning tree and a case of the \((k,\lambda )\)-subgraph problem, the (k, 2)-subgraph problem is studied, and some special graph properties are proved to find stronger and more compact IP formulations. Additionally, we study the valid inequalities for these IP formulations. Numerical experiments are performed to compare proposed IP formulations and inequalities.     

The distortion dimension of $$\mathbb $$-rank 1 lattices

Let \(X=G/K\) be a symmetric space of noncompact type and rank \(k\ge 2\). We prove that horospheres in X are Lipschitz \((k-2)\)-connected if their centers are not contained in a proper join factor of the spherical building of X at infinity. As a consequence, the distortion dimension of an irreducible \(\mathbb {Q}\)-rank-1 lattice \(\Gamma \) in a linear, semisimple Lie group G of \(\mathbb R\)-rank k is \(k-1\). That is, given \(m< k-1\), a Lipschitz m-sphere S in (a polyhedral complex quasi-isometric to) \(\Gamma \), and a \((m+1)\)-ball B in X (or G) filling S, there is a \((m+1)\)-ball \(B'\) in \(\Gamma \) filling S such that \({{\mathrm{vol}}}B'\sim {{\mathrm{vol}}}B\). In particular, such arithmetic lattices satisfy Euclidean isoperimetric inequalities up to dimension \(k-1\).     

<Emphasis Type="Italic">M</Emphasis>-curves and symmetric products

Let \((X\, , \sigma )\) be a geometrically irreducible smooth projective M-curve of genus g defined over the field of real numbers. We prove that the n-th symmetric product of \((X\, , \sigma )\) is an M-variety for \(n\,=\,2\, ,3\) and \(n \,\ge \, 2g -1\).     

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

Conformal CR Positive Mass Theorem

In this paper, we prove the following version of conformal CR positive mass theorem: Suppose that \((N, J,\theta )\) and \((N, J,\hat{\theta }=e^{2f}\theta )\) are three-dimensional asymptotically flat pseudohermitian manifolds such that their Tanaka-Webster curvatures satisfy \(e^{2f}\hat{R}-R\ge 0.\) Then the p-mass of \((N, J, \theta )\) and \((N, J, \hat{\theta })\) satisfy \( m(J, \hat{\theta })-m(J, \theta )\ge 0, \) and equality holds if and only if \(\hat{\theta }=\theta \). We also prove that the p-mass is independent of the choice of the sequence of coordinates spheres.     

Korovkin-Type Approximation Theory in Riesz Spaces

In this paper, we prove the following Riesz spaces’ version of the Korovkin theorem. Let E and F be two Archimedean Riesz spaces with F uniformly complete, let W be a nonempty subset of \(E^{+}\), and let \((T_{n})\) be a given sequence of (r-u)-continuous elements of \(\mathcal {L(}E,F)\), such that \(\left| T_{n}-T_{m}\right| x=\left| (T_{n}-T_{m})x\right| \mathcal {\ }\)for all \(x\in E^{+},\) \(m,n\ge n_{0}\) (for a given \(n_{0}\in \mathbb {N} )\). If the sequence \((T_{n}x)_{n}\) \((r-u)\)-converges for every \(x\in W\), then \((T_{n})\) \((r-u)\)-converges also pointwise on the ideal \(E_{W}\), generated by W, to a linear operator \(S_{0}:E_{W}\rightarrow F\). We also prove a similar Korovkin-type theorem for nets of operators. Some applications for f-algebras and orthomorphisms are presented.     

Linear sets in the projective line over the endomorphism ring of a finite field

Let \({{\mathrm{{PG}}}}(1,E)\) be the projective line over the endomorphism ring \( E={{\mathrm{End}}}_q({\mathbb F}_{q^t})\) of the \({\mathbb F}_q\)-vector space \({\mathbb F}_{q^t}\). As is well known, there is a bijection \(\varPsi :{{\mathrm{{PG}}}}(1,E)\rightarrow {\mathcal G}_{2t,t,q}\) with the Grassmannian of the \((t-1)\)-subspaces in \({{\mathrm{{PG}}}}(2t-1,q)\). In this paper along with any \({\mathbb F}_q\)-linear set L of rank t in \({{\mathrm{{PG}}}}(1,q^t)\), determined by a \((t-1)\)-dimensional subspace \(T^\varPsi \) of \({{\mathrm{{PG}}}}(2t-1,q)\), a subset \(L_T\) of \({{\mathrm{{PG}}}}(1,E)\) is investigated. Some properties of linear sets are expressed in terms of the projective line over the ring E. In particular, the attention is focused on the relationship between \(L_T\) and the set \(L'_T\), corresponding via \(\varPsi \) to a collection of pairwise skew \((t-1)\)-dimensional subspaces, with \(T\in L'_T\), each of which determine L. This leads among other things to a characterization of the linear sets of pseudoregulus type. It is proved that a scattered linear set L related to \(T\in {{\mathrm{{PG}}}}(1,E)\) is of pseudoregulus type if and only if there exists a projectivity \(\varphi \) of \({{\mathrm{{PG}}}}(1,E)\) such that \(L_T^\varphi =L'_T\).     

Hyperinvariant Subspace Problem for Some Classes of Operators

An n-normal operator may be defined as an \(n \times n\) operator matrix with entries that are mutually commuting normal operators and an operator \(T \in \mathcal {B(H)}\) is quasi-nM-hyponormal (for \(n \in \mathbb {N}\)) if it is unitarily equivalent to an \(n \times n\) upper triangular operator matrix \((T_{ij})\) acting on \(\mathcal {K}^{(n)}\), where \(\mathcal {K}\) is a separable complex Hilbert space and the diagonal entries \(T_{jj}\) \((j = 1,2,\ldots , n)\) are M-hyponormal operators in \(\mathcal {B(K)}\). This is an extended notion of n-normal operators. We prove a necessary and sufficient condition for an \(n \times n\) triangular operator matrix to have Bishop’s property \((\beta )\). This leads us to study the hyperinvariant subspace problem for an \(n \times n\) triangular operator matrix.     

Families of conditionally approximately convex functions

Let \((G,+)\) be an Abelian topological group, which is also a \(T_{0}\)-space and a Baire space simultaneously, D be an open connected subset of G and \(\alpha : D-D \rightarrow {\mathbb R}\) be a function continuous at zero and such that \(\alpha (0)=0\). We show that if \((f_n)\) is a sequence of continuous functions \(f_n : D \rightarrow {\mathbb R}\) such that \(f_n(z) \le \frac{1}{2} f_n(x)+\frac{1}{2}f(y)+\alpha (x-y)\) for \(n\in {\mathbb N}\) and \(x,y,z\in D\) such that \(2z=x+y\) and if \((f_n)\) is pointwise convergent [bounded] then it is convergent uniformly on compact subsets of D [in the case when G is additionally a separable space, it contains a subsequence which is convergent on compact subsets of D].     

Stability of minimizers of set optimization problems

We study the asymptotic behavior of sequences of minimization problems in set optimization. More precisely, considering a sequence of set optimization problems \((P_n)\) converging in some sense to a set optimization problem (P) we investigate the upper and lower convergences of the sets of minimizers of the problems \((P_n)\) to the set of minimizers of the problem (P).     

The maximally symmetric surfaces in the 3-torus

Suppose an orientation-preserving action of a finite group G on the closed surface \(\Sigma _g\) of genus \(g>1\) extends over the 3-torus \(T^3\) for some embedding \(\Sigma _g\subset T^3\). Then \(|G|\le 12(g-1)\), and this upper bound \(12(g-1)\) can be achieved for \(g=n^2+1, 3n^2+1, 2n^3+1, 4n^3+1, 8n^3+1, n\in {\mathbb {Z}}_+\). The surfaces in \(T^3\) realizing a maximal symmetry can be either unknotted or knotted. Similar problems in the non-orientable category are also discussed. The connection with minimal surfaces in \(T^3\) is addressed and the situation when the maximally symmetric surfaces above can be realized by minimal surfaces is identified.