UNIVERSALITY OF RANDOM GRAPHS

We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(1/d) n edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.

Essays on the Axiomatic Theory of Matching

This dissertation mimics the Turkish college admission procedure. It started with the purpose to reduce the inefficiencies in Turkish market. For this purpose, we propose a mechanism under a new market structure; as we prefer to call, semi-centralization. In chapter 1, we give a brief summary of Matching Theory. We present the first examples in Matching history with the most general papers and mechanisms. In chapter 2, we propose our mechanism. In real life application, that is in Turkish university placements, the mechanism reduces the inefficiencies of the current system. The success of the mechanism depends on the preference profile. It is easy to show that under complete information the mechanism implements the full set of stable matchings for a given profile. In chapter 3, we refine our basic mechanism. The modification on the mechanism has a crucial effect on the results. The new mechanism is, as we call, a middle mechanism. In one of the subdomain, this mechanism coincides with the original basic mechanism. But, in the other partition, it gives the same results with Gale and Shapley's algorithm. In chapter 4, we apply our basic mechanism to well known Roommate Problem. Since the roommate problem is in one-sided game patern, firstly we propose an auxiliary function to convert the game semi centralized two-sided game, because our basic mechanism is designed for this framework. We show that this process is succesful in finding a stable matching in the existence of stability. We also show that our mechanism easily and simply tells us if a profile lacks of stability by using purified orderings. Finally, we show a method to find all the stable matching in the existence of multi stability. The method is simply to run the mechanism for all of the top agents in the social preference.

Entwicklung und Charakterisierung eines Drop-on-Demand-Aerosolgenerators für die Probenzuführung kleinster Flüssigkeitsmengen in der analytischen Atomspektroskopie

Die pneumatische Zerstäubung ist die häufigste Methode der Probenzuführung von Flüssigkeiten in der Plasmaspektrometrie. Trotz der bekannten Limitierungen dieser Systeme, wie die hohen Probenverluste, finden diese Zerstäuber aufgrund ihrer guten Robustheit eine breite Anwendung. Die flussratenabhängige Aerosolcharakteristik und pumpenbasierte Signalschwankungen limitieren bisher Weiterentwicklungen. Diese Probleme werden umso gravierender, je weiter die notwendige Miniaturisierung dieser Systeme fortschreitet. Der neuartige Ansatz dieser Arbeit basiert auf dem Einsatz modifizierter Inkjet-Druckerpatronen für die Dosierung von pL-Tropfen. Ein selbst entwickelter Mikrokontroller ermöglicht den Betrieb von matrixkodierten Patronen des Typs HP45 mit vollem Zugriff auf alle essentiellen Betriebsparameter. Durch die neuartige Aerosoltransportkammer gelang die effiziente Kopplung des Tropfenerzeugungssystems an ein ICP-MS. Das so aufgebaute drop-on-demand-System (DOD) zeigt im Vergleich zu herkömmlichen und miniaturisierten Zerstäubern eine deutlich gesteigerte Empfindlichkeit (8 - 18x, elementabhängig) bei leicht erhöhtem, aber im Grunde vergleichbarem Signalrauschen. Darüber hinaus ist die Flexibilität durch die große Zahl an Freiheitsgraden des Systems überragend. So ist die Flussrate über einen großen Bereich variabel (5 nL - 12,5 µL min-1), ohne dabei die primäre Aerosolcharakteristik zu beeinflussen, welche vom Nutzer durch Wahl der elektrischen Parameter bestimmt wird. Das entwickelte Probenzuführungssystem ist verglichen mit dem pneumatischen Referenzsystem weniger anfällig gegenüber Matrixeffekten beim Einsatz von realen Proben mit hohen Anteilen gelöster Substanzen. So gelingt die richtige Quantifizierung von fünf Metallen im Spurenkonzentrationsbereich (Li, Sr, Mo, Sb und Cs) in nur 12 µL Urin-Referenzmaterial mittels externer Kalibrierung ohne Matrixanpassung. Wohingegen beim pneumatischen Referenzsystem die aufwändigere Standardadditionsmethode sowie über 250 µL Probenvolumen für eine akkurate Bestimmung der Analyten nötig sind. Darüber hinaus wird basierend auf der Dosierfrequenz eines dualen DOD-Systems eine neuartige Kalibrierstrategie vorgestellt. Bei diesem Ansatz werden nur eine Standard- und eine Blindlösung anstelle einer Reihe unterschiedlich konzentrierter Standards benötigt, um eine lineare Kalibrierfunktion zu erzeugen. Zusätzlich wurde mittels selbst entwickelter, zeitlich aufgelöster ICP-MS umfangreiche Rauschspektren aufgenommen. Aus diesen gelang die Ermittlung der Ursache des erhöhten Signalrauschens des DOD, welches maßgeblich durch das zeitlich nicht äquidistante Eintreffen der Tropfen am Detektor verursacht wird. Diese Messtechnik erlaubt auch die Detektion einzeln zugeführter Tropfen, wodurch ein Vergleich der Volumenverteilung der mittels ICP-MS detektierten, gegenüber den generierten und auf optischem Wege charakterisierten Tropfen möglich wurde. Dieses Werkzeug ist für diagnostische Untersuchungen äußerst hilfreich. So konnte aus diesen Studien neben der Aufklärung von Aerosoltransportprozessen die Transporteffizienz des DOD ermittelt werden, welche bis zu 94 Vol.-% beträgt.

