Generating trees and other combinatorial objects lexicographically /

"UILU-ENG 77 1762."

Representing Equivalence Problems for Combinatorial Objects

Methods for representing equivalence problems of various combinatorial objects as graphs or binary matrices are considered. Such representations can be used for isomorphism testing in classification or generation algorithms. Often it is easier to consider a graph or a binary matrix isomorphism problem than to implement heavy algorithms depending especially on particular combinatorial objects. Moreover, there already exist well tested algorithms for the graph isomorphism problem (nauty) and the binary matrix isomorphism problem as well (Q-Extension). ACM Computing Classification System (1998): F.2.1, G.4.

Applications of finite geometries to designs and codes

This dissertation concerns the intersection of three areas of discrete mathematics: finite geometries, design theory, and coding theory. The central theme is the power of finite geometry designs, which are constructed from the points and t-dimensional subspaces of a projective or affine geometry. We use these designs to construct and analyze combinatorial objects which inherit their best properties from these geometric structures. A central question in the study of finite geometry designs is Hamada’s conjecture, which proposes that finite geometry designs are the unique designs with minimum p-rank among all designs with the same parameters. In this dissertation, we will examine several questions related to Hamada’s conjecture, including the existence of counterexamples. We will also study the applicability of certain decoding methods to known counterexamples. We begin by constructing an infinite family of counterexamples to Hamada’s conjecture. These designs are the first infinite class of counterexamples for the affine case of Hamada’s conjecture. We further demonstrate how these designs, along with the projective polarity designs of Jungnickel and Tonchev, admit majority-logic decoding schemes. The codes obtained from these polarity designs attain error-correcting performance which is, in certain cases, equal to that of the finite geometry designs from which they are derived. This further demonstrates the highly geometric structure maintained by these designs. Finite geometries also help us construct several types of quantum error-correcting codes. We use relatives of finite geometry designs to construct infinite families of q-ary quantum stabilizer codes. We also construct entanglement-assisted quantum error-correcting codes (EAQECCs) which admit a particularly efficient and effective error-correcting scheme, while also providing the first general method for constructing these quantum codes with known parameters and desirable properties. Finite geometry designs are used to give exceptional examples of these codes.

Formal group laws and hypergraph colorings

Thesis (Ph.D.)--University of Washington, 2016-06

Poset associahedra as sections of graph associahedra

Poset associahedra are a family of convex polytopes recently introduced by Pavel Galashin in 2021. The associahedron An is an (n-2)-dimensional convex polytope whose facial structure encodes the ways of parenthesizing an n-letter word (among several equivalent combinatorial objects). Associahedra are deeply studied polytopes that appear naturally in many areas of mathematics: algebra, combinatorics, geometry, topology... They have many presentations and generalizations. One of their incarnations is as a compactification of the configuration space of n points on a line. Similarly, the P-associahedron of a poset P is a compactification of the configuration space of order preserving maps from P to R. Galashin presents poset associahedra as combinatorial objects and shows that they can be realized as convex polytopes. However, his proof is not constructive, in the sense that no explicit coordinates are provided. The main goal of this thesis is to provide an explicit construction of poset associahedra as sections of graph associahedra, thus solving the open problem stated in Remark 1.5 of Galashin's paper.

Associating optical measurements and estimating orbits of geocentric objects through population-based meta-heuristic methods

Currently several thousands of objects are being tracked in the MEO and GEO regions through optical means. The problem faced in this framework is that of Multiple Target Tracking (MTT). In this context both, the correct associations among the observations and the orbits of the objects have to be determined. The complexity of the MTT problem is defined by its dimension S. The number S corresponds to the number of fences involved in the problem. Each fence consists of a set of observations where each observation belongs to a different object. The S ≥ 3 MTT problem is an NP-hard combinatorial optimization problem. There are two general ways to solve this. One way is to seek the optimum solution, this can be achieved by applying a branch-and- bound algorithm. When using these algorithms the problem has to be greatly simplified to keep the computational cost at a reasonable level. Another option is to approximate the solution by using meta-heuristic methods. These methods aim to efficiently explore the different possible combinations so that a reasonable result can be obtained with a reasonable computational effort. To this end several population-based meta-heuristic methods are implemented and tested on simulated optical measurements. With the advent of improved sensors and a heightened interest in the problem of space debris, it is expected that the number of tracked objects will grow by an order of magnitude in the near future. This research aims to provide a method that can treat the correlation and orbit determination problems simultaneously, and is able to efficiently process large data sets with minimal manual intervention.

Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

