共查询到20条相似文献,搜索用时 46 毫秒
1.
The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h
L
(x) − h
L
(y)| ≤ k, where h
L
(x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed
the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point
reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width
2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique
linear extension that witnesses linear discrepancy 2.
The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290. 相似文献
2.
This article extends a paper of Abraham and Bonnet which generalised the famous Hausdorff characterisation of the class of
scattered linear orders. They gave an inductively defined hierarchy that characterised the class of scattered posets which
do not have infinite incomparability antichains (i.e. have the FAC). We define a larger inductive hierarchy κℌ* which characterises the closure of the class of all κ-well-founded linear orders under inversions, lexicographic sums and FAC weakenings. This includes a broader class of “scattered”
posets that we call κ-scattered. These posets cannot embed any order such that for every two subsets of size < κ, one being strictly less than the other, there is an element in between. If a linear order has this property and has size
κ it is unique and called ℚ(κ). Partial orders such that for every a < b the set {x: a < x < b} has size ≥ κ are called weakly κ-dense, and posets that do not have a weakly κ-dense subset are called strongly κ-scattered. We prove that κℌ* includes all strongly κ-scattered FAC posets and is included in the class of all FAC κ-scattered posets. For κ = ℵ0 the notions of scattered and strongly scattered coincide and our hierarchy is exactly aug(ℌ) from the Abraham-Bonnet theorem.
The authors warmly thank Uri Abraham for his many useful suggestions and comments. Mirna Džamonja thanks EPSRC for their support
on an EPSRC Advanced Fellowship. 相似文献
3.
The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h
L
(x)–h
L
(y)|≤k, where h
L
(x) is the height of x in L. Tanenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the
problem of characterizing the posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets
with linear discrepancy equal to 3 having the property that the deletion of any point results in a reduction in the linear
discrepancy. Howard determined that there are infinitely many such posets of width 2. We complete the forbidden subposet characterization
of posets with linear discrepancy equal to 2 by finding the minimal posets of width 3 with linear discrepancy equal to 3.
We do so by showing that, with a small number of exceptions, they can all be derived from the list for width 2 by the removal
of specific comparisons.
The first and second authors were supported during this research by National Science Foundation VIGRE grant DMS-0135290. 相似文献
4.
5.
We give a characterization of the class Co(F)\mathbf{Co}(\mathcal{F}) [Co(Fn)\mathrm{\mathbf{Co}}(\mathcal{F}_n), n < ω, respectively] of lattices isomorphic to convexity lattices of posets which are forests [forests of length at most n, respectively], as well as of the class Co(L)\mathbf{Co}(\mathcal{L}) of lattices isomorphic to convexity lattices of linearly ordered posets. This characterization yields that the class of finite
members from Co(F)\mathbf{Co}(\mathcal{F}) [from Co(Fn)\mathbf{Co}(\mathcal{F}_n), n < ω, or from Co(L)\mathbf{Co}(\mathcal{L})] is finitely axiomatizable within the class of finite lattices. 相似文献
6.
A graphG is calledrepresentable in a tree T, ifG is isomorphic to the intersection graph of a family of subtrees ofT. In this paper those graphs are characterized which are representable in some subdivision of theK
1,n. In the finite case polynomial-time recognition algorithms of these graphs are given. But this concept can be generalized
to essentially infinite graphs by using no more trees but ‘tree-like’ posets and representability of graphs in these posets. 相似文献
7.
In this paper we show that the number of pairwise nonisomorphic two-dimensional posets with n elements is asymptotically equivalent to 1/2n!. This estimate is based on a characterization, in terms of structural decomposition, of two-dimensional posets having a unique representation as the intersection of two linear extensions. 相似文献
8.
We study two kinds of segment orders, using definitions first proposed by Farhad Shahrokhi. Although the two kinds of segment
orders appear to be quite different, we prove several results suggesting that the are very much the same. For example, we
show that the following classes belong to both kinds of segment orders: (1) all posets having dimension at most 3; (2) interval
orders; and for n≥3, the standard example S
n
of an n-dimensional poset, all 1-element and (n−1)-element subsets of {1,2,…,n}, partially ordered by inclusion.
Moreover, we also show that, for each d≥4, almost all posets having dimension d belong to neither kind of segment orders. Motivated by these observations, it is natural to ask whether the two kinds of
segment orders are distinct. This problem is apparently very difficult, and we have not been able to resolve it completely.
The principal thrust of this paper is the development of techniques and results concerning the properties that must hold,
should the two kinds of segment orders prove to be the same. We also derive equivalent statements, one version of which is
a stretchability question involving certain sets of pseudoline arrangements. We conclude by proving several facts about continuous
universal functions that would transfer segment orders of the first kind into segments orders of the second kind. 相似文献
9.
D. N. Kozlov 《Discrete and Computational Geometry》1997,18(4):421-431
In this paper we describe the convex hulls of the sets of f- and β-vectors of different classes of simplicial complexes on n vertices. These include flag complexes, order complexes of posets, matroid complexes, and general abstract simplicial complexes.
As a result of this investigation, standard linear programming problems on these sets can be solved, including maximization
of the Euler characteristics or of the sum of the Betti numbers.
Received July 16, 1995, and in revised form May 1, 1996. 相似文献
10.
Bangming Deng 《中国科学A辑(英文版)》2000,43(11):1164-1173
This paper gives a complete classification of ℱ( Δ)-finite twisted double incidence algebras of posets in the case where the
Hasse quivers of posets are of type An. 相似文献
11.
Peter C. Fishburn 《Order》1999,16(4):335-396
Let M
n
(k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M
n
(k) is a semiorder and identifies all semiorders in M
n
(k) for k n. The present paper specifies M
n
(k) for all k 2 n – 3. 相似文献
12.
Radomír Halaš Vinayak Joshi Vilas S. Kharat 《Central European Journal of Mathematics》2010,8(5):985-991
A poset Q is called n-normal, if its every prime ideal contains at most n minimal prime ideals. In this paper, using the prime ideal theorem for finite ideal distributive posets, some properties
and characterizations of n-normal posets are obtained. 相似文献
13.
The Hom complex of homomorphisms between two graphs was originally introduced to provide topological lower bounds on the chromatic
number. In this paper we introduce new methods for understanding the topology of Hom complexes, mostly in the context of Γ-actions
on graphs and posets (for some group Γ). We view the Hom(T, ⊙) and Hom(⊙, G) complexes as functors from graphs to posets, and introduce a functor (⊙)1 from posets to graphs obtained by taking atoms as vertices. Our main structural results establish useful interpretations
of the equivariant homotopy type of Hom complexes in terms of spaces of equivariant poset maps and Γ-twisted products of spaces.
When P:= F(X) is the face poset of a simplicial complex X, this provides a useful way to control the topology of Hom complexes. These constructions generalize those of the second
author from [17] as well as the calculation of the homotopy groups of Hom complexes from [8]. 相似文献
14.
15.
Let Q be a convex solid in
n
, partitioned into two volumes u and v by an area s. We show that s>min(u,v)/diam Q, and use this inequality to obtain the lower bound n
-5/2 on the conductance of order Markov chains, which describe nearly uniform generators of linear extensions for posets of size n. We also discuss an application of the above results to the problem of sorting of posets.Computing Center of the USSR Academy of Sciences USSR 相似文献
16.
NS Condition of Admissibility for the Linear Estimator of Normal Mean with Unknown Variance 总被引:1,自引:0,他引:1
Xing Zhong XU Qi Guang WU 《数学学报(英文版)》2005,21(5):1083-1086
Suppose Y - N(β, σ^2 In), where β ∈ R^n and σ^2 〉 0 are unknown. We study the admissibility of linear estimators of mean vector under a quadratic loss function. A necessary and sufficient condition of the admissible linear estimator is given. 相似文献
17.
18.
Lacking an explicit formula for the numbers T
0(n) of all order relations (equivalently: T
0 topologies) on n elements, those numbers have been explored only up to n=13 (unlabeled posets) and n=15 (labeled posets), respectively.In a new approach, we used an orderly algorithm to (i) generate each unlabeled poset on up to 14 elements and (ii) collect enough information about the posets on 13 elements to be able to compute the number of labeled posets on 16 elements by means of a formula by Erné. Unlike other methods, our algorithm avoids isomorphism tests and can therefore be parallelized quite easily. The underlying principle of successively adding new elements to small objects is applicable to lattices and other kinds of order structures, too. 相似文献
19.
Abraham Neyman 《Israel Journal of Mathematics》1984,48(2-3):129-138
For fixed 1≦p<∞ theL
p-semi-norms onR
n
are identified with positive linear functionals on the closed linear subspace ofC(R
n
) spanned by the functions |<ξ, ·>|
p
, ξ∈R
n
. For every positive linear functional σ, on that space, the function Φσ:R
n
→R given by Φσ is anL
p-semi-norm and the mapping σ→Φσ is 1-1 and onto. The closed linear span of |<ξ, ·>|
p
, ξ∈R
n
is the space of all even continuous functions that are homogeneous of degreep, ifp is not an even integer and is the space of all homogeneous polynomials of degreep whenp is an even integer. This representation is used to prove that there is no finite list of norm inequalities that characterizes
linear isometric embeddability, in anyL
p unlessp=2.
Supported by the National Science Foundation MCS-79-06634 at U.C. Berkeley. 相似文献
20.
T. V. Budnyts’ka 《Ukrainian Mathematical Journal》2009,61(1):164-170
We consider affine mappings from ℝ
n
into ℝ
n
, n ≥ 1. We prove a theorem on the topological conjugacy of an affine mapping that has at least one fixed point to the corresponding
linear mapping. We give a classification, up to topological conjugacy, for affine mappings from R into R and also for affine
mappings from ℝ
n
into ℝ
n
, n > 1, having at least one fixed point and the nonperiodic linear part.
Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 61, No. 1, pp. 134–139, January, 2009. 相似文献