Covering simply connected regions by rectangles

We prove that the ratio of the minimum number of rectangles covering a simply connected board (polyomino)B and the maximum number of points inB no two of which are contained in a common rectangle is less than 2. This research was partially supported by MEV (Budapest).     

The Bohman‐Frieze process near criticality

The Erd?s‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the graph. A classical result of Erd?s and Rényi states that the Erd?s‐Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erd?s and Rényi, various random graph models have been introduced and studied. In this paper we study the Bohman‐Frieze process, a simple modification of the Erd?s‐Rényi process. The Bohman‐Frieze process also begins with an empty graph on n vertices. At each step two random edges are presented, and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman‐Frieze process. We show that it has a qualitatively similar phase transition to the Erd?s‐Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time t_c ? ? (that is, when the number of edges are (t_c ? ?)n/2) are trees or unicyclic components and that the largest component is of size Ω(?^‐2log n). Further, at t_c + ?, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(?^‐2log n). Each of these results corresponds to an analogous well‐known result for the Erd?s‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On the uniqueness of promotion operators on tensor products of type <Emphasis Type="Italic">A</Emphasis> crystals

The affine Dynkin diagram of type A _n ⁽¹⁾ has a cyclic symmetry. The analogue of this Dynkin diagram automorphism on the level of crystals is called a promotion operator. In this paper we show that the only irreducible type A _n crystals which admit a promotion operator are the highest weight crystals indexed by rectangles. In addition we prove that on the tensor product of two type A _n crystals labeled by rectangles, there is a single connected promotion operator. We conjecture this to be true for an arbitrary number of tensor factors. Our results are in agreement with Kashiwara’s conjecture that all ‘good’ affine crystals are tensor products of Kirillov-Reshetikhin crystals.     

Well-posedness in Sobolev spaces of the full water wave problem in 3-D

We consider the motion of the interface of a 3-D inviscid, incompressible, irrotational water wave, with air region above water region and surface tension zero. We prove that the motion of the interface of the water wave is not subject to Taylor instability, as long as the interface separates the whole 3-D space into two simply connected regions. We prove further the existence and uniqueness of solutions of the full 3-D water wave problem, locally in time, for any initial interface that separates the whole 3-D space into two simply connected regions.

     

Rectangular tileability and complementary tileability are undecidable

Does a given set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.     

On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph

The Erd?s‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that in many cases, this upper bound is sharp in the order of magnitude. Our result for the Erd?s‐Rényi graph has the following reformulation: the maximum size of a family of mutually non‐orthogonal lines in a vector space of dimension three over the finite field of order q is of order q^3/2. We also prove that every subset of vertices of size greater than q^2/2 + q^3/2 + O(q) in the Erd?s‐Rényi graph contains a triangle. This shows that an old construction of Parsons is asymptotically sharp. Several related results and open problems are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 113–127, 2007     

A Mordell-Lang plus Bogomolov type result for curves in $${\mathbb{G}_{m}^{2}}$$

We prove a sharper so-called Mordell-Lang plus Bogomolov type result for curves lying in the two-dimensional linear torus. We mainly follow the approach of Rémond in (Comp Math 134:337–366, 2002), using Vojta and Mumford type inequalities. In the special case we consider, we improve Rémond’s main result using a better Bogomolov property and an elementary arithmetic Bézout theorem.      

Optimal rectangle packing

We consider the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. We present two different constraint-satisfaction formulations of this problem. The first searches a space of absolute placements of rectangles in the enclosing rectangle, while the other searches a space of relative placements between pairs of rectangles. Both approaches dramatically outperform previous approaches to optimal rectangle packing. For problems where the rectangle dimensions have low precision, such as small integers, absolute placement is generally more efficient, whereas for rectangles with high-precision dimensions, relative placement will be more effective. In two sets of experiments, we find both the smallest rectangles and squares that can contain the set of squares of size 1×1, 2×2,…,N×N, for N up to 27. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to 24×24 in a square of size 70×70. Finally, we find the smallest enclosing rectangles that can contain a set of unoriented rectangles of size 1×2, 2×3, 3×4,…,N×(N+1), for N up to 25.     

Hamiltonian properties of triangular grid graphs