PARALLAXES OF SOUTHERN EXTREMELY COOL OBJECTS. I. TARGETS, PROPER MOTIONS, AND FIRST RESULTS

We present results from the PARallaxes of Southern Extremely Cool objects ( PARSEC) program, an observational program begun in 2007 April to determine parallaxes for 122 L and 28 T southern hemisphere dwarfs using the Wide Field Imager on the ESO 2.2 m telescope. The results presented here include parallaxes of 10 targets from observations over 18 months and a first version proper motion catalog. The proper motions were obtained by combining PARSEC observations astrometrically reduced with respect to the Second US Naval Observatory CCD Astrograph Catalog, and the Two Micron All Sky Survey Point Source Catalog. The resulting median proper motion precision is 5 mas yr(-1) for 195,700 sources. The 140 0.3 deg(2) fields sample the southern hemisphere in an unbiased fashion with the exception of the galactic plane due to the small number of targets in that region. The proper motion distributions are shown to be statistically well behaved. External comparisons are also fully consistent. We will continue to update this catalog until the end of the program, and we plan to improve it including also observations from the GSC2.3 database. We present preliminary parallaxes with a 4.2 mas median precision for 10 brown dwarfs, two of which are within 10 pc. These increase the present number of L dwarfs by 20% with published parallaxes. Of the 10 targets, seven have been previously discussed in the literature: two were thought to be binary, but the PARSEC observations show them to be single; one has been confirmed as a binary companion and another has been found to be part of a binary system, both of which will make good benchmark systems. These results confirm that the foreseen precision of PARSEC can be achieved and that the large field of view will allow us to identify wide binary systems. Observations for the PARSEC program will end in early 2011 providing three to four years of coverage for all targets. The main expected outputs are: more than a 100% increase in the number of L dwarfs with parallaxes, increment in the number of objects per spectral subclass up to L9-in conjunction with published results-to at least 10, and to put sensible limits on the general binary fraction of brown dwarfs. We aim to contribute significantly to the understanding of the faint end of the H-R diagram and of the L/T transition region.

Social interaction as a heuristic for combinatorial optimization problems

We investigate the performance of a variant of Axelrod's model for dissemination of culture-the Adaptive Culture Heuristic (ACH)-on solving an NP-Complete optimization problem, namely, the classification of binary input patterns of size F by a Boolean Binary Perceptron. In this heuristic, N agents, characterized by binary strings of length F which represent possible solutions to the optimization problem, are fixed at the sites of a square lattice and interact with their nearest neighbors only. The interactions are such that the agents' strings (or cultures) become more similar to the low-cost strings of their neighbors resulting in the dissemination of these strings across the lattice. Eventually the dynamics freezes into a homogeneous absorbing configuration in which all agents exhibit identical solutions to the optimization problem. We find through extensive simulations that the probability of finding the optimal solution is a function of the reduced variable F/N(1/4) so that the number of agents must increase with the fourth power of the problem size, N proportional to F(4), to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with F(6) which can be interpreted as the overall computational cost of the ACH to find an optimal set of weights for a Boolean binary perceptron, given a fixed probability of success.

Collaborative e-learning and Learning Objects

The Learning Object (OA) is any digital resource that can be reused to support learning with specific functions and objectives. The OA specifications are commonly offered in SCORM model without considering activities in groups. This deficiency was overcome by the solution presented in this paper. This work specified OA for e-learning activities in groups based on SCORM model. This solution allows the creation of dynamic objects which include content and software resources for the collaborative learning processes. That results in a generalization of the OA definition, and in a contribution with e-learning specifications.