Heat transfer in microwave heating

Heat transfer is considered as one of the most critical issues for design and implement of large-scale microwave heating systems, in which improvement of the microwave absorption of materials and suppression of uneven temperature distribution are the two main objectives. The present work focuses on the analysis of heat transfer in microwave heating for achieving highly efficient microwave assisted steelmaking through the investigations on the following aspects: (1) characterization of microwave dissipation using the derived equations, (2) quantification of magnetic loss, (3) determination of microwave absorption properties of materials, (4) modeling of microwave propagation, (5) simulation of heat transfer, and (6) improvement of microwave absorption and heating uniformity. Microwave heating is attributed to the heat generation in materials, which depends on the microwave dissipation. To theoretically characterize microwave heating, simplified equations for determining the transverse electromagnetic mode (TEM) power penetration depth, microwave field attenuation length, and half-power depth of microwaves in materials having both magnetic and dielectric responses were derived. It was followed by developing a simplified equation for quantifying magnetic loss in materials under microwave irradiation to demonstrate the importance of magnetic loss in microwave heating. The permittivity and permeability measurements of various materials, namely, hematite, magnetite concentrate, wüstite, and coal were performed. Microwave loss calculations for these materials were carried out. It is suggested that magnetic loss can play a major role in the heating of magnetic dielectrics. Microwave propagation in various media was predicted using the finite-difference time-domain method. For lossy magnetic dielectrics, the dissipation of microwaves in the medium is ascribed to the decay of both electric and magnetic fields. The heat transfer process in microwave heating of magnetite, which is a typical magnetic dielectric, was simulated by using an explicit finite-difference approach. It is demonstrated that the heat generation due to microwave irradiation dominates the initial temperature rise in the heating and the heat radiation heavily affects the temperature distribution, giving rise to a hot spot in the predicted temperature profile. Microwave heating at 915 MHz exhibits better heating homogeneity than that at 2450 MHz due to larger microwave penetration depth. To minimize/avoid temperature nonuniformity during microwave heating the optimization of object dimension should be considered. The calculated reflection loss over the temperature range of heating is found to be useful for obtaining a rapid optimization of absorber dimension, which increases microwave absorption and achieves relatively uniform heating. To further improve the heating effectiveness, a function for evaluating absorber impedance matching in microwave heating was proposed. It is found that the maximum absorption is associated with perfect impedance matching, which can be achieved by either selecting a reasonable sample dimension or modifying the microwave parameters of the sample.

Multi-Camera very wide baseline feature matching based on view-adaptive junction detection

This paper presents a strategy for solving the feature matching problem in calibrated very wide-baseline camera settings. In this kind of settings, perspective distortion, depth discontinuities and occlusion represent enormous challenges. The proposed strategy addresses them by using geometrical information, specifically by exploiting epipolar-constraints. As a result it provides a sparse number of reliable feature points for which 3D position is accurately recovered. Special features known as junctions are used for robust matching. In particular, a strategy for refinement of junction end-point matching is proposed which enhances usual junction-based approaches. This allows to compute cross-correlation between perfectly aligned plane patches in both images, thus yielding better matching results. Evaluation of experimental results proves the effectiveness of the proposed algorithm in very wide-baseline environments.

