Minimization of circuit registers: Retiming revisited

We address the following problem: given a synchronous digital circuit, is it possible to construct a new circuit computing the same function as the original one but using a minimal number of registers? We show that the minimal number of registers is the size of the minimal cut on a bi-infinite graph, namely the unfolding of the dependencies in the digital circuit. Furthermore, the construction of such a cut and the corresponding circuit can be done in polynomial time, using a max-flow min-cut result of Orlin for one-periodic bi-infinite graphs. Finally, we show the relation between this construction and the retiming technique introduced by Leiserson and Saxe.     

Topological Ergodicity of Real Cocycles over Minimal Rotations

 We prove that for each minimal rotation on a compact metric group and each topological cocycle , either φ is a topological coboundary, or is topologically ergodic, or the partition into orbits is the decomposition of into minimal components. As an application, we generalize a result by Glasner and show that if is a minimal topologically weakly mixing flow, then whenever φ is universally ergodic the minimal map

Minimal and locally minimal games and game forms

By Shapley’s (1964) theorem, a matrix game has a saddle point whenever each of its 2×2 subgames has one. In other words, all minimal saddle point free (SP-free) matrices are of size 2×2. We strengthen this result and show that all locally minimal SP-free matrices also are of size 2×2. In other words, if A is a SP-free matrix in which a saddle point appears after deleting an arbitrary row or column then A is of size 2×2. Furthermore, we generalize this result and characterize the locally minimal Nash equilibrium free (NE-free) bimatrix games.Let us recall that a two-person game form is Nash-solvable if and only if it is tight [V. Gurvich, Solution of positional games in pure strategies, USSR Comput. Math. and Math. Phys. 15 (2) (1975) 74-87]. We show that all (locally) minimal non-tight game forms are of size 2×2. In contrast, it seems difficult to characterize the locally minimal tight game forms (while all minimal ones are just trivial); we only obtain some necessary and some sufficient conditions. We also recall an example from cooperative game theory: a maximal stable effectivity function that is not self-dual and not convex.     

Cut sets and normed cohomology with applications to percolation

We discuss an inequality for graphs, which relates the distances between components of any minimal cut set to the lengths of generators for the homology of the graph. Our motivation arises from percolation theory. In particular this result is applied to Cayley graphs of finite presentations of groups with one end, where it gives an exponential bound on the number of minimal cut sets, and thereby shows that the critical probability for percolation on these graphs is neither zero nor one. We further show for this same class of graphs that the critical probability for the coalescence of all infinite components into a single one is neither zero nor one.

     

Minimal left ideals of near-rings

We show that a finite minimal left ideal L of a zero symmetric near-ring N is a planar near-ring if L is not contained in the radical J ₂(N). This result will follow from a more general discussion on minimal N-subgroups of a near-ring. Then we discuss some consequences of this result when applied to the structure theory of near-rings. Finally we transfer our results to rings and deal with some ring theoretic questions concerning “trivial” multiplications in rings.     

A generalization of Rado's Theorem for almost graphical boundaries

In this paper, we prove a generalization of Rado's Theorem, a fundamental result of minimal surface theory, which says that minimal surfaces over a convex domain with graphical boundaries must be disks which are themselves graphical. We will show that, for a minimal surface of any genus, whose boundary is ``almost graphical' in some sense, that the surface must be graphical once we move sufficiently far from the boundary.     

The Regularity of Parametrized Integer Stationary Varifolds in Two Dimensions

We establish an optimal regularity result for parametrized two-dimensional stationary varifolds. Namely, we show that the parametrization map is a smooth minimal branched immersion and that the multiplicity function is constant. We provide some applications of this regularity result, especially in the calculus of variations for the area functional. © 2020 Wiley Periodicals LLC     

Minimal Surfaces in the Heisenberg Group

We investigate the minimal surface problem in the three dimensional Heisenberg group, H, equipped with its standard Carnot–Carathéodory metric. Using a particular surface measure, we characterize minimal surfaces in terms of a sub-elliptic partial differential equation and prove an existence result for the Plateau problem in this setting. Further, we provide a link between our minimal surfaces and Riemannian constant mean curvature surfaces in H equipped with different Riemannian metrics approximating the Carnot–Carathéodory metric. We generate a large library of examples of minimal surfaces and use these to show that the solution to the Dirichlet problem need not be unique. Moreover, we show that the minimal surfaces we construct are in fact X-minimal surfaces in the sense of Garofalo and Nhieu.     

Enlarging totally geodesic submanifolds of symmetric spaces to minimal submanifolds of one dimension higher

We show that a totally geodesic submanifold of a symmetric space satisfying certain conditions admits an extension to a minimal submanifold of dimension one higher, and we apply this result to construct new examples of complete embedded minimal submanifolds in simply connected noncompact globally symmetric spaces.

     

Partitions of Graphs into Cographs

Cographs from the minimal family of graphs containing K₁ which are closed with respect to complements and unions. We discuss vertex partitions of graphs into the smallest number of cographs, where the partition is as small as possible. We shall call the order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show both bounds are sharp, for graphs with arbitrarily high girth. This provides an alternative proof to a result in [3]; there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number of at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

On Minimal Annuli with a Straight Line Boundary

Shiffman proved that if a minimal annulus A in a slab is bounded by two convex Jordan curves contained respectively in the two boundary planes P and Q of the slab, then A intersects all parallel planes between P and Q in strictly convex curves. We generalize Shiffman's result to the case that A is bounded by a strictly convex C² Jordan curve and a straight line. We show that in this case Shiffman's result is still true.     

