Please use this identifier to cite or link to this item:

`http://arks.princeton.edu/ark:/88435/dsp01h415pd397`

Title: | The girth of digraphs and concatenating bipartite graphs |

Authors: | Hompe, Patrick |

Advisors: | Seymour, Paul D |

Department: | Mathematics |

Class Year: | 2019 |

Abstract: | We first disprove an old conjecture of Seymour which was a generalization of the famous Caccetta-Haggkvist conjecture, and then characterize when a bipartite digraph must contain a 2-cycle. Afterwards, we consider two functions Φ and Ψ, defi ned as follows. Let x,y ∈ (0; 1] and let A,B,C be disjoint nonempty subsets of a graph G, where every vertex in A has at least x|B| neighbors in B, and every vertex in B has at least y|C| neighbors in C. We denote by Φ(x,y) the maximum z such that, in all such graphs G, there is a vertex v ∈ C that is joined to at least z|A| vertices in A by two-edge paths. If in addition we require that every vertex in B has at least x|A| neighbors in A, and every vertex in C has at least y|B| neighbors in C, we denote by Ψ(x, y) the maximum z such that, in all such graphs G, there is a vertex v ∈ C that is joined to at least z|A| vertices in A by two-edge paths. In their recent paper [1], M. Chudnovsky, P. Hompe, A. Scott, P. Seymour, and S. Spirkl introduced these functions, proved some general results about them, and analyzed when they are greater than or equal to 1/2, 2/3, and 1/3. Here, we extend their results by analyzing when they are greater than or equal to 3/4, 2/5, and 3/5. |

URI: | http://arks.princeton.edu/ark:/88435/dsp01h415pd397 |

Type of Material: | Princeton University Senior Theses |

Language: | en |

Appears in Collections: | Mathematics, 1934-2020 |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

HOMPE-PATRICK-THESIS.pdf | 335.39 kB | Adobe PDF | Request a copy |

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.