| Discrete Mathematics & Theoretical Computer Science |
DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)
Robert Cori, Jacques Mazoyer, Michel Morvan and Rémy Mosseri (eds.), Proceedings of *Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001*
1. Characterization of Lattices Induced by (extended) Chip Firing Games
The Chip Firing Game (CFG) is a discrete dynamical model used in physics, computer science and economics. It is known that the set of configurationsreachable from an initial configuration (this set is called the \textitconfiguration space) can be ordered as a lattice. We first present a structural result about this model, which allows us to introduce some useful tools for describing those lattices. Then we establish that the class of lattices that are the configuration space of a CFG is strictly between the class of distributive lattices and the class of upper locally distributive (or ULD) lattices. Finally we propose an extension of the model, the \textitcoloured Chip Firing Game, which generates exactly the class of ULD lattices.
Section:
Proceedings
2. The Chip Firing Game and Matroid Complexes
In this paper we construct from a cographic matroid M, a pure multicomplex whose degree sequence is the h―vector of the the matroid complex of M. This result provesa conjecture of Richard Stanley [Sta96] in the particular case of cographic matroids. We also prove that the multicomplexes constructed are M―shellable, so proving a conjecture of Manoj Chari [Cha97] again in the case of cographic matroids. The proofs use results on a game for graphs called the chip firing game.
Section:
Proceedings
3. Partitions of an Integer into Powers
In this paper, we use a simple discrete dynamical model to study partitions of integers into powers of another integer. We extend and generalize some known results about their enumeration and counting, and we give new structural results. In particular, we show that the set of these partitions can be ordered in a natural way which gives the distributive lattice structure to this set. We also give a tree structure which allow efficient and simple enumeration of the partitions of an integer.
Section:
Proceedings
4. Performance Evaluation of Demodulation Methods: a Combinatorial Approach
This paper provides a combinatorial approach for analyzing the performance of demodulation methods used in GSM. We also show how to obtain combinatorially a nice specialization of an important performance evaluation formula, using its connection with a classical bijection of Knuth between pairs of Young tableaux and {0,1}-matrices.
Section:
Proceedings
5. A Sequential Search Distribution: Proofreading, Russian Roulette, and the Incomplete q-Eulerian Polynomials
The distribution for the number of searches needed to find k of n lost objects is expressed in terms of a refinement of the q-Eulerian polynomials, for which formulae are developed involving homogeneous symmetric polynomials. In the case when k=n and the find probability remains constant, relatively simple and efficient formulas are obtained.From our main theorem, we further (1) deduce the inverse absorption distribution and (2) determine the expected number of times the survivor pulls the trigger in an n-player game of Russian roulette.
Section:
Proceedings
6. Tiling the Line with Triples
It is known the one dimensional prototile $0,a,a+b$ and its reflection $0,b,a+b$ always tile some interval. The subject has not received a great deal of further attention, although many interesting questions exist. All the information about tilings can be encoded in a finite digraph $D_{ab}$. We present several results about cycles and other structures in this graph. A number of conjectures and open problems are given.In [Go] an elegant proof by contradiction shows that a greedy algorithm will produce an interval tiling. We show that the process of converting to a direct proof leads to much stronger results.
Section:
Proceedings
7. On the Toppling of a Sand Pile
In this paper, we provide the first study of the sand pile model SPM(0) where we assume that all the grains are numbered with a distinct integer.We obtain a lower bound on the number of terminal sand piles by establishing a bijection between a subset of these sand piles and the set of shifted Young tableaux. We then prove that this number is at least factorial.
Section:
Proceedings
8. Megamaps: Construction and Examples
We consider the usual model of hypermaps or, equivalently, bipartite maps, represented by pairs of permutations that act transitively on a set of edges E. The specific feature of our construction is the fact that the elements of E are themselves (or are labelled by) rather complicated combinatorial objects, namely, the 4-constellations, while the permutations defining the hypermap originate from an action of the Hurwitz braid group on these 4-constellations.The motivation for the whole construction is the combinatorial representation of the parameter space of the ramified coverings of the Riemann sphere having four ramification points.
Section:
Proceedings
9. Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis
We present a characteristic-free algorithm for computing minimal generating sets of invariant rings of permutation groups. We circumvent the main weaknesses of the usual approaches (using classical Gröbner basis inside the full polynomial ring, or pure linear algebra inside the invariant ring) by relying on the theory of SAGBI- Gröbner basis. This theory takes, in this special case, a strongly combinatorial flavor, which makes it particularly effective. Our algorithm does not require the computation of a Hironaka decomposition, nor even the computation of a system of parameters, and could be parallelized. Our implementation, as part of the library $permuvar$ for $mupad$, is in many cases much more efficient than the other existing software.
Section:
Proceedings
10. A Poset Classifying Non-Commutative Term Orders
We study a poset $\Re$ on the free monoid (X*) on a countable alphabet X.This poset is determined by the fact that its total extensions are precisely the standard term orders on X*. We also investigate the poset classifying degree-compatible standard term orders, and the poset classifying sorted term orders. For the latter poset, we give a Galois coconnection with the Young lattice.
Section:
Proceedings
11. Tilings of a Domain on a Hexagon Mesh with Balanced 3-Tiles
In this article, we study the question of tilings on a hexagon mesh with balanced 3-tiles. This problem has been studied by Conway and Lagarias in [CL90], by studying the tiling groups, in fact a group containing the tiling-groups, and their Cayley graphs. We will use two different approaches. The first one is based on matchings in bipartite graphs, which in this case are in correspondance with tilings of domains by lozenges, and thus can be efficiently studied, using Thurston's algorithm (see [Thu90]). The second one is based on a color and balancing approach of Thurston's algorithm, exposed in [Fou96].
Section:
Proceedings
12. Larger than Life: Digital Creatures in a Family of Two-Dimensional Cellular Automata
We introduce the Larger than Life family of two-dimensional two-state cellular automata that generalize certain nearest neighbor outer totalistic cellular automaton rules to large neighborhoods. We describe linear and quadratic rescalings of John Conway's celebrated Game of Life to these large neighborhood cellular automaton rules and present corresponding generalizations of Life's famous gliders and spaceships. We show that, as is becoming well known for nearest neighbor cellular automaton rules, these ``digital creatures'' are ubiquitous for certain parameter values.
Section:
Proceedings
13. On Minimal Strings Containing the Elements of S_n by Decimation
The permutations by decimation problem is thought to be applicable to computer graphics, and raises interesting theoretical questions in combinatory theory.We present the results of some theoretical and practical investigation into this problem.We show that sequences of this form are $O(n^2)$ in length, but finding optimal solutions can be difficult.
Section:
Proceedings
14. Periodic Patterns in Orbits of Certain Linear Cellular Automata
We discuss certain linear cellular automata whose cells take values in a finite field. We investigate the periodic behavior of the verticals of an orbit of the cellular automaton and establish that there exists, depending on the characteristic of the field, a universal behavior for the evolution of periodic verticals.
Section:
Proceedings
15. Tilings, Quasicrystals, Discrete Planes, Generalized Substitutions, and Multidimensional Continued Fractions
The aim of this paper is to give an overview of recent results about tilings, discrete approximations of lines and planes, and Markov partitions for toral automorphisms.The main tool is a generalization of the notion of substitution. The simplest examples which correspond to algebraic parameters, are related to the iteration of one substitution, but we show that it is possible to treat arbitrary irrationalexamples by using multidimensional continued fractions.We give some non-trivial applications to Diophantine approximation, numeration systems and tilings, and we expose the main unsolved questions.
Section:
Proceedings
16. The Many Faces of Alternating-Sign Matrices
I give a survey of different combinatorial forms of alternating-sign matrices, starting with the original form introduced by Mills, Robbins and Rumsey as well as corner-sum matrices, height-function matrices, three-colorings, monotone triangles, tetrahedral order ideals, square ice, gasket-and-basket tilings and full packings of loops.
Section:
Proceedings
17. An n-Dimensional Generalization of the Rhombus Tiling
Several classic tilings, including rhombuses and dominoes, possess height functions which allow us to 1) prove ergodicity and polynomial mixing times for Markov chains based on local moves, 2) use coupling from the past to sample perfectly random tilings, 3) map the statistics of random tilings at large scales to physical models of random surfaces, and and 4) are related to the "arctic circle"' phenomenon.However, few examples are known for which this approach works in three or more dimensions.Here we show that the rhombus tiling can be generalized to n-dimensional tiles for any $n ≥ 3$. For each $n$, we show that a certain local move is ergodic, and conjecture that it has a mixing time of $O(L^{n+2} log L)$ on regions of size $L$. For $n=3$, the tiles are rhombohedra, and the local move consists of switching between two tilings of a rhombic dodecahedron.We use coupling from the past to sample random tilings of a large rhombic dodecahedron, and show that arctic regions exist in which the tiling is frozen into a fixed state.However, unlike the two-dimensional case in which the arctic region is an inscribed circle, here it seems to be octahedral.In addition, height fluctuations between the boundary of the region and the center appear to be constant rather than growing logarithmically.We conjecture that this is because the physics of the model is in a "smooth" phase where it is rigid at large scales, rather than a "rough" phase in which it is […]
Section:
Proceedings
18. Gardens of Eden and Fixed Points in Sequential Dynamical Systems
A class of finite discrete dynamical systems, called <b>Sequential Dynamical Systems</b> (SDSs), was proposed in [BMR99,BR99] as an abstract model of computer simulations. Here, we address some questions concerning two special types of the SDS configurations, namely Garden of Eden and Fixed Point configurations. A configuration $C$ of an SDS is a Garden of Eden (GE) configuration if it cannot be reached from any configuration. A necessary and sufficient condition for the non-existence of GE configurations in SDSs whose state values are from a finite domain was provided in [MR00]. We show this condition is sufficient but not necessary for SDSs whose state values are drawn from an infinite domain. We also present results that relate the existence of GE configurations to other properties of an SDS. A configuration $C$ of an SDS is a fixed point if the transition out of $C$ is to $C$ itself. The FIXED POINT EXISTENCE (or FPE) problem is to determine whether a given SDS has a fixed point. We show thatthe FPE problem is <b>NP</b>-complete even for some simple classes of SDSs (e.g., SDSs in which each local transition function is from the set{NAND, XNOR}). We also identify several classes of SDSs (e.g., SDSs with linear or monotone local transition functions) for which the FPE problem can be solved efficiently.
Section:
Proceedings
19. Enumerating Triangulations of Convex Polytopes
A triangulation of a finite point set A in $\mathbb{R}^d$ is a geometric simplicial complex which covers the convex hull of $A$ and whose vertices are points of $A$. We study the graph of triangulations whose vertices represent the triangulations and whose edges represent geometric bistellar flips. The main result of this paper is that the graph of triangulations in three dimensions is connected when the points of $A$ are in convex position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in $O(log log n)$ time per triangulation.
Section:
Proceedings
20. New Bounds for Hypercube Slicing Numbers
What is the maximum number of edges of the d-dimensional hypercube, denoted by S(d,k), that can be sliced by k hyperplanes? This question on combinatorial properties of Euclidean geometry arising from linear separability considerations in the theory of Perceptrons has become an issue on its own. We use computational and combinatorial methods to obtain new bounds for S(d,k), d ≤ 8. These strengthen earlier results on hypercube cut numbers.
Section:
Proceedings
21. Representing Reversible Cellular Automata with Reversible Block Cellular Automata
Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks.We prove that any d-dimensional reversible cellular automaton can be exp ressed as thecomposition of d+1 block permutations.We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus <i>(Physica D 45)</i> improved by Kari in 1996 <i>(Mathematical System Theory 29)</i>.
Section:
Proceedings
22. A Bijection for Directed-Convex Polyominoes
In this paper we consider two classes of lattice paths on the plane which use \textitnorth, \textiteast, \textitsouth,and \textitwest unitary steps, beginningand ending at (0,0).We enumerate them according to the number ofsteps by means of bijective arguments; in particular, we apply the cycle lemma.Then, using these results, we provide a bijective proof for the number of directed-convex polyominoes having a fixed number of rows and columns.
Section:
Proceedings
23. Pseudo-Permutations II: Geometry and Representation Theory
In this paper, we provide the second part of the study of the pseudo-permutations. We first derive a complete analysis of the pseudo-permutations, based on hyperplane arrangements, generalizing the usual way of translating the permutations. We then study the module of the pseudo-permutations over the symmetric group and provide the characteristics of this action.
Section:
Proceedings
24. Mixing Times of Plane Random Rhombus Tilings
We address the question of single flip discrete dynamics in sets of two-dimensional random rhombus tilings with fixed polygonal boundaries. Single flips are local rearrangements of tiles which enable to sample the configuration sets of tilings via Markov chains. We determine the convergence rates of these dynamical processes towards the statistical equilibrium distributions and we demonstrate that the dynamics are rapidly mixing: the ergodic times are polynomial in the number of tiles up to logarithmic corrections. We use an inherent symmetry of tiling sets which enables to decompose them into smaller subsets where a technique from probability theory, the so-called coupling technique, can be applied. We also point out an interesting occurrence in this work of extreme-value statistics, namely Gumbel distributions.
Section:
Proceedings