Bounds for solid angles of lattices of rank three

We find sharp absolute constants C₁ and C₂ with the following property: every well-rounded lattice of rank 3 in a Euclidean space has a minimal basis so that the solid angle spanned by these basis vectors lies in the interval [C₁,C₂]. In fact, we show that these absolute bounds hold for a larger class of lattices than just well-rounded, and the upper bound holds for all. We state a technical condition on the lattice that may prevent it from satisfying the absolute lower bound on the solid angle, in which case we derive a lower bound in terms of the ratios of successive minima of the lattice. We use this result to show that among all spherical triangles on the unit sphere in RN with vertices on the minimal vectors of a lattice, the smallest possible area is achieved by a configuration of minimal vectors of the (normalized) face centered cubic lattice in R³. Such spherical configurations come up in connection with the kissing number problem.     

2-Minimality,jump classes and a note on natural definability

We show that there is a generalized high degree which is a minimal cover of a minimal degree. This is the highest jump class one can reach by finite iterations of minimality. This result also answers an old question by Lerman.     

Bounded Immunity and Btt-Reductions

We define and study a new notion called k-immunity that lies between immunity and hyperimmunity in strength. Our interest in k-immunity is justified by the result that θ does not k-tt reduce to a k-immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt-reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new characterization of effectively simple sets and show that simple sets are not btt-cuppable.     

A General Existence Theorem for Embedded Minimal Surfaces with Free Boundary

In this paper, we prove a general existence theorem for properly embedded minimal surfaces with free boundary in any compact Riemannian 3‐manifold M with boundary ?M. These minimal surfaces are either disjoint from ?M or meet ?M orthogonally. The main feature of our result is that there is no assumptions on the curvature of M or convexity of ?M. We prove the boundary regularity of the minimal surfaces at their free boundaries. Furthermore, we define a topological invariant, the filling genus, for compact 3‐manifolds with boundary and show that we can bound the genus of the minimal surface constructed above in terms of the filling genus of the ambient manifold M. Our proof employs a variant of the min‐max construction used by Colding and De Lellis on closed embedded minimal surfaces, which were first developed by Almgren and Pitts.© 2014 Wiley Periodicals, Inc.     

An extension of Barta’s Theorem and geometric applications

We prove an extension of a theorem of Barta and we give some geometric applications. We extend Cheng’s lower eigenvalue estimates of normal geodesic balls. We generalize Cheng-Li-Yau eigenvalue estimates of minimal submanifolds of the space forms. We show that the spectrum of the Nadirashvili bounded minimal surfaces in have positive lower bounds. We prove a stability theorem for minimal hypersurfaces of the Euclidean space, giving a converse statement of a result of Schoen. Finally we prove generalization of a result of Kazdan–Kramer about existence of solutions of certain quasi-linear elliptic equations. Bessa and Montenegro were partially supported by CNPq Grant.     

Measurable cardinals and good ‐wellorderings

We study the influence of the existence of large cardinals on the existence of wellorderings of power sets of infinite cardinals κ with the property that the collection of all initial segments of the wellordering is definable by a Σ₁‐formula with parameter κ. A short argument shows that the existence of a measurable cardinal δ implies that such wellorderings do not exist at δ‐inaccessible cardinals of cofinality not equal to δ and their successors. In contrast, our main result shows that these wellorderings exist at all other uncountable cardinals in the minimal model containing a measurable cardinal. In addition, we show that measurability is the smallest large cardinal property that imposes restrictions on the existence of such wellorderings at uncountable cardinals. Finally, we generalise the above result to the minimal model containing two measurable cardinals.     

Rich families and elementary submodels

We compare two methods of proving separable reduction theorems in functional analysis — the method of rich families and the method of elementary submodels. We show that any result proved using rich families holds also when formulated with elementary submodels and the converse is true in spaces with fundamental minimal system and in spaces of density ?₁. We do not know whether the converse is true in general. We apply our results to show that a projectional skeleton may be without loss of generality indexed by ranges of its projections.     

E_(s)^(5)中的双调和超曲面北大核心CSCD

本文研究五维伪欧氏空间E_(s)^(5)中的双调和超曲面的几何和分类问题,证明了:如果M^(4)_(r)是E_(s)^(5)(s=1,2,3,4)中具有对角化形状算子的双调和超曲面,那么M^(4)_(r)一定是极小的.结合Turgay等人结果,本文进一步表明了五维Minkowski空间E_(1)^(5)中Lorentz双调和超曲面一定是极小的.该结果证明了五维伪欧氏空间中超曲面情形下的双调和猜想.     

A generalization of the Shapley–Ichiishi result

The Shapley–Ichiishi result states that a game is convex if and only if the convex hull of marginal vectors equals the core. In this paper, we generalize this result by distinguishing equivalence classes of balanced games that share the same core structure. We then associate a system of linear inequalities with each equivalence class, and we show that the system defines the class. Application of this general theorem to the class of convex games yields an alternative proof of the Shapley–Ichiishi result. Other applications range from computation of stable sets in non-cooperative game theory to determination of classes of TU games on which the core correspondence is additive (even linear). For the case of convex games we prove that the theorem provides the minimal defining system of linear inequalities. An example shows that this is not necessarily true for other equivalence classes of balanced games.