The 13th Annual Uri N. Peled Memorial Lecture - Monday May 30, 2022 by Martin Milanič - Shifting paths to avoidable ones

[Prof. Martin Charles Golumbic]

You are cordially invited to attend on zoom

The 13th Annual Uri N. Peled Memorial Lecture

Date: Monday May 30, 2022 (zoom link below)
Time: 13:30 UK; 14:30 France; 15:30 Israel; 18:00 India;
9:30 Rio and Buenos Aires ; 8:30 New York; 7:30 Chicago

Speaker: Martin Milanič (University of Primorska, Koper, Slovenia)
Title: "Shifting paths to avoidable ones"

Abstract:

An *extension* of an induced path P in a graph G is an induced path P’ such
that deleting the endpoints of P’ results in P. An induced path in a graph is
said to be *avoidable* if each of its extensions is contained in an induced
cycle. In 2019, Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius
conjectured that every graph that contains an induced k‐vertex path also
contains an avoidable induced path of the same length, and proved the result
for k = 2. The case k = 1 was known much earlier, due to a work of Ohtsuki,
Cheung, and Fujisawa in 1976. The conjecture was proved for all k in 2020 by
Bonamy, Defrain, Hatzel, and Thiebaut.

Using a similar approach, we strengthen their result from a reconfiguration
point of view. Namely, we show that in every graph, each induced path can be
transformed to an avoidable one by a sequence of shifts, where two induced
k-vertex paths are *shifts* of each other if their union is an induced path
with k + 1 vertices. We also obtain analogous results for not necessarily
induced paths and for walks. In contrast, the statement cannot be extended to
trails or to isometric paths.

This is joint work with Vladimir Gurvich, Matjaž Krnc, and Mikhail Vyalyi.

Note:
Uri Natan Peled ז"ל was a mathematician, friend, open-minded, thoughtful, and
generous person, author of many research papers,
journal guest editor, survey and book writer. He was a perfectionist
with the patience to wait for the right solution to an open problem before
committing to a final written version. Together with colleagues, his work
introduced many topics related to threshold graphs, as well as mathematical
works on Boolean functions, polyhedral combinatorics, and information theory.
He contributed much to the academic atmosphere at his home institution, the
University of Illinois at Chicago, and was a frequent visitor to the Caesarea
Rothschild Institute at the University of Haifa. Prof. Peled died on September
5, 2009 at the age of 65. By this annual lecture series, we honor his memory
and his research work.


Forthcoming Topics in Algorithmic Gaph Theory Seminar Meetings

June 13, 2022 Nathan Wallheimer
"Improved Compression of the Okamura-Seymour Metric"
June 20, 2022 Abhiruk Lahiri
"The Graph Square Root Problem"
June 27, 2022 Rishikesh Gajjala
"Perfect matchings and Quantum Physics"

The seminar meets on Mondays at
Israel: 15:30 EU: 14:30 UK: 13:30 USA East coast: 8:30
Korea: 21:30 India: 18:00 Brazil and Argentina: 9:30


Feel free to pass this announcement on to interested trusted colleagues
and students, but please do not republish the zoom link externally.
The zoom link for this year:
Topics in Algorithmic Graph Theory
Zoom Meeting Link:

https://us06web.zoom.us/j/82694935491?pwd=SW1oYVl2WXJDVTJDUlRISjdjWGcwUT09
Meeting ID: 826 9493 5491
Passcode: 3.14159