## Type of Work

Article (82) Book (0) Theses (15) Multimedia (1)

## Peer Review

Peer-reviewed only (95)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (5)

## Publication Year

## Campus

UC Berkeley (8) UC Davis (12) UC Irvine (16) UCLA (22) UC Merced (3) UC Riverside (8) UC San Diego (23) UCSF (4) UC Santa Barbara (1) UC Santa Cruz (0) UC Office of the President (10) Lawrence Berkeley National Laboratory (37) UC Agriculture & Natural Resources (0)

## Department

Research Grants Program Office (RGPO) (10) University of California Research Initiatives (UCRI) (2) UC Lab Fees Research Program (LFRP); a funding opportunity through UC Research Initiatives (UCRI) (2)

Department of Earth System Science (7) Center for Comparative Immigration Studies (2) Department of Emergency Medicine (UCI) (2) UC Berkeley Library (1)

## Journal

Clinical Practice and Cases in Emergency Medicine (1) Journal of Education and Teaching in Emergency Medicine (1) Proceedings of the Annual Meeting of the Cognitive Science Society (1)

## Discipline

Physical Sciences and Mathematics (10) Life Sciences (2) Medicine and Health Sciences (2) Engineering (1) Social and Behavioral Sciences (1)

## Reuse License

BY - Attribution required (14) BY-NC-ND - Attribution; NonCommercial use; No derivatives (1)

## Scholarly Works (98 results)

When does a topological polyhedral complex (embedded in R^{d}) admit a geometric realization (a rectilinear embedding in R^{d})? What are the constraints on the possible realizations? Two classic results concerning such questions are Fary's theorem, which states that every planar graph can be drawn in the plane such that each edge is a straight line segment, and Tutte's theorem, which provides necessary and sufficient conditions for embedding a planar graph such that all faces are convex. The present work is motivated largely by the question of whether these types of results generalize to higher dimensions.

We begin by constructing an irrational polytopal complex consisting of 1278 convex 3-polytopes in R^{3}. The methods of this construction may also be used to produce small topological complexes with no geometric realization, as well as geometric complexes which encode arbitrary point and line configurations. This allows us to prove universality theorems for 3-dimensional polytopal complexes and arrangements. We also investigate geometric realizations of plane triangulations, and describe an explicit algorithm that embeds a plane triangulation with n vertices in a 4n^{3} x 8n^{5} integer grid, in such a way that at each step of the algorithm, the resulting region of the plane is convex. This embedding, by nature of its sequential convexity, may be lifted vertically to a 3-polytope. This process gives a new proof of Steinitz's Theorem for triangulations, and provides a new upper bound on the size of the integer grid necessary to embed the vertices of simplicial 3-polytopes. For certain classes of triangulations, this grid size is subexponential.

- 1 supplemental file

This paper offers three linked arguments. First, it argues that Japan alone amongst the industrialized democracies avoided importing guestworkers for decades due to the legacies in its experience of decolonization. The rapidity and abruptness of decolonization in Japan led to an extremely rigid entry control policy, which was closed to economic concerns. Second, the paper argues that the comparative study of immigration politics is ripe for the development of a theoretically grounded typology based on the institutional logics embedded in national migration regimes. Three ideal types are proposed: (1) decolonization (or post-colonial) regimes; (2) demographic regimes; and (3) economic (labor-market) regimes. The third argument is that “convergence” between national migration regimes exists in the layering of logics. That is, over time, most states have moved from regimes that are closer to one of the three ideal types to regimes that layer, or mix, multiple regimes.

We present some combinatorial results about finitely generated groups, particularly groups acting on rooted trees.

Given a finitely generated group G and a positive integer k, the product replacement graph Γ_{k}(G) is the graph whose vertices are generating k-tuples of G, and whose edges are Nielsen transformations between these generating k-tuples. We prove that if G has polynomial growth or G has exponential growth, then Γ_{k}(G) has exponential growth for sufficiently large k. We also prove with a direct combinatorial argument that Γ_{k}(**G**_{ω}) has exponential growth for k ≥ 5, where **G**_{ω} is the generalized Grigorchuk group.

We prove that Γ_{k}(G) is non-amenable for sufficiently large k in either of the following two cases: G is uniformly non-amenable, or G is virtually indicable. It follows that Γ_{k}(G) is non-amenable whenever G is a linear group, or a hyperbolic group, or an elementary amenable group.

We describe two Mealy automata, the Aleshin automaton and the Bellaterra automaton, whose Schreier graphs are conjectured to be expanders. We verify that these Schreier graphs have polylogarithmic diameter. We describe a class of Mealy automata for which the same is true. However, some members of this class do not give rise to expander graphs.

This dissertation investigates the difficulty of counting two classes of combinatorial objects, linear extensions of posets and contingency tables. For linear extensions of posets, we prove a number of hardness results. We show that computing the parity of the number of linear extensions of dimension two is parity-P-complete. We extend this result to show that counting linear extensions of dimension two posets is #P-complete, answering a question posed by M�hring and by Felsner and Wernisch. We also show that counting linear extensions of height two posets is #P-complete, resolving a conjecture of Brightwell and Winkler. We extend this result to show that incidence posets are #P-complete.

For the results about posets of dimension two we employed a computer search to construct families of permutations that behave as logic gates in a certain setting. The results about height two posets and incidence posets rely instead on gadgets that were constructed by hand.

For contingency tables, we work from the opposite direction, proving results about the feasibility of approximately counting and sampling tables. We give a new algorithm for approximating the number of contingency tables with fixed margins, which we call the SHM algorithm. We prove that the SHM algorithm is a fully polynomial random approximation scheme (FPRAS) for the number of tables for certain families of sparse margins. We then use this result to establish a polynomial mixing time for the Diaconis-Gangolli chain with sparse margins.

Using our SHM algorithm and techniques in discrete probability, we present experimental and theoretical evidence in support of answers to a number of questions Barvinok posed about the distribution of individual entries in contingency tables. In particular, we show that for a certain set of margins considered by Barvinok, and under certain assumptions about weak independence of entries, the distribution of the corner table entry exhibits a phase transition in mean and distribution.