The LYM property of a finite standard graded poset is one of the central notions in Sperner theory. It is known that the product of two finite standard graded posets satisfying the LYM properties may not have the LYM property again. In 1974, Harper proved that if two finite standard graded posets satisfying the LYM properties also satisfy rank logarithmic concavities, then their product also satisfies these two properties. However, Harper's proof is rather non-intuitive. Giving a natural proof of Harper's theorem is one of the goals of this thesis. The main new result of this thesis is a characterization of rank-finite standard graded LYM posets that satisfy rank logarithmic concavities. With this characterization theorem, we are able to give a new, natural proof of Harper's theorem. In fact, we prove a strengthened version of Harper's theorem by weakening the finiteness condition to the rank-finiteness condition. We present some interesting applications of the main characterization theorem. We also give a brief history of Sperner theory, and summarize all the ingredients we need for the main theorem and its applications, including a new equivalent condition for the LYM property that is a key for proving our main theorem.

The LYM property of a finite standard graded poset is one of the central notions in Sperner theory. It is known that the product of two finite standard graded posets satisfying the LYM properties may not have the LYM property again. In 1974, Harper proved that if two finite standard graded posets satisfying the LYM properties also satisfy rank logarithmic concavities, then their product also satisfies these two properties. However, Harper's proof is rather non-intuitive. Giving a natural proof of Harper's theorem is one of the goals of this thesis. The main new result of this thesis is a characterization of rank-finite standard graded LYM posets that satisfy rank logarithmic concavities. With this characterization theorem, we are able to give a new, natural proof of Harper's theorem. In fact, we prove a strengthened version of Harper's theorem by weakening the finiteness condition to the rank-finiteness condition. We present some interesting applications of the main characterization theorem. We also give a brief history of Sperner theory, and summarize all the ingredients we need for the main theorem and its applications, including a new equivalent condition for the LYM property that is a key for proving our main theorem.

Thesis (Ph.D.)--Syracuse University, 2008. / "Publication number: AAT 3323082."

Modern software systems have been pervasively concurrent to utilize parallel hardware and perform asynchronous tasks. The correctness of concurrent programming, however, has been challenging for real-world and large systems. As the concurrent events of a system can interleave arbitrarily, unexpected interleavings may lead the system to undefined states, resulting in denials of services, performance degradation, inconsistent data, security issues, etc. To detect such concurrency errors, concurrency testing repeatedly explores the interleavings of a system to find the ones that induce errors. Traditional systematic testing, however, suffers from the intractable number of interleavings due to the complexity in real-world systems. Moreover, each iteration in systematic testing adjusts the explored interleaving with a minimal change that swaps the ordering of two events. Such exploration may waste time in large homogeneous sub-spaces leading to the same testing result. Thus on real-world systems, systematic testing often performs poorly to reveal even simple errors within a limited time budget. On the other hand, randomized testing samples interleavings of the system to quickly surface simple errors with substantial chances, but it may as well explore equivalent interleavings that do not affect the testing results. Such redundancies weaken the probabilistic guarantees and performance of randomized testing to find any errors. Towards effective concurrency testing, this thesis leverages partial order semantics with randomized testing to find errors with strong probabilistic guarantees. First, we propose partial order sampling (POS), a new randomized testing framework to sample interleavings of a concurrent program with a novel partial order method. It effectively and simultaneously explores the orderings of all events of the program, and has high probabilities to manifest any errors of unexpected interleavings. We formally proved that our approach has exponentially better probabilistic guarantees to sample any partial orders of the program than state-of-the-art approaches. Our evaluation over 32 known concurrency errors in public benchmarks shows that our framework performed 2.6 times better than state-of-the-art approaches to find the errors. Secondly, we describe Morpheus, a new practical concurrency testing tool to apply POS to high-level distributed systems in Erlang. Morpheus leverages dynamic analysis to identify and predict critical events to reorder during testing, and significantly improves the exploration effectiveness of POS. We performed a case study to apply Morpheus on four popular distributed systems in Erlang, including Mnesia, the database system in standard Erlang distribution, and RabbitMQ, the message broker service. Morpheus found 11 previously unknown errors leading to unexpected crashes, deadlocks, and inconsistent states, demonstrating the effectiveness and practicalness of our approaches.

