On Sub-determinants and the Diameter of Polyhedra

We derive a new upper bound on the diameter of a polyhedron \(P = \{x {\in } {\mathbb {R}}^n :Ax\le b\}\) , where \(A \in {\mathbb {Z}}^{m\times n}\) . The bound is polynomial in \(n\) and the largest absolute value of a sub-determinant of \(A\) , denoted by \(\Delta \) . More precisely, we show that the diameter of \(P\) is bounded by \(O(\Delta ^2 n^4\log n\Delta )\) . If \(P\) is bounded, then we show that the diameter of \(P\) is at most \(O(\Delta ^2 n^{3.5}\log n\Delta )\) . For the special case in which \(A\) is a totally unimodular matrix, the bounds are \(O(n^4\log n)\) and \(O(n^{3.5}\log n)\) respectively. This improves over the previous best bound of \(O(m^{16}n^3(\log mn)^3)\) due to Dyer and Frieze (Math Program 64:1–16, 1994).     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.     

Counting and Sampling Minimum Cuts in Genus g Graphs

Let \(G\) be a directed graph with \(n\) vertices embedded on an orientable surface of genus \(g\) with two designated vertices \(s\) and \(t\) . We show that computing the number of minimum \((s,t)\) -cuts in \(G\) is fixed-parameter tractable in \(g\) . Specifically, we give a \(2^{O(g)} n^2\) time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are no prior results that are fixed-parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample an \((s,t)\) -minimum cut uniformly at random in \(O(n \log n)\) time per sample.     

Une preuve de la conjecture d’Erdős,Joò et Komornik dans le cas des séries formelles

Properties of Pisot numbers have long been of interest. One line of questioning, initiated by Erdös, Joò and Komornik in (Bull Soc Math France 118:377–390, 1990), is the study of the set \(\Lambda _{m}(\beta )\) the spectrum of \(\beta \) and the determination of \(l^{m}(\beta )\) for Pisot number \(\beta \) , where \(\Lambda _{m}(\beta )\) denotes the set of numbers having at least one representation of the form \(\omega =\varepsilon _{n} \beta ^{n}+\varepsilon _{n-1}\beta ^{n-1}+\cdots +\varepsilon _{1}\beta +\varepsilon _{0},\) such that the \(\varepsilon _{i}\in \{-m,\ldots ,0,\ldots ,m\}\) , for all \(0\le i\le n\) , and \(l^{m}(\beta )=\inf \{|\omega |:\omega \in \Lambda _{m},\omega \ne 0\}.\) In this paper, we consider \(\Lambda _{m}(\beta )\) , where \(\beta \) is a formal power series over a finite field and the \(\varepsilon _{i}\) are polynomials of degree at most \(m\) for all \(0\le i\le n\) . Our main result is to give a full answer in the Laurent series case, to an old question of Erd?s and Komornik (Acta Math Hungar 79:57–83, 1998), as to whether \(l^{1}(\beta )=0\) for all non-Pisot numbers. More generally, we characterize the inequalities \(l^{m}(\beta )>0\) .     

Hyperreflexivity of bounded N-cocycle spaces of banach algebras

Let \(X\) and \(Y\) be Banach spaces, \(n\in \mathbb {N}\) , and \(B^n(X,Y)\) the space of bounded \(n\) -linear maps from \(X\times \ldots \times X\) ( \(n\) -times) into \(Y\) . The concept of hyperreflexivity has already been defined for subspaces of \(B(X,Y)\) , where \(X\) and \(Y\) are Banach spaces. We extend this concept to the subspaces of \(B^n(X,Y)\) , taking into account its \(n\) -linear structure. We then investigate when \(\mathcal {Z}^n(A,X)\) , the space of all bounded \(n\) -cocycles from a Banach algebra \(A\) into a Banach \(A\) -bimodule \(X\) , is hyperreflexive. Our approach is based on defining two notions related to a Banach algebra, namely the strong property \((\mathbb {B})\) and bounded local units, and then applying them to find uniform criterions under which \(\mathcal {Z}^n(A,X)\) is hyperreflexive. We also demonstrate that these criterions are satisfied in variety of examples including large classes of C \(^*\) -algebras and group algebras and thereby providing various examples of hyperreflexive \(n\) -cocyle spaces. One advantage of our approach is that not only we obtain the hyperreflexivity for bounded \(n\) -cocycle spaces in different cases but also our results generalize the earlier ones on the hyperreflexivity of bounded derivation spaces, i.e. when \(n=1\) , in the literature. Finally, we investigate the hereditary properties of the strong property \((\mathbb {B})\) and b.l.u. This allows us to come with more examples of bounded \(n\) -cocycle spaces which are hyperreflexive.     

Composition operators acting on Besov spaces on the real line

