Maximal 0–1-fillings of moon polyominoes with restricted chain lengths and rc-graphs

We show that maximal 0–1-fillings of moon polynomials with restricted chain lengths can be identified with certain rc-graphs, also known as pipe dreams. In particular, this exhibits a connection between maximal 0–1-fillings of Ferrers shapes and Schubert polynomials. Moreover, it entails a bijective proof showing that the number of maximal fillings of a stack polyomino S with no north-east chains longer than k depends only on k and the multiset of column heights of S.     

Major index for 01-fillings of moon polyominoes

We propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M,s;A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations.     

Resistance distances in the linear polyomino chain

The resistance distance between any two vertices of a connected graph is defined as the effective resistance between them in the electrical network constructed from the graph by replacing each edge with a unit resistor. Let \(B_n\) denote the linear polyomino chain with \(n-1\) squares. In this paper, first by using resistance sum rules along with series and parallel principles, explicit formulae for the resistance distances between any two vertices of \(B_n\) are given. Then based on these formulae, the largest and the smallest resistance distances in \(B_n\) are determined. Finally, the monotonicity and some asymptotic properties of resistance distances in \(B_n\) are given.     

Many L-Shaped Polyominoes Have Odd Rectangular Packings

A polyomino is called odd if it can tile a rectangle using an odd number of copies. We give a very general family of odd polyominoes. Specifically, consider an L-shaped polyomino, i.e., a rectangle that has a rectangular piece removed from one corner. For some of these polyominoes, two copies tile a rectangle, called a basic rectangle. We prove that such a polyomino is odd if its basic rectangle has relatively prime side lengths. This general family encompasses several previously known families of odd polyominoes, as well as many individual examples. We prove a stronger result for a narrower family of polyominoes. Let L _n denote the polyomino formed by removing a 1 ×  (n?2) corner from a 2 ×  (n?1) rectangle. We show that when n is odd, L _n tiles all rectangles both of whose sides are at least 8n ³, and whose area is a multiple of n. If we only allow L _n to be rotated, but not reflected, then the same is true, provided that both sides of the rectangle are at least 16n ⁴. We also give several isolated examples of odd polyominoes.     

Irregular polyomino tiling via integer programming with application in phased array antenna design

A polyomino is a generalization of the domino and is created by connecting a fixed number of unit squares along edges. Tiling a region with a given set of polyominoes is a hard combinatorial optimization problem. This paper is motivated by a recent application of irregular polyomino tilings in the design of phased array antennas. Specifically, we formulate the irregular polyomino tiling problem as a nonlinear exact set covering model, where irregularity is incorporated into the objective function using the information-theoretic entropy concept. An exact solution method based on a branch-and-price framework along with novel branching and lower-bounding schemes is proposed. The developed method is shown to be effective for small- and medium-size instances of the problem. For large-size instances, efficient heuristics and approximation algorithms are provided. Encouraging computational results including phased array antenna simulations are reported.     

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

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

Helly Numbers of Polyominoes

We define the Helly number of a polyomino P as the smallest number h such that the h-Helly property holds for the family of symmetric and translated copies of P on the integer grid. We prove the following: (i) the only polyominoes with Helly number 2 are the rectangles, (ii) there does not exist any polyomino with Helly number 3, (iii) there exist polyominoes of Helly number k for any k ≠ 1, 3.     

Extremal polyomino chains with respect to Zagreb indices

For a molecular graph, the first Zagreb index M₁ is equal to the sum of squares of the vertex degrees and second Zagreb index M₂ is equal to the sum of products of degree of pairs of adjacent vertices. In this paper, Zagreb indices of polyomino chains are computed. Also the extremal polyomino chains with respect to Zagreb indices are determined.     

A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square