A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. In 2000, Reay and Zamfirescu showed that all 2-connected, linearly-convex triangular grid graphs (with the exception of one of them) are hamiltonian. The only exception is a graph D which is the linearly-convex hull of the Star of David. We extend this result to a wider class of locally connected triangular grid graphs. Namely, we prove that all connected, locally connected triangular grid graphs (with the same exception of graph D) are hamiltonian. Moreover, we present a sufficient condition for a connected graph to be fully cycle extendable. We also show that the problem Hamiltonian Cycle is NP-complete for triangular grid graphs.     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

Semilattice orders on the homomorphic images of the Rédei semigroup

The combinatorial simple principal ideal semigroups generated by two elements were described by L. Megyesi and G. Pollák. The ‘most general’ among them is called the Rédei semigroup. The ‘most special’ combinatorial simple principal ideal semigroup generated by two elements is the bicyclic semigroup. D. B. McAlister determined the compatible semilattice orders on the bicyclic semigroup. Our aim is to study the compatible semilattice orders on the homomorphic images of the Rédei semigroup. We prove that there are four compatible total orders on these semigroups. We show that on the Rédei semigroup, the total orders are the only compatible semilattice orders. Moreover, on each proper homomorphic image of the Rédei semigroup, we give a compatible semilattice order which is not a total order. Communicated by Mária B. Szendrei     

Saddle points and overdetermined problems for the Helmholtz equation

In a seminal 1971 paper, James Serrin showed that the only open, smoothly bounded domain in ⁿ on which the positive Dirichlet eigenfunction of the Laplacian has constant (nonzero) normal derivative on the boundary, is then-dimensional ball. The positivity of the eigenfunction is crucial to his proof. To date it is an open conjecture that the same result is true for Dirichlet eigenvalues other than the least. We show that for simply connected, plane domains, the absence of saddle points is a condition sufficient to validate this conjecture. This condition is also sufficient to prove Schiffer's conjecture: the only simply connected planar domain, on the boundary of which a nonconstant Neumann eigenfunction of the Laplacian can take constant value, is the disc.     

Witness Rectangle Graphs

In a witness rectangle graph (WRG) on vertex point set P with respect to witness point set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally, we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n points.     

Fibrations of Campana general type on surfaces

We construct complex surfaces with genus two fibrations over \mathbb P¹{\mathbb P^1} having special fibres such that the minimum of the multiplicities of the components is ≥ 2 whereas the g.c.d is 1. We can then produce new examples of fibred surfaces without multiple fibres which are of “general type” according to the definition of Campana. We prove that these surfaces are of general type and simply connected; and we compute in some cases their invariants. Moreover, we extend the construction obtaining general type fibrations of any even genus on simply connected surfaces. All our examples are defined over number fields.     

SUBGROUP DISTORTIONS IN NILPOTENT GROUPS

The explicit formula for the distortion function of a connected Lie subgroup in a connected simply connected nilpotent Lie group is obtained. In particular, we prove that a function f: N → R can be realized (up to equivalence) as the distortion function of a connected Lie subgroup in a connected simply connected nilpotent Lie group if and only if f ～ n^r for some nonnegative r ∈ Q. Considering lattices in Lie groups, we establish the analogous results for finitely generated nilpotent groups.     

Isoperimetric properties of Euclidean boundary moments of a simply connected domain

We consider integral functionals of a simply connected domain which depend on the distance to the domain boundary. We prove an isoperimetric inequality generalizing theorems derived by the Schwarz symmetrization method. For L ^p -norms of the distance function we prove an analog of the Payne inequality for the torsional rigidity of the domain. In compare with the Payne inequality we find new extremal domains different from a disk.     

A Mordell-Lang plus Bogomolov type result for curves in \mathbbGm2{\mathbb{G}_{m}^{2}}

We prove a sharper so-called Mordell-Lang plus Bogomolov type result for curves lying in the two-dimensional linear torus. We mainly follow the approach of Rémond in (Comp Math 134:337–366, 2002), using Vojta and Mumford type inequalities. In the special case we consider, we improve Rémond’s main result using a better Bogomolov property and an elementary arithmetic Bézout theorem.     

Generalized entropy of the Heisenberg spin chain

We consider the XY quantum spin chain in a transverse magnetic field. We consider the Rényi entropy of a block of neighboring spins at zero temperature on an infinite lattice. The Rényi entropy is essentially the trace of some power α of the density matrix of the block. We calculate the entropy of the large block in terms of Klein’s elliptic λ-function. We study the limit entropy as a function of its parameter α. We show that the Rényi entropy is essentially an automorphic function with respect to a certain subgroup of the modular group. Using this, we derive the transformation properties of the Rényi entropy under the map α → α ⁻¹ .