On the edit distance from $K_{2,t}$-free graphs

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

31 pages, 12 figures. This paper is a combination of earlier postings: "On the edit distance from $K_{2,t}$-free graphs I: Cas

Scientific paper

The edit distance between two graphs on the same vertex set is defined to be the size of the symmetric difference of their edge sets. The edit distance function of a hereditary property, $\mathcal{H}$, is a function of $p$, and measures, asymptotically, the furthest graph of edge density $p$ from $\mathcal{H}$ under this metric. In this paper, we address the hereditary property $\forb(K_{2,t})$, the property of having no induced copy of the complete bipartite graph with 2 vertices in one class and $t$ in the other. Employing an assortment of techniques and colored regularity graph constructions, we are able to determine the edit distance function over the entire domain $p\in [0,1]$ when $t=3,4$ and extend the interval over which the edit distance function for $\forb(K_{2,t})$ is known for all values of $t$, determining its maximum value for all odd $t$. We also prove that the function for odd $t$ has a nontrivial interval on which it achieves its maximum. These are the only known principal hereditary properties for which this occurs. In the process of studying this class of functions, we encounter some surprising connections to extremal graph theory problems, such as strongly regular graphs and the problem of Zarankiewicz.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On the edit distance from $K_{2,t}$-free graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the edit distance from $K_{2,t}$-free graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the edit distance from $K_{2,t}$-free graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-515630

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.