We study the composition operator \(T_f(g):= f\circ g\) on Besov spaces \(B_{{p},{q}}^{s}(\mathbb{R })\) . In case \(1 < p< +\infty ,\, 0< q \le +\infty \) and \(s>1+ (1/p)\) , we will prove that the operator \(T_f\) maps \(B_{{p},{q}}^{s}(\mathbb{R })\) to itself if, and only if, \(f(0)=0\) and \(f\) belongs locally to \(B_{{p},{q}}^{s}(\mathbb{R })\) . For the case \(p=q\) , i.e., in case of Slobodeckij spaces, we can extend our results from the real line to \(\mathbb{R }^n\) .     

Square functions in the Hermite setting for functions with values in UMD spaces

In this paper, we characterize the Lebesgue Bochner spaces \(L^p({\mathbb{R }}^{n},B),\, 1 , by using Littlewood–Paley \(g\) -functions in the Hermite setting, provided that \(B\) is a UMD Banach space. We use \(\gamma \) -radonifying operators \(\gamma (H,B)\) where \(H=L^2((0,\infty ),\frac{\mathrm{d}t}{t})\) . We also characterize the UMD Banach spaces in terms of \(L^p({\mathbb{R }}^{n},B)-L^p({\mathbb{R }}^{n},\gamma (H,B))\) boundedness of Hermite Littlewood–Paley \(g\) -functions.     

A canonical structure on the tangent bundle of a pseudo- or para-Kähler manifold

It is a classical fact that the cotangent bundle \(T^* {\mathcal {M}}\) of a differentiable manifold \({\mathcal {M}}\) enjoys a canonical symplectic form \(\Omega ^*\) . If \(({\mathcal {M}},\mathrm{J} ,g,\omega )\) is a pseudo-Kähler or para-Kähler \(2n\) -dimensional manifold, we prove that the tangent bundle \(T{\mathcal {M}}\) also enjoys a natural pseudo-Kähler or para-Kähler structure \(({\tilde{\hbox {J}}},\tilde{g},\Omega )\) , where \(\Omega \) is the pull-back by \(g\) of \(\Omega ^*\) and \(\tilde{g}\) is a pseudo-Riemannian metric with neutral signature \((2n,2n)\) . We investigate the curvature properties of the pair \(({\tilde{\hbox {J}}},\tilde{g})\) and prove that: \(\tilde{g}\) is scalar-flat, is not Einstein unless \(g\) is flat, has nonpositive (resp. nonnegative) Ricci curvature if and only if \(g\) has nonpositive (resp. nonnegative) Ricci curvature as well, and is locally conformally flat if and only if \(n=1\) and \(g\) has constant curvature, or \(n>2\) and \(g\) is flat. We also check that (i) the holomorphic sectional curvature of \(({\tilde{\hbox {J}}},\tilde{g})\) is not constant unless \(g\) is flat, and (ii) in \(n=1\) case, that \(\tilde{g}\) is never anti-self-dual, unless conformally flat.     

Pointwise convergence in Pringsheim’s sense of the summability of Fourier transforms on Wiener amalgam spaces

New multi-dimensional Wiener amalgam spaces \(W_c(L_p,\ell _\infty )(\mathbb{R }^d)\) are introduced by taking the usual one-dimensional spaces coordinatewise in each dimension. The strong Hardy-Littlewood maximal function is investigated on these spaces. The pointwise convergence in Pringsheim’s sense of the \(\theta \) -summability of multi-dimensional Fourier transforms is studied. It is proved that if the Fourier transform of \(\theta \) is in a suitable Herz space, then the \(\theta \) -means \(\sigma _T^\theta f\) converge to \(f\) a.e. for all \(f\in W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d)\) . Note that \(W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d) \supset W_c(L_r,\ell _\infty )(\mathbb{R }^d) \supset L_r(\mathbb{R }^d)\) and \(W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d) \supset L_1(\log L)^{d-1}(\mathbb{R }^d)\) , where \(1 . Moreover, \(\sigma _T^\theta f(x)\) converges to \(f(x)\) at each Lebesgue point of \(f\in W_c(L_1(\log L)^{d-1},\ell _\infty )(\mathbb{R }^d)\) .     

Transitive \text{ PSL}(2,7)-invariant 42-arcs in 3-dimensional projective spaces

We construct an infinite family of transitive 42-arcs in \(\text{ PG}(3,q^{2})\) , with \(q=p^{n}\ge 29\) and \(q\equiv 1\pmod {7}\) , under the action of the group \(\text{ PSL}(2,7)\) in its representation as a subgroup of \(\text{ PGL}(4,q)\) . Further, we study the case \(q=29\) in detail with computer assistance. For \(q=29\) these 42-arcs turn out to be complete.     

Measure of Self-Affine Sets and Associated Densities

Let \(B\) be an \(n\times n\) real expanding matrix and \(\mathcal {D}\) be a finite subset of \(\mathbb {R}^n\) with \(0\in \mathcal {D}\) . The self-affine set \(K=K(B,\mathcal {D})\) is the unique compact set satisfying the set-valued equation \(BK=\bigcup _{d\in \mathcal {D}}(K+d)\) . In the case where \(\#\mathcal D=|\det B|,\) we relate the Lebesgue measure of \(K(B,\mathcal {D})\) to the upper Beurling density of the associated measure \(\mu =\lim _{s\rightarrow \infty }\sum _{\ell _0, \ldots ,\ell _{s-1}\in \mathcal {D}}\delta _{\ell _0+B\ell _1+\cdots +B^{s-1}\ell _{s-1}}.\) If, on the other hand, \(\#\mathcal D<|\det B|\) and \(B\) is a similarity matrix, we relate the Hausdorff measure \(\mathcal {H}^s(K)\) , where \(s\) is the similarity dimension of \(K\) , to a corresponding notion of upper density for the measure \(\mu \) .     

Generation of full cycles by a composition of NLFSRs

Non-linear feedback shift registers (NLFSRs) are a generalization of linear feedback shift registers in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are typically hard to break with existing cryptanalytic methods. However, it is still not known how to construct large \(n\) -stage NLFSRs which generate full cycles of \(2^n\) possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an \(n*k\) -stage register with period \(O(2^{2n})\) can be constructed from \(k\) NLFSRs with \(n\) -stages by adding to their feedback functions a logic block of size \(O(nk)\) , for \(k > 1\) . This logic block implements Boolean functions representing pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size \(O(nk)\) .     

Second eigenvalue of the Yamabe operator and applications

Let \((M,g)\) be a compact Riemannian manifold of dimension \(n\ge 3\) . In this paper, we give various properties of the eigenvalues of the Yamabe operator \(L_g\) . In particular, we show how the second eigenvalue of \(L_g\) is related to the existence of nodal solutions of the equation \(L_g u = {\varepsilon }|u|^{N-2}u,\) where \({\varepsilon }= +1,\) \(0,\) or \(-1.\)      

Fast algorithms for a space-time concordance measure

This paper presents a number of algorithms for a recently developed measure of space-time concordance. Based on a spatially explicit version of Kendall’s \(\tau \) the original implementation of the concordance measure relied on a brute force \(O(n^2)\) algorithm which has limited its use to modest sized problems. Several new algorithms have been devised which move this run time to \(O(n log(n) +np)\) where \(p\) is the expected number of spatial neighbors for each unit. Comparative timing of these alternative implementations reveals dramatic efficiency gains in moving away from the brute force algorithms. A tree-based implementation of the spatial concordance is also found to dominate a merge sort implementation.     

On matching cover of graphs

A k-matching cover of a graph \(G\) is a union of \(k\) matchings of \(G\) which covers \(V(G)\) . The matching cover number of \(G\) , denoted by \(mc(G)\) , is the minimum number \(k\) such that \(G\) has a \(k\) -matching cover. A matching cover of \(G\) is optimal if it consists of \(mc(G)\) matchings of \(G\) . In this paper, we present an algorithm for finding an optimal matching cover of a graph on \(n\) vertices in \(O(n^3)\) time (if use a faster maximum matching algorithm, the time complexity can be reduced to \(O(nm)\) , where \(m=|E(G)|\) ), and give an upper bound on matching cover number of graphs. In particular, for trees, a linear-time algorithm is given, and as a by-product, the matching cover number of trees is determined.     

Vertex transitive graphs from injective linear mappings

Based on a motivation coming from the study of the metric structure of the category of finite dimensional vector spaces over a finite field \(\mathbb {F}\) , we examine a family of graphs, defined for each pair of integers \(1 \le k \le n\) , with vertex set formed by all injective linear transformations \(\mathbb {F}^k \rightarrow \mathbb {F}^n\) and edges corresponding to pairs of mappings, \(f\) and \(g\) , with \(\lambda (f,g)= \dim \mathrm{Im }(f-g)=1 \) . For \(\mathbb {F}\cong \mathrm{GF }(q)\) , this graph will be denoted by \(\mathrm{INJ }_q(k,n)\) . We show that all such graphs are vertex transitive and Hamiltonian and describe the full automorphism group of each \(\mathrm{INJ }_q (k,n)\) for \(k . Using the properties of line-transitive groups, we completely determine which of the graphs \(\mathrm{INJ }_q (k,n)\) are Cayley and which are not. The Cayley ones consist of three infinite families, corresponding to pairs \((1,n),\,(n-1,n)\) , and \((n,n)\) , with \(n\) and \(q\) arbitrary, and of two sporadic examples \(\mathrm{INJ }_{2} (2,5)\) and \(\mathrm{INJ }_{2}(3,5)\) . Hence, the overwhelming majority of our graphs is not Cayley.