UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Some results in extremal combinatorics

Baber, R.; (2011) Some results in extremal combinatorics. Doctoral thesis , UCL (University College London). Green open access

[thumbnail of 1306175.pdf]
Preview
PDF
1306175.pdf

Download (852kB)
[thumbnail of Supplementary files: Density Bounder files] ZIP file (Supplementary files: Density Bounder files)
DensityBounder.zip

Download (63kB)
[thumbnail of Supplementary files: Density Checker files] ZIP file (Supplementary files: Density Checker files)
DensityChecker.zip

Download (411kB)
[thumbnail of Supplementary files: Graph Finder files] ZIP file (Supplementary files: Graph Finder files)
GraphFinder.zip

Download (7kB)
[thumbnail of Supplementary files: Hypercube Edge Density Checker files] ZIP file (Supplementary files: Hypercube Edge Density Checker files)
HypercubeEdgeDensityChecker.zip

Download (29kB)
[thumbnail of Supplementary files: Hypercube Vertex Density Checker files] ZIP file (Supplementary files: Hypercube Vertex Density Checker files)
HypercubeVertexDensityChecker.zip

Download (39kB)

Abstract

In Chapter 1 we determine the minimal density of triangles in a tripartite graph with prescribed edge densities. This extends work of Bondy, Shen, Thomassé and Thomassen characterizing those edge densities guaranteeing the existence of a triangle in a tripartite graph. We also determine those edge densities guaranteeing a copy of a triangle or C5 in a tripartite graph. In Chapter 2 we describe Razborov's flag algebra method and apply this to Erdös' jumping hypergraph problem to find the first non-trivial regions of jumps. We also use Razborov's method to prove five new sharp Turan densities, by looking at six vertex 3-graphs which are edge minimal and not 2-colourable. We extend Razborov's method to hypercubes. This allows us to significantly improve the upper bound given by Thomason and Wagner on the number of edges in a C4-free subgraph of the hypercube. We also show that the vertex Turan density of a 3-cube with a single vertex removed is precisely 3/4. In Chapter 3 we look at problems for intersecting families of sets on graphs. We give a new bound for the size of G-intersecting families on a cycle, disproving a conjecture of Johnson and Talbot. We also extend this result to cross-intersecting families and to powers of cycles. Finally in Chapter 4 we disprove a conjecture of Hurlbert and Kamat that the largest trivial intersecting family of independent r-sets from the vertex set of a tree is centred on a leaf.

Type: Thesis (Doctoral)
Title: Some results in extremal combinatorics
Open access status: An open access version is available from UCL Discovery
Language: English
UCL classification: UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/1306175
Downloads since deposit
616Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item