Enumeration of Almost-Convex Polygons on the Square Lattice

We classify self-avoiding polygons on the square lattice according to a concavity measure, m, where 2m is the difference between the number of steps in the polygon and the perimeter of the minimal rectangle bounding the polygon. We generate series expansions for the perimeter generating functions S_m(x) for polygons of concavity m. We analyze the series S_m(x) for m = 0 to 3. If N_m,n denotes the number of polygons of perimeter 2n and concavity m, with m = o(n^1/2), we prove that N_m,n ? 2^2n?m?7n^m+1/m!, and that the radius of convergence of the series counting all polygons with m = o(n) is equal to 1/4. Our numerical data leads us to conjecture that in fact for m = o(n^1/2), a result confirmed for m = 0 and 1.     

Correlated equilibria of games with many players

Let G _m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G _m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than 2⁻ⁿ; and (2) for each 1<c<m, the solution set contains c ⁿ correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c ₁, …, c _l be independent and symmetric random vectors in R ^k, l≥k. Then the probability that the convex hull of c ₁, …, c _l intersects R ^k ₊ is greater than or equal to . Received: December 1998/Final version: March 2000     

Maximal triangle-free graphs with restrictions on the degrees

We investigate the problem that at least how many edges must a maximal triangle-free graph on n vertices have if the maximal valency is ≤D. Denote this minimum value by F(n, D). For large enough n, we determine the exact value of F(n, D) if D ≥ (n ? 2)/2 and we prove that lim F(n, cn)/n = K(c) exists for all 0 < c with the possible exception of a sequence c_k → 0. The determination of K(c) is a finite problem on all intervals [γ, ∞). For D = cn^?, 1/2 < ? < 1, we give upper and lower bounds for F(n, D) differing only in a constant factor. (Clearly, D < (n - 1)^1/2 is impossible in a maximal triangle-free graph.)     

The Hardness of 3-Uniform Hypergraph Coloring

We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n^1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c₂ > c₁ > 1, coloring a k-uniform c₁-colorable hypergraph with c₂ colors is NP-hard; the case k = 2, however, remains wide open. This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has ‘many’ non-monochromatic edges. * Research supported by NSF grant CCR-9987845. † Supported by an Alon Fellowship and by NSF grant CCR-9987845. ‡ Work supported in part by NSF grants CCF-9988526 and DMS 9729992, and the State of New Jersery.     

Estimates of maximal distances between spaces whose norms are invariant under a group of operators

We consider the class A_г of n-dimensional normed spaces with unit balls of the form: , where B _n ¹ n is the unit ball of ℓ _n ¹ , Γ is a finite group of orthogonal operators acting in ℝⁿ, and U is a “random” orthogonal transformation. It is proved that this class contains spaces with a large Banach-Mazur distance between them. If the cardinality of Γ is of order n^c, it is shown that, in the power scale, the diameter of A_г in the modified Banach-Mazur distance behaves as the classical diameter and is of order n. Bibliography: 8 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 333, 2006, pp. 33–42.     

Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

Isoperimetric Polygons of Maximum Width

The value is shown to be an upper bound on the width of any n-sided polygon with unit perimeter. This bound is reached when n is not a power of 2, and the corresponding optimal solutions are the regular polygons when n is odd and clipped regular Reuleaux polygons when n is even but not a power of 2. Using a global optimization algorithm, we show that the optimal width for the quadrilateral is with a precision of 10⁻⁴. We propose two mathematical programs to determine the maximum width when n=2 ^s with s≥3 and provide approximate, but near-optimal, solutions obtained by various heuristics and local optimization for n=8, 16, and 32. Work of the first author was supported by NSERC grant 239436-01, AFOSR FA9550-07-1-0302, and ExxonMobil. Work of the second author was supported by NSERC grant 239436-01.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

The equator map and the negative exponential functional

We define a negative exponential harmonic map from the ballB ⁿ of ℝ_n into the sphereS ⁿ of ℝ ⁿ⁺¹ . We prove that the equator map is a negative exponential harmonic map, but not stable for the negative exponential functional whenn≥2. Moreover, we consider maps from a ballB ⁿ into the unit sphereS ^m of ℝ_m+1 wherem≥2, and prove that no nonconstant, non surjective map can reach either the minimum or the maximum of the negative exponential functional.     

On Small World Semiplanes with Generalised Schubert Cells

The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog  _k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q ⁿ , where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.     

Long Monochromatic Berge Cycles in Colored 4-Uniform Hypergraphs

Here we prove that for n ≥ 140, in every 3-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a monochromatic Berge cycle of length at least n − 10. This result sharpens an asymptotic result obtained earlier. Another result is that for n ≥ 15, in every 2-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a 3-tight Berge cycle of length at least n − 10.     

Constructing Maximal Commutative Subalgebras of Matrix Rings in Small Dimensions

