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
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
