Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 65 for “"Extremal graph theory"”.

  1. Extremal Graph Theory: Basic Results

    Η παρούσα διπλωματική εργασία έχει σκοπό να παρουσιάσει μία σφαιρική εικόνα της θεωρίας των ακραίων γραφημάτων, διερευνώντας κοινές τεχνικές και τον τρόπο που εφαρμόζονται σε κάποια από τα πιο διάσημα αποτελέσματα του τομέα. Το πρώτο κεφάλαιο είναι μία εισαγωγή στο θέμα και κάποιοι προαπαιτούμενοι …

    athens Repository record for Extremal Graph Theory: Basic Results (opens in a new tab)

  2. Problems in Extremal Graph Theory

    What is the maximum number of edges in a multigraph on n vertices if every k-set spans at most r edges? We asymptotically determine this maximum for almost all k and r as n tends to infinity, thus giving a generalization of Turan's theorem. We find exact answers in many cases, even when edges of …

    uiuc Repository record for Problems in Extremal Graph Theory (opens in a new tab)

  3. Topics in extremal graph theory

    New results are proved on several problems in extremal graph theory.

    uiuc Repository record for Topics in extremal graph theory (opens in a new tab)

  4. Problems in extremal graph theory

    We consider a variety of problems in extremal graph and set theory. The {\em chromatic number} of $G$, $\chi(G)$, is the smallest integer $k$ such that $G$ is $k$-colorable. The {\it square} of $G$, written $G^2$, is the supergraph of $G$ in which also vertices within distance 2 of each other in …

    uiuc Repository record for Problems in extremal graph theory (opens in a new tab)

  5. Extremal graph theory via structural analysis

    We discuss two extremal problems in extremal graph theory. First we establish a precise characterisation of 4-uniform hypergraphs with minimum codegree close to n/2 which contain a Hamilton 2-cycle. As a corollary we determine the exact Dirac threshold for Hamilton 2-cycles in 4-uniform …

    birmingham Download PDF for Extremal graph theory via structural analysis (opens in a new tab)

  6. Extremal Graph Theory and Enumerative Combinatorics

    This thesis consists of research on two topics.The first topic is about different middle parts of trees, such as center, centroid, subtree core. In this work, we considered how far apart (with given order of the tree) two different `middle points' can be and when such maximum distances are …

    gsu Repository record for Extremal Graph Theory and Enumerative Combinatorics (opens in a new tab)

  7. Extremal graph theory: supersaturation and enumeration

    … supersaturation and enumeration problems in extremal combinatorics. In Chapter 2, with Balogh, we disprove a conjecture of Erdos and Tuza concerning the number of different ways one can create a copy of K_4, a complete graph on 4 vertices, in a K_4-free graph. In Chapter 3, we extend a …

    uiuc Repository record for Extremal graph theory: supersaturation and enumeration (opens in a new tab)

  8. Three Existence Problems in Extremal Graph Theory

    … three different structural questions rooted in extremal graph theory. When studying graph representations, we seek efficient ways to encode the structure of a graph. For example, an {\it interval representation} of a graph $G$ is an assignment of intervals on the real line to the vertices of $G$ …

    uiuc Repository record for Three Existence Problems in Extremal Graph Theory (opens in a new tab)

  9. Topics in extremal graph theory and probabilistic combinatorics

    <p>This thesis considers a variety of problems in Extremal Graph Theory and Probabilistic Combinatorics. Most of these problems are structural in nature, but some concern random reconstruction and parking problems.</p> <p>A <em>matching</em> in a bipartite graph G = (U, V, E) is a subset of the …

    oxford Repository record for Topics in extremal graph theory and probabilistic combinatorics (opens in a new tab)

  10. Turan problems in extremal graph theory and flexibility

    … this work we will study two distinct areas of graph theory: generalized Turan problems and graph flexibility. In the first chapter, we will provide some basic definitions and motivation. Chapters 2 and 3 contain two submitted papers showing that two graphs, the cycle on five vertices and the …

    iastate Repository record for Turan problems in extremal graph theory and flexibility (opens in a new tab)

  11. Problems in extremal graph theory and Euclidean Ramsey theory

    … of three types. The first type is finding extremal numbers for unions of graphs, each with a colour-critical edge (joint work with V. Nikiforov). In 1968, Simonovits found extremal numbers $ex(n,H)$ for graphs with a colour-critical edge for large $n$ (without specifying how large). A …

    manitoba Repository record for Problems in extremal graph theory and Euclidean Ramsey theory (opens in a new tab)

  12. Topics in Stochastic Combinatorial Optimization and Extremal Graph Theory

    We consider a random geometric graph, G(n, r ), constructed by placing points randomly in a square S n of area n according to a Poisson process of intensity 1, and adding an edge joining any pair of points at most distance r=r(n) apart according to the &ell;infinity -metric. We show that w.h.p. …

    uiuc Repository record for Topics in Stochastic Combinatorial Optimization and Extremal Graph Theory (opens in a new tab)

  13. Applications of flag algebras to problems in extremal graph theory

    … several applications of flag algebras in extremal graph theory. We construct flag algebras in two ways, one based in model theory and one based in graph theory. We show that these are equivalent and demonstrate how flag algebras allow for analytic formulations of combinatorial problems via …

    iastate Repository record for Applications of flag algebras to problems in extremal graph theory (opens in a new tab)

  14. Embedding problems and Ramsey-Turán variations in extremal graph theory

    Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2018-08-01

    uiuc Repository record for Embedding problems and Ramsey-Turán variations in extremal graph theory (opens in a new tab)

  15. Extremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors

    … dissertation investigates several questions in extremal graph theory and the theory of graph minors. It consists of three independent parts; the first two parts focus on questions motivated by Turan's Theorem and the third part investigates a problem related to Hadwiger's Conjecture. Let H be a …

    uiuc Repository record for Extremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors (opens in a new tab)

  16. Extremal graph theory: flag algebras, Ramsey-Turan numbers, chromatic thresholds, and sparse hypergraphs

    Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-07-16T19:15:45Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Hu_Ping.pdf: 911457 bytes, checksum: d58f34d1ea93d149457db170269d9561 (MD5)

    uiuc Repository record for Extremal graph theory: flag algebras, Ramsey-Turan numbers, chromatic thresholds, and sparse hypergraphs (opens in a new tab)

  17. Model-theoretic considerations in finite combinatorics

    … that lie primarily in the intersection of model theory and finite combinatorics. The two main areas of combinatorics that make an appearance in the pages to follow are Structural Ramsey Theory and Extremal Graph Theory. Chapter 3 focusses on interactions between model theory and structural Ramsey …

    whiterose Download PDF for Model-theoretic considerations in finite combinatorics (opens in a new tab)

  18. Problems in Domination and Graph Products

    … minimum dominating sets in Cartesian product graphs. Our attention then turns to unique minimum independent dominating sets in trees, and in some direct product graphs. Next, we consider an extremal graph theory problem and determine the maximum number of edges in a graph having a unique …

    clemson Repository record for Problems in Domination and Graph Products (opens in a new tab)

  19. A Hypergraph Regularity Method for Linear Hypergraphs

    Szemerédi's Regularity Lemma is powerful tool in Graph Theory, yielding many applications in areas such as Extremal Graph Theory, Combinatorial Number Theory and Theoretical Computer Science. Strong hypergraph extensions of graph regularity techniques were recently given by Nagle, Rödl, Schacht and …

    usf Repository record for A Hypergraph Regularity Method for Linear Hypergraphs (opens in a new tab)

  20. Probabilistic Methods

    … discrete mathematics, combinatorics and also in graph .theory. It is also very useful to solve problems in number theory, combinatorial geometry, linear algebra and real analysis. More recently, it has been applied in the development of efficient algorithms and in the study of various …

    vcu Repository record for Probabilistic Methods (opens in a new tab)

Page 1 of 4