共查询到20条相似文献,搜索用时 0 毫秒
1.
Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx
1<x
2 <...<x
k
such thatg(x
1)≦g(x
2)≦...≦g(x
k
). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it
will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1)
k
.
Dedicated to Paul Erdős on his seventieth birthday
Research supported in part by the National Science Foundation under ISP-80-11451. 相似文献
2.
Roger L. Jones Joseph M. Rosenblatt Má té Wierdl 《Proceedings of the American Mathematical Society》2001,129(5):1349-1358
In this paper we extend previously obtained results on norm inequalities for square functions, oscillation and variation operators, with actions, to the case of actions. The technique involves the use of a result about vector valued maximal functions, due to Fefferman and Stein, to reduce the problem to a situation where we can apply our previous results. 相似文献
3.
4.
《Computational Geometry》2005,30(1):59-77
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the -distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their -distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles.We study the following problem: given n non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i) for arbitrary graphs, the problem is NP-hard; (ii) for trees, we can solve the problem by linear programming on variables and constraints; (iii) for paths, we can solve the problem in time ; (iv) for rectangles sorted vertically along a path, the problem can be solved in time, and a -approximation can be computed in linear time. 相似文献
5.
Magic squares have been extremely useful and popular in combinatorics and statistics. One generalization of magic squares is magic rectangles which are useful for designing experiments in statistics. A necessary and sufficient condition for the existence of magic rectangles restricts the number of rows and columns to be either both odd or both even. In this paper, we generalize magic rectangles to even by odd nearly magic rectangles. We also prove necessary and sufficient conditions for the existence of a nearly magic rectangle, and construct one for each parameter set for which they exist. 相似文献
6.
7.
Byong-hun Ahn 《Operations Research Letters》1982,1(3):117-120
This paper presents a simple yet practically useful Gauss-Seidel iterative method for solving a class of nonlinear variational inequality problems over rectangles and of nonlinear complementarity problems. This scheme is a nonlinear generalization of a robust iterative method for linear complementarity problems developed by Mangasarian. Global convergence is presented for problems with Z-functions. It is noted that the suggested method can be viewed as a specific case of a class of linear approximation methods studied by Pang and others. 相似文献
8.
9.
E.G. Coffman Jr. George S. Lueker Joel Spencer Peter M. Winkler 《Probability Theory and Related Fields》2001,120(4):585-599
A random rectangle is the product of two independent random intervals, each being the interval between two random points
drawn independently and uniformly from [0,1]. We prove that te number C
n
of items in a maximum cardinality disjoint subset of n random rectangles satisfies
where K is an absolute constant. Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we are able to show that, for some absolute constat K,
Finally, for a certain distribution of random cubes we show that for some absolute constant K, the number Q
n
of items in a maximum cardinality disjoint subset of the cubes satisies
Received: 1 September 1999 / Revised version: 3 November 2000 / Published online: 14 June 2001 相似文献
10.
A new quadratic nonconforming finite element on rectangles (or parallelograms) is introduced. The nonconforming element consists of P2 ⊕ Span{x2y,xy2} on a rectangle and eight degrees of freedom. Our element is essentially of seven degrees of freedom since the degree of freedom associated with the integration on rectangle is essentially of bubble‐function nature. Global basis functions are constructed for both Dirichlet and Neumann type of problems; accordingly the corresponding dimensions are counted. The local and global interpolation operators are defined. Error estimates of optimal order are derived in both broken energy and L2(Ω) norms for second‐order of elliptic problems. Brief numerical results are also shown to confirm the optimality of the presented quadratic nonconforming element. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006 相似文献
11.
We investigate the connection between lozenge tilings and domino tilings by introducing a new family of regions obtained by attaching two different Aztec rectangles. We prove a simple product formula for the generating functions of the tilings of the new regions, which involves the statistics as in the Aztec diamond theorem (Elkies et al. (1992) [2], [3]). Moreover, we consider the connection between the generating function and MacMahon's q-enumeration of plane partitions fitting in a given box 相似文献
12.
For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r=2, this answers a question of S. Smorodinsky [S. Smorodinsky, On the chromatic number of some geometric hypergraphs, SIAM J. Discrete Math. 21 (2007) 676-687]. 相似文献
13.
Zhaoliang Meng Zhongxuan Luo Dongwoo Sheen 《Numerical Methods for Partial Differential Equations》2015,31(3):691-705
A new nonconforming rectangle element with cubic convergence for the energy norm is introduced. The degrees of freedom (DOFs) are defined by the 12 values at the three Gauss points on each of the four edges. Due to the existence of one linear relation among the above DOFs, it turns out the DOFs are 11. The nonconforming element consists of . We count the corresponding dimension for Dirichlet and Neumann boundary value problems of second‐order elliptic problems. We also present the optimal error estimates in both broken energy and norms. Finally, numerical examples match our theoretical results very well. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 691–705, 2015 相似文献
14.
Yaodong Cui 《Operations Research Letters》2006,34(6):630-638
This paper presents branch-and-bound algorithms that can guarantee the simplest optimal cutting patterns of equal rectangles. An existing linear algorithm determines the global upper bound exactly. The branching process ends when a branch of a lower bound equal to the global upper bound is found. 相似文献
15.
W. O. J. Moser 《Discrete Mathematics》1982,40(2-3):311-313
A formula is obtained for the number of three-line latin rectangles with first row normalized and second row a permutation which, in disjoint cycle form, has no cycles of prescribed lengths. 相似文献
16.
Given a set of n iso-oriented rectangles in 2-space we describe an algorithm which determines the contour of their union in O(n log n + p) time and O(n + p) space, where p is the number of edges in the contour. This performance is time-optimal. The space requirements are the same as in the best previously known algorithm. We achieve this by introducing a new data structure, the contracted segment tree, which is a non-trivial modification of the well known segment tree. If only the pieces of the contour are to be reported then this approach yields a time- and space-optimal algorithm. 相似文献
17.
《Discrete Mathematics》2019,342(12):111607
We prove an upper bound for the independence number of a graph in terms of the largest Laplacian eigenvalue, and of a certain induced subgraph. Our bound is a refinement of a well-known Hoffman-type bound. 相似文献
18.
I. F. Sharygin 《Mathematical Notes》1972,12(4):680-684
Let D be a subset of the s-dimensional lattice ZS, M=M(D) the number of elements in D,
Dthe space of trigonometric polynomials on the torus TS with spectrum concentrated in D and having unit norm in L2(TS). In this paper we give the following bound for the Gel'fand diameter:d
n(
D,C(Ts))M/2–N/2. This bound is subsequently used for actual functional classes.Translated from Matematicheskie Zametki, Vol. 12, No. 4, pp. 413–419, October, 1972. 相似文献
19.
S. A. Sander 《Siberian Mathematical Journal》1989,30(4):635-636
Novosibirsk. Translated from Sibirskii Matematicheskii Zhurnal, Vol. 30, No. 4, pp. 171–173, July–August, 1989. 相似文献
20.
Hazarika Irani Mahanta Anjana Kakoti 《Advances in Data Analysis and Classification》2022,16(3):593-616
Advances in Data Analysis and Classification - Interval data, a special case of symbolic data, are becoming more frequent in different fields of applications due to the uncertainty in the... 相似文献