Denisiuk-type reflection holography display with sillenite crystals for imaging and interferometry of small objects

A novel setup for imaging and interferometry through reflection holography with Bi12TiPO20(BTO) sillenite photorefractive crystals is proposed. A variation of the lensless Denisiuk arrangement was developed resulting in a compact, robust and simple interferometer. A red He-Ne laser was used as light source and the holographic recording occurred by diffusion with the grating vector parallel to the crystal [0 0 1]-axis. In order to enhance the holographic image quality and reduce noise a polarizing beam splitter (PBS) was positioned at the BTO input and the crystal was tilted around the [0 0 1]-axis. This enabled the orthogonally polarized transmission and diffracted beams to be separated by the PBS, providing the holographic image only. The possibility of performing deformation and strain analysis as well as vibration measurement of small objects was demonstrated. (C) 2007 Elsevier B.V. All rights reserved.

Linking Agentive Objects in Mandarin Chinese

This paper is concerned with the problem of argument-function mismatch observed in the apparent subject-object inversion in Chinese consumption verbs, e.g., chi 'eat' and he 'drink', and accommodation verbs, e.g., zhu 'live' and shui 'sleep'. These verbs seem to allow the linking of [agent-SUBJ theme-OBJ] as well as [agent-OBJ theme-SUBJ], but only when the agent is also the semantic role denoting the measure or extent of the action. The account offered is formulated within LFG's lexical mapping theory. Under the simplest and also the strictest interpretation of the one-to-one argument-function mapping principle (or the theta-criterion), a composite role such as ag-ext receives syntactic assignment via one composing role only. One-to-one linking thus entails the suppression of the other composing role. Apparent subject-object inversion occurs when the more prominent agent role is suppressed and thus allows the less prominent extent role to dictate the linking of the entire ag-ext composite role. This LMT account also potentially facilitates a natural explanation of markedness among the competing syntactic structures.

Encoding combinatorial libraries: A novel application of fluorescent silica colloids

A major challenge associated with using large chemical libraries synthesized on microscopic solid support beads is the rapid discrimination of individual compounds in these libraries. This challenge can be overcome by encoding the beads with 1 mum silica colloidal particles (reporters) that contain specific and identifiable combinations of fluorescent byes. The colored bar code generated on support beads during combinatorial library synthesis can be easily, rapidly, and inexpensively decoded through the use of fluorescence microscopy. All reporters are precoated with polyelectrolytes [poly(acrylic acid), PAA, poly(sodium 4-styrenesulfonate PSSS, polyethylenimine, PEI, and/or poly(diallyldimethylammonium chloride), PDADMAC] with the aim of enhancing surface charge, promoting electrostatic attraction to the bead, and facilitating polymer bridging between the bead and reporter for permanent adhesion. As shown in this article, reporters coated with polyelectrolytes clearly outperform uncoated reporters with regard to quantity of attached reporters per bead (54 +/- 23 in 2500 mum(2) area for PEI/PAA coated and 11 +/- 6 for uncoated reporters) and minimization of cross-contamination (1 red reporter in 2500 mum(2) area of green-labeled bead for PEI/PAA coated and 26 +/- 15 red reporters on green-labeled beads for uncoated reporters after 10 days). Examination of various polyelectrolyte systems shows that the magnitude of the xi -potential of polyelectrolyte-coated reporters (-64 mV for PDADMAC/PSSS and -42 mV for PEI/PAA-coated reporters) has no correlation with the number of reporters that adhere to the solid support beads (21 +/- 16 in 2500 mum(2) area for PDADMAC/PSSS and 54 +/- 23 for PEI/PAA-coated reporters). The contribution of polymer bridging to the adhesion has a far greater influence than electrostatic attraction and is demonstrated by modification of the polyelectrolyte multilayers using gamma irradiation of precoated reporters either in aqueous solution or in polyelectrolyte solution.