Raziskovalni matematični seminar - Arhiv
| 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
This talk will consist of three parts.
In the first part of the talk (joint work with Valerio Boncompagni and Kristina Vušković), we present some recent structural and algorithmic results for several classes of graphs defined by forbidding certain "Truemper configurations" as induced subgraphs. (A _Truemper configuration_ is any theta, pyramid, prism, or wheel.)
In the second part of the talk (joint work with Frédéric Maffray and Kristina Vušković), we present a polynomial-time coloring algorithm for "rings." A ring is a certain generalization of a hyperhole, and it has the property that all holes in it are of the same length. (A _hole_ is an induced cycle of length at least four.) Rings originally appeared as a "basic" class in decomposition theorems for a couple of classes discussed in the first part of the talk.
In the third part of the talk, we discuss the structure of even-hole-free graphs of stability number at most three, and we present a polynomial-time coloring algorithm for these graphs.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs:
Is a given clique strong?
Does the graph have a strong clique?
Is every vertex contained in a strong clique?
Given a partition of the vertex set into cliques, is every clique in the partition strong?
Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs:
Does every induced subgraph have a strong clique?
Is every maximal clique strong?
Is every edge contained in a strong clique?
The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdos-Hajnal property for such graphs.
Join Zoom Meeting:
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Pawel Komosa and Manuel Sorge.
A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H_1 and H_2 in the bramble either V(H_1) intersects V(H_2) or there is an edge of G with one endpoint in V(H_1) and the second endpoint in V(H_2). The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble.
Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph G equals one plus the treewidth of G. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree n-vertex expander a bramble of order Ω(n^{1/2+δ}) requires size exponential in Ω(n^{2δ}) for any fixed δ \in (0,1/2]. On the other hand, the combination of results of Grohe and Marx, and Chekuri and Chuzhoy shows that a graph of treewidth k admits a bramble of order \widetilde{Ω}(k^{1/2}) and size \widetilde{O}(k^{3/2}). (\widetilde{Ω} and \widetilde{O} hide polylogarithmic factors and divisors, respectively.)
We first sharpen the second bound by proving that every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2}) and congestion 2, i.e., every vertex of G is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every δ \in (0,1/2], every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2+δ}) and size 2^{\widetilde{O}(k^{2δ})}.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
If you missed it, you can watch the lecture via the following link:
Passcode: K2@ZVpEY
Transmission of a vertex in a connected graph is the sum of distances from that vertex to all other vertices in the graph. While the use of transmissions as the basis for various topological indices is well known in mathematical chemistry, it is less known that transmissions have been used since 1970s also in space syntax, a particular field of architecture, to denote how easily one can get the sense of a whole building from a locally visible information. Besides these two applications, in this talk we will focus on recent theoretical results on transmissions in graphs, that are mostly related to questions of Klavžar and Dobrynin about graphs in which vertices have distinct transmissions.
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
In recent years, even-hole-free graphs were the object of much attention, however, many questions remain unanswered, such as the existence of a polynomial time algorithm for colouring even-hole-free graphs, or for finding a maximum stable set. The class of even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, K4)- free graphs was constructed, that still has unbounded tree-width [Sintiari and Trotignon, 2019]. The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary.
We show the class of even-hole-free graphs excluding a minor has bounded tree-width (1). This implies that planar even-hole-free graphs have bounded tree-width [da Silva and Linhares Sales, 2010]. To prove this, we provide an "induced grid theorem" for minor-free graphs.
We conjecture that for every d, the class of even-hole-free graphs of degree at most d has bounded tree-width, and we obtain partial results.
- The class of even-hole-free graphs of degree at most 3 has bounded tree-width.
- The class of (even-hole, pyramid)-free graphs of degree at most 4 has bounded tree-width.
In the meantime, our conjecture has been proven [Abrishami, Chudnovsky and Vuskovic, 2020].
Our second source of motivation for studying the tree-width of even-hole-free graphs stems from the area of property testing, namely, from the question whether even-hole-freeness is testable in the bounded degree model. Indeed, since our conjecture holds, this question is now answered.
In this talk I will explain the proof of (1), and give some background on property testing and testability of even-hole-freeness.
This is joint work with Pierre Aboulker, Frederik Harwath, Eunjung Kim, Noleen Köhler, Ni Luh Dewi Sintiari and Nicolas Trotignon.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
The slides of the talk are available HERE.
If you missed it, you can watch the lecture via the following link:
Passcode: kKx7cM?n
Abstract: Combinatorial shifting is a tool used to prove results from extremal set theory such as the Erdős-Ko-Rado theorem. Combinatorial shifting applies a step-by-step procedure to replace a system with a
somewhat simpler (shifted) system.
There are alternate algebraic approaches to shifting. For example, in recent work, I've shown how the Borel Fixed-Point theorem can in certain settings replace (in one step) a system with a shifted system.
In this talk, I'll connect the combinatorial shifting approach with the Borel Fixed-Point approach, by showing how to realize the step-by-step procedure of combinatorial shifting with a limiting
procedure of actions by 1-parameter matrices.
The seminar will be broadcasting via Zoom through the following link:
Join Zoom Meeting
https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09
