Dartmouth College Computer Science Technical Report series CS home TR home TR search TR listserv By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Algorithmic Problems Arising in Posets and Permutations
Dartmouth TR2016-795

Abstract: Partially ordered sets and permutations are combinatorial structures having vast applications in theoretical computer science. In this thesis, we study various computational and algorithmic problems related to these structures.

The first chapter of the thesis contains discussion about randomized fully polynomial approximation schemes obtained by employing Markov chain Monte Carlo. In this chapter we study various Markov chains that we call: the gladiator chain, the interval chain, and cube shuffling. Our objective is to identify some conditions that assure rapid mixing; and we obtain partial results.

The gladiator chain is a biased random walk on the set of permutations. This chain is related to self organizing lists, and various versions of it have been studied. The interval chain is a random walk on the set of points in $\mathbb{R}^n$ whose coordinates respect a partial order. Since the sample space of the interval chain is continuous, many mixing techniques for discrete chains are not applicable to it. The cube shuffle chain is a generalization of H\r{a}stad's square shuffle. The importance of this chain is that it mixes in constant number of steps.

In the second chapter, we are interested in calculating expected value of real valued function $f:S\rightarrow \mathbb{R}$ on a set of combinatorial structures $S$, given a probability distribution on it. We first suggest a Markov chain Monte Carlo approach to this problem. We identify the conditions under which our proposed solution will be efficient, and present examples where it fails. Then, we study homomesy. Homomesy is a phenomenon introduced by Jim Propp and Tom Roby. We say the triple $\langle S, \tau,f\rangle$ ($\tau$ is a permutation mapping $S$ to itself) exhibits homomesy, if the average of $f$ along all $\tau$-orbits of $S$ is a constant only depending on $f$ and $S$. We study homomesy and obtain some results when $S$ is the set of ideals in a class of simply described lattices.

Note:

PDF (1443KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
Shahrzad Haddadan, "Algorithmic Problems Arising in Posets and Permutations." Dartmouth Computer Science Technical Report TR2016-795, May 2016.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.