Let k denote an algebraically closed field of arbitrary characteristic. Let C denote the set of all commutative, finite dimensional, local k-algebras of the form (B, m, k) with i(m) ?2. Here i(m) denotes the index of nilpotency of the maximal ideal m. A Akalgebra (R, J,k)∈L is called a (c₁-construction if there exists (B, m, k)∈ £ ? {(k, (0), k)} and a finitely generated, faithful B-module N such that R,?B?(the idealization of N). (R.J.k) is called a (c_2::-construction if there exist a (B,m k)∈ L, a positive integer p $ge;2 and a nonzero z £ S_B(the socle of B) such that R?B[x]/(mX, X^p- z). Let M_n×n(K) denote the set of all n x n matrices, over k with n≥2. Let .M_n(k) denote the set of all maximal, commutative A;-subalgebras of M_n×n(k). In this paper, we show any (R J, k) ∈£?M_n;(k) with n>5 is a C₁ or C₂ -construction except for one isomorphism class. The one exception occurs when n = 5.     

Smallest maximally nonhamiltonian graphs II

Bollobás posed the problem of finding the least number of edges,f(n), in a maximally nonhamiltonian graph of ordern. Clark and Entringer showedf(n)=3n/2 for all evenn≥36 andf(n)=(3n+1)/2 or (3n+3)/2 for all oddn≥55. We showf(n)=(3n+1)/2 for all oddn≥53.     

A family of Bernstein quasi-interpolants on [0,1]

Suppose that we want to approximate f∈C[0,1] by polynomials inP, using only its values on X_n={i/n, 0≤i≤n}. This can be done by the Lagrange interpolant L_n f or the classical Bernstein polynomial B_n f. But, when n tends to infinity, L_n f does not converge to f in general and the convergence of B_n f to f is very slow. We define a family of operators B _n ^(k) , n≥k, which are intermediate ones between B _n ⁽⁰⁾ =B _n ⁽¹⁾ =B_n and B _n ⁽ⁿ⁾ =L_n, and we study some of their properties. In particular, we prove a Voronovskaja-type theorem which asserts that B _n ^(k) f−f=O(n^−[(k+2)/2]) for f sufficiently regular. Moreover, B _n ^(k) f uses only values of B_n f and its derivaties and can be computed by De Casteljau or subdivision algorithms.     

On numbers badly approximable by dyadic rationals

We consider a problem originating both from circle coverings and badly approximable numbers in the case of dyadic diophantine approximation. For the unit circle we give an elementary proof that the set {x ∈ : 2 ⁿ x ≥ c (mod 1) n ≥ 0} is a fractal set whose Hausdorff dimension depends continuously on c and is constant on intervals which form a set of Lebesgue measure 1. Hence it has a fractal graph. We completely characterize the intervals where the dimension remains unchanged. As a consequence we can describe the graph of c ↦ dim _H {x ∈ [0; 1]: x − m/2 ⁿ < c/2 ⁿ (mod 1) finitely often}.     

Cryptic Semigroup Varieties

We describe all minimal noncryptic periodic semigroup [monoid] varieties. We prove that there are exactly three distinct maximal cryptic semigroup [monoid] varieties contained in the variety determined by xⁿ ≈ x ^n+m, n ≥ 2, m ≥ 2. Analogous results are obtained for pseudovarieties: there are exactly three maximal cryptic pseudovarieties of semigroups [monoids]. It is shown that if a cryptic variety or pseudovariety of monoids contains a nonabelian group, then it consists of bands of groups only. Several characterizations are given of the cryptic overcommutative semigroup [monoid] varieties.     

The region of values of the system { f ( z 1),..., f ( z n )} in the class of typically real functions. III

The paper studies the region of values D_m,n(T) of the system {f(z₁), f(z₂),..., f(z_m), f(r₁), f(r₂),..., f(r_n)}, where m ≥ 1; n > 1; z_j, j = 1, ... m, are arbitrary fixed points of the disk U = {z: |z| < 1} with Im z_j ≠ 0, j = 1, 2, ..., m; r_j, 0 < r_j < 1, j = 1, 2, ..., n, are fixed; f ∈ T, and the class T consists of functions f(z) = z + c₂z² + ... regular in the disk U and satisfying the condition Im f(z) · Im z > 0 for Im z ≠= 0, z ∈ U. An algebraic characterization of the set D_m,n(T) in terms of nonnegative-definite Hermitian forms is provided, and all the boundary functions are described. As an implication, the region of values of f(z₁) in the subclass of functions f ∈ T with prescribed values f(r_j) (j = 1, 2, 3) is determined. Bibliography: 12 titles. Dedicated to the 100th anniversary of my father’s birthday __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 337, 2006, pp. 23–34.     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

The orthogonal convex skull problem

We give a combinatorial definition of the notion of a simple orthogonal polygon beingk-concave, wherek is a nonnegative integer. (A polygon is orthogonal if its edges are only horizontal or vertical.) Under this definition an orthogonal polygon which is 0-concave is convex, that is, it is a rectangle, and one that is 1-concave is orthoconvex in the usual sense, and vice versa. Then we consider the problem of computing an orthoconvex orthogonal polygon of maximal area contained in a simple orthogonal polygon. This is the orthogonal version of the potato peeling problem. AnO(n ²) algorithm is presented, which is a substantial improvement over theO(n ⁷) time algorithm for the general problem.The work of the first author was supported under a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692 and the work of the second author was partially supported by NSF Grants Nos. DCR-84-01898 and DCR-84-01633.