No description available.

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 dissertation we solve several combinatorial problems in different areas of mathematics: automata theory, combinatorics of partially ordered sets and extremal combinatorics. Firstly, we focus on some new automata that do not seem to have occurred much in the literature, that of solvability of mazes. For our model, a maze is a countable strongly connected digraph together with a proper colouring of its edges (without two edges leaving a vertex getting the same colour) and two special vertices: the origin and the destination. A pointer or robot starts in the origin of a maze and moves naturally between its vertices, according to a sequence of specific instructions from the set of all colours; if the robot is at a vertex for which there is no out-edge of the colour indicated by the instruction, it remains at that vertex and proceeds to execute the next instruction in the sequence. We call such a finite or infinite sequence of instructions an algorithm. In particular, one of the most interesting and very natural sets of mazes occurs when our maze is the square lattice Z2 as a graph with some of its edges removed. Obviously, we need to require that the origin and the destination vertices are in the same connected component and it is very natural to take the four instructions to be the cardinal directions. In this set-up, we make progress towards a beautiful problem posed by Leader and Spink in 2011 which asks whether there is an algorithm which solves the set of all such mazes. Next, we address a problem regarding symmetric chain decompositions of posets. We ask if there exists a symmetric chain decomposition of a 2 × 2 × ... × 2 × n cuboid (k 2’s) such that no chain has a subchain of the form (a1,...,ak,0) ≺ ... ≺ (a1,...,ak,n−1)? We show this is true precisely when k≥5 and n≥3. Thisquestion arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this chapter unexpectedly resolves the most difficult case of previous work by Spink on almost orthogonal symmetric chain decompositions (2017) which makes progress on a conjecture of Shearer and Kleitman. Moreover, we generalize our methods to other finite graded posets. Finally, we address two different problems in extremal combinatorics related to mathematical physics. Firstly, we study metastable states in the Ising model. We propose a general model for 1-flip spin systems, and initiate the study of extremal properties of their stable states. By translating local stability conditions into Sperner- type conditions, we provide non-trivial upper bounds which are often tight for large classes of such systems. The last topic we consider is a deterministic bootstrap percolation type problem. More specifically, we prove several extremal results about fast 2-neighbour percolation on the two dimensional grid.

In 2001, Fishburn, Tanenbaum, and Trenk published a pair of papers that introduced the notions of linear and weak discrepancy of a partially ordered set or poset. Linear discrepancy for a poset is the least k such that for any ordering of the points in the poset there is a pair of incomparable points at least distance k away in the ordering. Weak discrepancy is similar to linear discrepancy except that the distance is observed over weak labelings (i.e. two points can have the same label if they are incomparable, but order is still preserved). My thesis gives a variety of results pertaining to these properties and other forms of discrepancy in posets. The first chapter of my thesis partially answers a question of Fishburn, Tanenbaum, and Trenk that was to characterize those posets with linear discrepancy two. It makes the characterization for those posets with width two and references the paper where the full characterization is given. The second chapter introduces the notion of t-discrepancy which is similar to weak discrepancy except only the weak labelings with at most t copies of any label are considered. This chapter shows that determining a poset's t-discrepancy is NP-Complete. It also gives the t-discrepancy for the disjoint sum of chains and provides a polynomial time algorithm for determining t-discrepancy of semiorders. The third chapter presents another notion of discrepancy namely total discrepancy which minimizes the average distance between incomparable elements. This chapter proves that finding this value can be done in polynomial time unlike linear discrepancy and t-discrepancy. The final chapter answers another question of Fishburn, Tanenbaum, and Trenk that asked to characterize those posets that have equal linear and weak discrepancies. Though determining the answer of whether the weak discrepancy and linear discrepancy of a poset are equal is an NP-Complete problem, the set of minimal posets that have this property are given. At the end of the thesis I discuss two other open problems not mentioned in the previous chapters that relate to linear discrepancy. The first asks if there is a link between a poset's dimension and its linear discrepancy. The second refers to approximating linear discrepancy and possible ways to do it.

This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.

This thesis contains several results concerning the combinatorics of partially ordered sets (posets) which are either of enumerative or extremal nature. <br><br> The first concerns conjectures of Friedland and Kahn, which state that the (extremal) d-regular graph on N vertices containing both the maximal number of matchings and independent sets of a fixed size is the graph consisting of disjoint union of appropriate number of complete bipartite d-regular graphs on 2d vertices. We show that the conjectures are true in an asymptotic sense, using entropy techniques. <br><br> As a second result, we give tight bounds on the size of the largest Boolean family which contains no three distinct subsets forming an "induced V" (i.e. if A,B,C are all in our family, if C is contained in the intersection of A B, A must be a subset of B). This result, though similar to known results, gives the first bound on a family defined by an induced property. <br><br> We pose both Dedekind-type questions concerning the number of antichains and a Stanley-type question concerning the number of linear extensions in generalized Boolean lattices; namely, products of chain posets and the poset of partially defined functions. We provide asymptotically tight bounds for these problems. <br><br> A Boolean function, f, is called cherry-free if for all triples x,y,z where z covers both x and y, f(z)=1 whenever both f(x)=1 and f(y)=1. We give bounds on the number of cherry-free functions on bipartite regular posets, with stronger results for bipartite posets under an additional co-degree hypotheses. We discuss applications of these functions to Boolean Horn functions and similar structures in ranked regular posets.