Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for +publisher:"Rutgers University" +contributor:("Grigoriadis, Michael"). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Rutgers University

1. Khan, Imdadullah, 1980-. Spanning subgraphs in graphs and hypergraphs.

Degree: PhD, Computer Science, 2011, Rutgers University

This thesis consists of three new fundamental results on the existence of spanning subgraphs in graphs and hypergraphs. Cycle Factors in Graphs: A classical conjecture of El-Zahar states that if H is a graph consisting of r vertex disjoint cycles of length n1, n2, ldots , nr, and G is a graph on n = n1+n2 + ... +nr vertices with minimum degree at least [sigmar/i=1 n1/2 then G contains H as a subgraph. A proof of this conjecture for graphs withn[greater than or less than] n0 was announced by S. Abbasi (1998) using the Regularity Lemma-Blow-up Lemma method. We give a new, ``de-regularized" proof of the conjecture for large graphs that avoids the use of the Regularity Lemma, and thus the resulting n0 is much smaller. Perfect Matching in three-uniform hypergraphs A perfect matching in a three-uniform hypergraph on n=3k vertices is a subset of n/3 disjoint edges. We prove that if H is a three-uniform hypergraph on n=3k vertices such that every vertex belongs to at least {n-1choose 2} - {2n/3choose 2}+1 edges, then H contains a perfect matching. We give a construction to show that our result is best possible. Perfect Matching in four-uniform hypergraphs A perfect matching in a four-uniform hypergraph is a subset of lfloorfrac{n}{4} floor disjoint edges. We prove that if H is a sufficiently large four-uniform hypergraph on n=4k vertices such that every vertex belongs to more than {n-1choose 3} - {3n/4 choose 3} edges, then H contains a perfect matching. Our bound is tight and settles a conjecture of Hán, Person and Schacht (2009).

Advisors/Committee Members: Khan, Imdadullah, 1980- (author), Szemeredi, Endre (chair), Steiger, William (internal member), Grigoriadis, Michael (internal member), Reed, Bruce (outside member).

Subjects/Keywords: Graph theory; Hypergraphs

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Khan, Imdadullah, 1. (2011). Spanning subgraphs in graphs and hypergraphs. (Doctoral Dissertation). Rutgers University. Retrieved from http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299

Chicago Manual of Style (16th Edition):

Khan, Imdadullah, 1980-. “Spanning subgraphs in graphs and hypergraphs.” 2011. Doctoral Dissertation, Rutgers University. Accessed October 31, 2020. http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299.

MLA Handbook (7th Edition):

Khan, Imdadullah, 1980-. “Spanning subgraphs in graphs and hypergraphs.” 2011. Web. 31 Oct 2020.

Vancouver:

Khan, Imdadullah 1. Spanning subgraphs in graphs and hypergraphs. [Internet] [Doctoral dissertation]. Rutgers University; 2011. [cited 2020 Oct 31]. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299.

Council of Science Editors:

Khan, Imdadullah 1. Spanning subgraphs in graphs and hypergraphs. [Doctoral Dissertation]. Rutgers University; 2011. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299


Rutgers University

2. Jamshed, Asif. Embedding spanning subgraphs into large dense graphs.

Degree: PhD, Computer Science, 2010, Rutgers University

In this thesis we are going to present some results on embedding spanning subgraphs into large dense graphs. Spanning Trees Bollob'as conjectured that if G is a graph on n vertices, δ(G) geq (1/2 + epsilon) n for some ε > 0, and T is a bounded degree tree on n vertices, then T is a subgraph of G. The problem was solved in the affirmative by Koml'os, S'ark"ozy and Szemer'edi for large graphs. They then strengthened their result, and showed that the maximum degree of T need not be bounded: there exists a constant c such that T is a subgraph of G if Δ(T) leq cn / log n, δ(G) geq (1/2 + epsilon) n and n is large. Both proofs are based on the Regularity Lemma-Blow-up Lemma Method. Recently, using other methods, it was shown that bounded degree trees embed into graphs with minimum degree n/2 + C log n, where C is a constant depending on the maximum degree of T. Here we show that in general n/2 + O(Delta(T) cdot log n) is sufficient for every Δ(T) leq cn / log n. We also show that this bound is tight for the two extreme values of m i.e. when m = C and when m = cn / log n. Powers of Hamiltonian Cycles In 1962 P'osa conjectured that if δ(G) geq frac{2}{3}n then G contains the square of a Hamiltonian cycle. Later, in 1974, Seymour generalized this conjecture: if δ(G) geq (frac{k-1}{k})n then G contains the (k-1)th power of a Hamiltonian cycle. In 1998 the conjecture was proved by Koml'os, S'ark"ozy and Szemer'edi for large graphs using the Regularity Lemma. We present a ``deregularised" proof of the P'osa-Seymour conjecture which results in a much lower threshold value for n, the size of the graph for which the conjecture is true. We hope that the tools used in this proof will push down the threshold value for n to around 100 at which point we will be able to verify the conjecture for every n.

Advisors/Committee Members: Jamshed, Asif (author), Szemeredi, Endre (chair), Steiger, William (internal member), Grigoriadis, Michael (internal member), Abello, James (outside member).

Subjects/Keywords: Hamiltonian graph theory; Spanning trees (Graph theory); Embeddings (Mathematics)

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Jamshed, A. (2010). Embedding spanning subgraphs into large dense graphs. (Doctoral Dissertation). Rutgers University. Retrieved from http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417

Chicago Manual of Style (16th Edition):

Jamshed, Asif. “Embedding spanning subgraphs into large dense graphs.” 2010. Doctoral Dissertation, Rutgers University. Accessed October 31, 2020. http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417.

MLA Handbook (7th Edition):

Jamshed, Asif. “Embedding spanning subgraphs into large dense graphs.” 2010. Web. 31 Oct 2020.

Vancouver:

Jamshed A. Embedding spanning subgraphs into large dense graphs. [Internet] [Doctoral dissertation]. Rutgers University; 2010. [cited 2020 Oct 31]. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417.

Council of Science Editors:

Jamshed A. Embedding spanning subgraphs into large dense graphs. [Doctoral Dissertation]. Rutgers University; 2010. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417

.