Tanenbaum, Trenk, and Fishburn introduced the concept of linear discrepancy in 2001, proposing it as a way to measure a partially ordered set's distance from being a linear order. In addition to proving a number of results about linear discrepancy, they posed eight challenges and questions for future work. This dissertation completely resolves one of those challenges and makes contributions on two others. This dissertation has three principal components: 3-discrepancy irreducible posets of width 3, degree bounds, and online algorithms for linear discrepancy. The first principal component of this dissertation provides a forbidden subposet characterization of the posets with linear discrepancy equal to 2 by completing the determination of the posets that are 3-irreducible with respect to linear discrepancy. The second principal component concerns degree bounds for linear discrepancy and weak discrepancy, a parameter similar to linear discrepancy. Specifically, if every point of a poset is incomparable to at most D other points of the poset, we prove three bounds: the linear discrepancy of an interval order is at most D, with equality if and only if it contains an antichain of size D; the linear discrepancy of a disconnected poset is at most the greatest integer less than or equal to (3D-1)/2; and the weak discrepancy of a poset is at most D. The third principal component of this dissertation incorporates another large area of research, that of online algorithms. We show that no online algorithm for linear discrepancy can be better than 3-competitive, even for the class of interval orders. We also give a 2-competitive online algorithm for linear discrepancy on semiorders and show that this algorithm is optimal.

In this thesis we study the following dimensional parameters : boxicity, cubicity, threshold dimension and poset dimension. While the first three parameters are defined on graphs, poset dimension is defined on partially ordered sets (or posets). We only consider finite graphs and posets. In addition, we assume that the graphs are simple and undirected. Boxicity and Cubicity: A k-box (k-cube) is a Cartesian product of closed intervals(unit-intervals) [a1,b1]x…x [ak,bk]. The boxicity (cubicity) of a graph G,box (G) (cub(G)) is the minimum integer k such that every vertex in G is mapped to a k-box(k-cube) in the k-dimensional Euclidean space and two boxes(cubes) intersect if and only if their corresponding vertices are adjacent in G. Boxicity and cubicity can be considered as extensions of the concept of interval graphs and unit-interval graphs respectively. Threshold Dimension: A graph G is a threshold graph if there is a real number p and a weight function w: V→ R such that for any two vertices u,,v ε V(G),{ u, v }is an edge if and only if w(u)+w(v) ≥ p. The threshold dimension of a graph G is the minimum integer k such that there exist k threshold graphs Gi, i =1,2,...,k which satisfy E(G)= E(G1)U E(G2)U….UE(Gk). Poset Dimension: Let P = (S, P)be a poset where S is a finite non-empty set and P is a reflexive, anti-symmetric and transitive binary relation on S. P is a total order if every pair of elements in S is comparable in P. The dimension of P , denoted by dim(P )is the minimum integer k such that there exist k total orders on S, L1,...,Lk and for two distinct elements x,y ε S: x < y in P if and only if x < y in each Li,i ε ,{1. 2,...,k } All the four dimensional parameters that we have considered are very hard to compute. It is NP-complete to even determine if the boxicity of a graph is at most 2, if its cubicity is at most 3, if its threshold dimension is at most 3 and if the dimension of a poset is at most 3. Also it is hard to design an approximation algorithm within √n factor for computing the dimension of a poset. OurResults We state some of our main results: 1. Lower bounds for boxicity: We have developed two general methods based on certain vertex isoperimetric properties of graphs for deriving lower bounds. Application of these methods has led to some significant results. We mention a few of them here: ( a) Almost all graphs have boxicity Ω(n). (b) For a fixed k, boxicity of random k-regular graphs is Ω(k/log k). 2. Consider a poset P = (S,P) and let GP be its underlying comparability graph. We show that for any poset P, box(GP)/(χ(GP) - 1) ≤ dim(P) ≤ 2box (GP), where χ(GP) is the chromatic number of GP and χ(GP) = 1. Some important consequences of this result are: (a) It allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) ≤ 2tree-width (GP) + 4. (b) The boxicity of any graph with maximum degree Δ is O (Δlog2 Δ) which is an improvement over the best known upper bound of Δ2 +2. (c) There exist graphs with boxicity Ω(ΔlogΔ). This disproves a conjecture that the boxicity of a graph is O(Δ). (d)There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices within a factor of O(n0.5−ε)for any ε > 0, unless NP = ZPP. 3.We show that every poset can be associated with a split graph such that the threshold dimension of the complement of the split graph is equal to the dimension of the poset. As a consequence we show that there exists no polynomial-time algorithm to approximate the threshold dimension of a split graph on n vertices with a factor of O(n0.5−ε)for any ε > 0, unless NP= ZPP. 4.We have given an upper bound for the cubicity of interval graphs. Claw number of a graph G, ψ(G) is the largest positive integer m such that K1,m is an induced subgraph of G. If G is an interval graph, we show that [log2 ψ(G)] ≤ cub(G) ≤ min([log2 α ], [log2 ψ(G)] +2), where α is the independence number of G. 5.We have improved upper bounds for the dimension of incidence posets and interval orders which are among the well-studied classes of posets.