1,721,087 research outputs found
On the structure of graphs with forbidden induced substructures
Full text linkOne of the central goals in extremal combinatorics is to understand how the global structure of a combinatorial object, e.g. a graph, hypergraph or set system, is affected by local constraints.
In this thesis we are concerned with structural properties of graphs and hypergraphs which locally do not look like some type of forbidden induced pattern. Patterns can be single subgraphs, families of subgraphs, or in the multicolour version colourings or families of colourings of subgraphs.
Erdős and Szekeres\u27s quantitative version of Ramsey\u27s theorem asserts that in every -edge-colouring of the complete graph on vertices there is a monochromatic clique on at least vertices. The famous Erdős-Hajnal conjecture asserts that forbidding fixed colourings on subgraphs ensures much larger monochromatic cliques. The conjecture is open in general, though a few partial results are known. The first part of this thesis will be concerned with different variants of this conjecture: A bipartite variant, a multicolour variant, and an order-size variant for hypergraphs.
In the second part of this thesis we focus more on order-size pairs; an order-size pair is the family consisting of all graphs of order and size , i.e. on vertices with edges. We consider order-size pairs in different settings: The graph setting, the bipartite setting and the hypergraph setting. In all these settings we investigate the existence of absolutely avoidable pairs, i.e. fixed pairs that are avoided by all order-size pairs with sufficiently large order, and also forcing densities of order-size pairs , i.e. for approaching infinity, the limit superior of the fraction of all possible sizes , such that the order-size pair does not avoid the pair
Capturing the Computational Complexity of Geometric Problems by the First-Order Theory of the Reals
Full text linkRamsey numbers for partially ordered sets
Full text linkThe main objective of Ramsey theory is to investigate the largest monochromatic substructure guaranteed in any coloring of a given discrete host structure. Examples for such substructures are subgraphs hosted in a complete graph or arithmetic progressions in the natural numbers. In this thesis, we present quantitative Ramsey-type results in the setting of finite sets that are equipped with a partial order, so-called posets. A prominent example of a poset is the Boolean lattice , which consists of all subsets of , ordered by inclusion. For posets and , the poset Ramsey number is the smallest such that no matter how the elements of are colored in blue and red, there is either an induced subposet isomorphic to in which every element is colored blue, or an induced subposet isomorphic to in which every element is colored red.
The central focus of this thesis is to investigate , where is fixed and grows large. Our results contribute to an active area of discrete mathematics, which studies the existence of large homogeneous substructures in host structures with local constraints, introduced for graphs by Erd\H{o}s and Hajnal. We provide an asymptotically tight bound on for from several classes of posets, and show a dichotomy in the asymptotic behavior of , depending on whether contains a subposet isomorphic to one of two specific posets.
A fundamental question in the study of poset Ramsey numbers is to determine the asymptotic behavior of for large . In this dissertation, we present improvements on the known lower and upper bound on . Moreover, we explore variations of the poset Ramsey setting, including Erd\H{o}s-Hajnal-type questions when the small forbidden poset has a non-monochromatic color pattern, and so-called weak poset Ramsey numbers, which are concerned with non-induced subposets
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Geometrische Repräsentationen von Graphen mit geringer polygonaler Komplexität
No full textDiese Arbeit befasst sich mit der Darstellung eines Graphen als Durchschnittsgraphen in der Ebene. Wir betrachten zwei Varianten einer solchen Darstellung: In der ersten Variante, den side contact representations, werden Knoten durch einfache Polygone repräsentiert, deren Innere disjunkt sind. Jede Kante des Graphen entspricht einer Überschneidung der Ränder der entsprechenden Polygone mit echt positiver Länge, einem sogenannten side contact. In der zweiten Variante, den EPG representations, sind Knoten durch Pfade im ebenen Quadratgitter repräsentiert, und Kanten durch Pfade die mindestens eine Gitterkante gemeinsam haben. In beiden Fällen wird die schlimmstenfalls benötigte polygonale Komplexität der Polygone bzw. Gitterpfade untersucht.In this thesis we investigate graphs that are represented as intersection graphs in the plane. We consider two types of intersection graphs: In a side contact representation vertices are represented by simple polygons whose interiors are pairwise disjoint. Every edge corresponds to a non-trivial overlap of the boundaries of the corresponding polygons, a so-called side contact. Secondly we consider EPG representations in which vertices are represented by paths in the plane square grid and edges correspond to pairs of paths that have at least one grid edge in common. In both cases we investigate the worst-case polygonal complexity of the polygons, respectively paths, in the representation
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
A Note on Polychromatic Colorings of Shift-Chains
Full text linkWe popularize the question whether, for large enough, all -uniform
shift-chain hypergraphs are properly -colorable. On the other hand, we show
that for every some -uniform shift-chains are not polychromatic
-colorable
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
