Thursday, March 2, 2023, 3:30 – 4:30pm

Let G be a graph on n vertices, and assume that its minimum degree is at least k, or its independence number is at most t. What can be said then about various graph-theoretic parameters of G, such as connectivity, large minors and subdivisions, diameter, etc.? Trivial extremal examples (disjoint cliques, unbalanced complete bipartite graphs, random graphs and their disjoint unions) supply rather prosaic bounds for these questions.

We show that the situation is bound to change dramatically if one adds relatively few random edges on top of G
(the so called randomly perturbed graph model, launched in a paper by Bohman, Frieze and Martin from 2003). Here are representative results, in a somewhat approximate form:

• Assuming δ(G)≥k
• , and for s<ck, adding about Cns∗log(n/k) / k random edges to G results with high probability in an s-connected graph;
• Assuming α(G)≤t and adding cn random edges to G typically produces a graph containing a minor of a graph of average degree of order n/ √t

In this talk I will introduce and discuss the model of randomly perturbed graphs, and will present our results.

A joint work with Elad Aigner-Horev and Dan Hefetz.

Event Type: Seminars
Room Number: In Person
Building: Wean Hall 8220
Speaker's Name: MICHAEL KRIVELEVICH
Speaker Website: www.math.tau.ac.il…
Speaker's Professional Title: Baumritter Chair in Combinatorics School of Mathematical Sciences Sackler Faculty of Exact Sciences Tel Aviv University
Talk Title: Improving graph's parameters through random perturbation
For More Information: amzij@cmu.edu
Affiliations: Computer Science Department (CSD)
Organization(s): Department of Mathematical Sciences, Tepper
Event Website Title: Event Website
Event Website URL: aco.math.cmu.edu…