Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:( Szemeredi)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

1. Yeager, Elyse Christine. Extremal problems in disjoint cycles and graph saturation.

Degree: PhD, Mathematics, 2015, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/78444

In this thesis, we tackle two main themes: sufficient conditions for the existence of particular subgraphs in a graph, and variations on graph saturation.
Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence of a given subgraph are prized. In Chapter 2, we offer a significant refinement of the Corradi-Hajnal Theorem, which gives sufficient conditions for the existence of a given number of disjoint cycles in a graph. Further, our refined theorem leads to an answer for a question posed by G. Dirac in 1963 regarding the existence of disjoint cycles in graphs with a certain connectivity. This answer comprises Chapter 3.
In Chapter 4 we prove a result about equitable coloring: that is, a proper coloring whose color classes all have the same size. Our equitable-coloring result confirms a partial case of a generalized version of the much-studied Chen-Lih-Wu conjecture on equitable coloring. In addition, the equitable-coloring result is equivalent to a statement about the existence of disjoint cycles, contributing to our refinement of the Corradi-Hajnal Theorem.
In Chapters 5 and 6, we move to the topic of graph saturation, which is related to the Turan problem. One imagines a set of n vertices, to which edges are added one-by-one so that a forbidden subgraph never appears. At some point, no more edges can be added. The Turan problem asks the maximum number of edges in such a graph; the saturation number, on the other hand, asks the minimum number of edges. Two variations of this parameter are studied.
In Chapter 5, we study the saturation of Ramsey-minimal families. Ramsey theory deals with partitioning the edges of graphs so that each partition avoids the particular forbidden subgraph assigned to it. Our motivation for studying these families is that they provide a convincing edge-colored (Ramsey) version of graph saturation. We develop a method, called iterated recoloring, for using results from graph saturation to understand this Ramsey version of saturation. As a proof of concept, we use iterated recoloring to determine the saturation number of the Ramsey-minimal families of matchings and describe the assiociated extremal graphs.
An induced version of graph saturation was suggested by Martin and Smith. In order to offer a parameter that is defined for all forbidden graphs, Martin and Smith consider generalized graphs, called trigraphs. Of particular interest is the case when the induced-saturated trigraphs in question are equivalent to graphs. In Chapter 6, we show that a surprisingly large number of families fall into this case. Further, we define and investigate another parameter that is a version of induced saturation that is closer in spirit to the original version of graph saturation, but that is not defined for all forbidden subgraphs.
*Advisors/Committee Members: Kostochka, Alexandr V. (advisor), Balogh, Jozsef (Committee Chair), Reznick, Bruce A. (committee member), Molla, Theodore (committee member).*

Subjects/Keywords: equitable coloring; cycles; Corradi-Hajnal; Hajnal-Szemeredi; Chen-Lih-Wu; graph saturation; co-criticality; edge-colored saturation

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Yeager, E. C. (2015). Extremal problems in disjoint cycles and graph saturation. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/78444

Chicago Manual of Style (16^{th} Edition):

Yeager, Elyse Christine. “Extremal problems in disjoint cycles and graph saturation.” 2015. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed July 14, 2020. http://hdl.handle.net/2142/78444.

MLA Handbook (7^{th} Edition):

Yeager, Elyse Christine. “Extremal problems in disjoint cycles and graph saturation.” 2015. Web. 14 Jul 2020.

Vancouver:

Yeager EC. Extremal problems in disjoint cycles and graph saturation. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2015. [cited 2020 Jul 14]. Available from: http://hdl.handle.net/2142/78444.

Council of Science Editors:

Yeager EC. Extremal problems in disjoint cycles and graph saturation. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2015. Available from: http://hdl.handle.net/2142/78444

2. Curado, Manuel. Structural Similarity: Applications to Object Recognition and Clustering .

Degree: 2018, University of Alicante

URL: http://hdl.handle.net/10045/98110

In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of m-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape…
*Advisors/Committee Members: Escolano, Francisco (advisor), Sáez Martínez, Juan Manuel (advisor).*

Subjects/Keywords: Graph densification; Cut similarity; Spectral clustering; Dirichlet problems; Random walkers; Commute Times; Graph algorithms; Regular Partition; Szemeredi; Alzheimer's disease; Graphs; Return Random Walk; Net4lap; Directed graphs; Spectral graph theory; Graph entropy; Mutual information; Manifold alignment; m-Best Graph Matching; Binary-Tree Partitions; QAP; Graph sparsification; Shape simplification; Alpha shapes

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Curado, M. (2018). Structural Similarity: Applications to Object Recognition and Clustering . (Thesis). University of Alicante. Retrieved from http://hdl.handle.net/10045/98110

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Curado, Manuel. “Structural Similarity: Applications to Object Recognition and Clustering .” 2018. Thesis, University of Alicante. Accessed July 14, 2020. http://hdl.handle.net/10045/98110.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Curado, Manuel. “Structural Similarity: Applications to Object Recognition and Clustering .” 2018. Web. 14 Jul 2020.

Vancouver:

Curado M. Structural Similarity: Applications to Object Recognition and Clustering . [Internet] [Thesis]. University of Alicante; 2018. [cited 2020 Jul 14]. Available from: http://hdl.handle.net/10045/98110.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Curado M. Structural Similarity: Applications to Object Recognition and Clustering . [Thesis]. University of Alicante; 2018. Available from: http://hdl.handle.net/10045/98110

Not specified: Masters Thesis or Doctoral Dissertation