We propose an algorithm to sample the area of the smallest convex hull containing \(n\) sample points uniformly distributed over unit square. To do it, we introduce a new coordinate system for the position of vertexes and re-write joint distribution of the number of vertexes and their locations in the new coordinate system. The proposed algorithm is much faster than existing procedure and has a computational complexity on the order of \(O(T)\) , where \(T\) is the number of vertexes. Using the proposed algorithm, we numerically investigate the asymptotic behavior of functionals of the random convex hull. In addition, we apply it to finding pairs of stocks where the returns are dependent on each other on the New York Stock Exchange.     

Perfect Graphs and Guarding Rectilinear Art Galleries

In this paper we introduce a new method based on perfect graphs that can be used to prove bounds on the number of guards necessary to guard a rectilinear art gallery in terms of the number of vertices, area and perimeter, respectively. Using this method, we prove that a polyomino with perimeter $l\ge 6$ can be guarded by at most $\lfloor \tfrac{l}{6}\rfloor $ guards. Moreover, we give a new proof for the rectilinear art gallery theorem, stating that any rectilinear art gallery with $n$ vertices can be guarded by at most $\lfloor \frac{n}{4}\rfloor $ guards. Finally, we give a new proof that at most $\lfloor \tfrac{m+1}{3}\rfloor $ guards are necessary to guard an $m$ -polyomino, even if the polyomino contains holes.     

Mixed degree number field computations

We present a method for computing complete lists of number fields in cases where the Galois group, as an abstract group, appears as a Galois group in smaller degree. We apply this method to find the 25 octic fields with Galois group \({{\mathrm{PSL}}}_2(7)\) and smallest absolute discriminant. We carry out a number of related computations, including determining the octic field with Galois group \(2^3{:}{{\mathrm{GL}}}_3(2)\) of smallest absolute discriminant.     

Counting polyominoes: Yet another attack

A polyomino is a connected collection of squares on an unbounded chessboard. There is no known formula yielding the number of distinct polyominoes of a given number of squares A polyomino enumeration method, faster than any previous, is presented. This method includes the calculation of the number of symmetric polyominoes. All polyominoes containing up to 24 squares have been enumerated (using ten months of computer time). Previously, only polyominoes up to size 18 were enumerated.     

Markov Chains on Graded Posets

We consider two types of discrete-time Markov chains where the state space is a graded poset and the transitions are taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts between the up-directed transition probabilities (an up rule) and the down-directed (a down rule), and we relate these to compatibility between up-and-down chains. This framework is used to prove a conjecture about a limit shape for a process on Young’s lattice. Finally, we settle the questions whether the reverse of an up chain is a down chain for some down rule and whether there exists an up or down chain at all if the rank function is not bounded.     

The <Emphasis Type="Italic">m</Emphasis>th Largest and <Emphasis Type="Italic">m</Emphasis>th Smallest Parts of a Partition

The theory of overpartitions is applied to determine formulas for the number of partitions of n where (1) the mth largest part is k and (2) the mth smallest part is k.     

Stability of Quantum Electrodynamics and Quantum Chromodynamics

We consider the vacuum energy in QED viewed as in a system of charged fermions and bosons and in QCD viewed as in a system of quarks (fermions) and gluons (bosons) in a self-dual field with a constant strength. We show that the cause of instability is the instability of bosons in the self-dual vacuum field. For the global stability of a system consisting of fermions and bosons, the number of fermions should be sufficiently large. The nonzero self-dual field leading to the confinement of fermions realizes the minimum of the vacuum energy in the case where the boson has the smallest mass in the system. Confinement therefore does not arise in QED, where the fermion (electron) has the smallest mass, and does arise in QCD, where the boson (gluon) has the smallest mass.     

Reciprocal complementary Wiener numbers of trees, unicyclic graphs and bicyclic graphs

The reciprocal complementary Wiener number of a connected graph G is defined as

where V(G) is the vertex set, d(u,v|G) is the distance between vertices u and v, d is the diameter of G. We determine the trees with the smallest, the second smallest and the third smallest reciprocal complementary Wiener numbers, and the unicyclic and bicyclic graphs with the smallest and the second smallest reciprocal complementary Wiener numbers.     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20