-
Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle
Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle
In an n-vertex graph, there must be a clique or stable set of size at least
42 events found.
Seminars and Colloquiums
Calendar of Events
S Sun
M Mon
T Tue
W Wed
T Thu
F Fri
S Sat
0 events,
0 events,
0 events,
0 events,
1 event,
-
O-joung Kwon (권오정), Directed tangles and applications
O-joung Kwon (권오정), Directed tangles and applications
The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition …
0 events,
0 events,
0 events,
0 events,
0 events,
0 events,
1 event,
-
Andreas Holmsen, Discrete geometry in convexity spaces
Andreas Holmsen, Discrete geometry in convexity spaces
The notion of convexity spaces provides a purely combinatorial framework for certain problems in discrete geometry. In the last ten years, we have seen some progress on several open problems in the area, and in this talk, I will focus on the recent results relating to Tverberg’s theorem and the Alon-Kleitman (p,q) theorem.
1 event,
-
Rose McCarty, Vertex-minors and flooding immersions
Rose McCarty, Vertex-minors and flooding immersions
An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G is in one of the trails. Flooding immersions are interesting for Eulerian group-labelled graphs; in this context they behave quite differently from regular immersions. Moreover, …
0 events,
0 events,
0 events,
0 events,
0 events,
1 event,
-
Ben Lund, Perfect matchings and derangements on graphs
Ben Lund, Perfect matchings and derangements on graphs
We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions. This …
1 event,
-
Yusuke Kobayashi (小林 佑輔), An FPT Algorithm for Minimum Additive Spanner Problem
Yusuke Kobayashi (小林 佑輔), An FPT Algorithm for Minimum Additive Spanner Problem
For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph, …
0 events,
0 events,
0 events,
0 events,
0 events,
1 event,
-
Tuan Tran, Minimum saturated families of sets
Tuan Tran, Minimum saturated families of sets
A family
1 event,
-
Dong Yeap Kang (강동엽), A proof of the Erdős-Faber-Lovász conjecture
Dong Yeap Kang (강동엽), A proof of the Erdős-Faber-Lovász conjecture
A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on
0 events,
0 events,
0 events,
0 events,
0 events,
0 events,
1 event,
-
Ron Aharoni, Colorful KKM and multiple cakes division
Ron Aharoni, Colorful KKM and multiple cakes division
In the "cake partition" problem n players have each a list of preferred parts for any partition of the interval ("cake") into n sub-intervals. Woodall, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players, in which every player gets …