Blazed Gratings Recorded in Absorbent Photopolymers

Phase diffractive optical elements, which have many interesting applications, are usually fabricated using a photoresist. In this paper, they were made using a hybrid optic-digital system and a photopolymer as recording medium. We analyzed the characteristics of the input and recording light and then simulated the generation of blazed gratings with different spatial periods in different types of photopolymers using a diffusion model. Finally, we analyzed the output and diffraction efficiencies of the 0 and 1st order so as to compare the simulated values with those measured experimentally. We evaluated the effects of index matching in a standard PVA/AA photopolymer, and in a variation of Biophotopol, a more biocompatible photopolymer. Diffraction efficiencies near 70%, for a wavelength of 633 nm, were achieved for periods longer than 300 µm in this kind of materials.

Quantum-gate characterization in an extended Hilbert space

We describe an approach for characterizing the process performed by a quantum gate using quantum process tomography, by first modeling the gate in an extended Hilbert space, which includes nonqubit degrees of freedom. To prevent unphysical processes from being predicted, present quantum process tomography procedures incorporate mathematical constraints, which make no assumptions as to the actual physical nature of the system being described. By contrast, the procedure presented here assumes a particular class of physical processes, and enforces physicality by fitting the data to this model. This allows quantum process tomography to be performed using a smaller experimental data set, and produces parameters with a direct physical interpretation. The approach is demonstrated by example of mode matching in an all-optical controlled-NOT gate. The techniques described are general and could be applied to other optical circuits or quantum computing architectures.

3D protein structure matching by patch signatures

For determining functionality dependencies between two proteins, both represented as 3D structures, it is an essential condition that they have one or more matching structural regions called patches. As 3D structures for proteins are large, complex and constantly evolving, it is computationally expensive and very time-consuming to identify possible locations and sizes of patches for a given protein against a large protein database. In this paper, we address a vector space based representation for protein structures, where a patch is formed by the vectors within the region. Based on our previews work, a compact representation of the patch named patch signature is applied here. A similarity measure of two patches is then derived based on their signatures. To achieve fast patch matching in large protein databases, a match-and-expand strategy is proposed. Given a query patch, a set of small k-sized matching patches, called candidate patches, is generated in match stage. The candidate patches are further filtered by enlarging k in expand stage. Our extensive experimental results demonstrate encouraging performances with respect to this biologically critical but previously computationally prohibitive problem.

Comparing methods to separate treatment from self-selection effects in an online banking setting

The literature discusses several methods to control for self-selection effects but provides little guidance on which method to use in a setting with a limited number of variables. The authors theoretically compare and empirically assess the performance of different matching methods and instrumental variable and control function methods in this type of setting by investigating the effect of online banking on product usage. Hybrid matching in combination with the Gaussian kernel algorithm outperforms the other methods with respect to predictive validity. The empirical finding of large self-selection effects indicates the importance of controlling for these effects when assessing the effectiveness of marketing activities.

Hausdorff Distances for Searching in Binary Text Images

This work has been partially supported by Grant No. DO 02-275, 16.12.2008, Bulgarian NSF, Ministry of Education and Science.

Essays on Matching Markets and Their Equilibria

Matching theory and matching markets are a core component of modern economic theory and market design. This dissertation presents three original contributions to this area. The first essay constructs a matching mechanism in an incomplete information matching market in which the positive assortative match is the unique efficient and unique stable match. The mechanism asks each agent in the matching market to reveal her privately known type. Through its novel payment rule, truthful revelation forms an ex post Nash equilibrium in this setting. This mechanism works in one-, two- and many-sided matching markets, thus offering the first mechanism to unify these matching markets under a single mechanism design framework. The second essay confronts a problem of matching in an environment in which no efficient and incentive compatible matching mechanism exists due to matching externalities. I develop a two-stage matching game in which a contracting stage facilitates subsequent conditionally efficient and incentive compatible Vickrey auction stage. Infinite repetition of this two-stage matching game enforces the contract in every period. This mechanism produces inequitably distributed social improvement: parties to the contract receive all of the gains and then some. The final essay demonstrates the existence of prices which stably and efficiently partition a single set of agents into firms and workers, and match those two sets to each other. This pricing system extends Kelso and Crawford's general equilibrium results in a labor market matching model and links one- and two-sided matching markets as well.