Seminars and Colloquiums

  1. Events
  2. Seminars and Colloquiums

Events Search and Views Navigation

Event Views Navigation

Today

Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues

Room B232 IBS (기초과학연구원)

An odd $$-factor of a graph is a spanning subgraph H such that for every vertex v∈V(G), 1≤dH(v)≤b, and dH(v) is odd. For positive integers r≥3 and b≤r, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an r-regular graph with even number of …

Continue Reading

Patrice Ossona de Mendez, A model theoretical approach to sparsity

Room B232 IBS (기초과학연구원)

We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.

Dabeen Lee (이다빈), Integrality of set covering polyhedra and clutter minors

Room B232 IBS (기초과학연구원)

Given a finite set of elements V and a family C of subsets of V, the set covering problem is to find a minimum cardinality subset of V intersecting every subset in the family C. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint …

Continue Reading

Mihyun Kang (강미현), The genus of a random graph and the fragile genus property

Room B232 IBS (기초과학연구원)

In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich)

Kevin Hendrey, The minimum connectivity forcing forest minors in large graphs

Room B232 IBS (기초과학연구원)

Given a graph G, we define exc(G) to be the minimum value of t for which there exists a constant N(t,G) such that every t-connected graph with at least N(t,G) vertices contains G as a minor. The value of exc(G) is known to be tied to the vertex cover number τ(G), and in fact $\tau(G)\leq …

Continue Reading

Cory Palmer, A survey of Turán-type subgraph counting problems

Room B232 IBS (기초과학연구원)

Let F and H be graphs. The subgraph counting function ex(n,H,F) is defined as the maximum possible number of subgraphs H in an n-vertex F-free graph. This function is a direct generalization of the Turán function as ex(n,F)=ex(n,K2,F). The systematic study of ex(n,H,F) was initiated by Alon and Shikhelman in 2016 who generalized several classical …

Continue Reading

Casey Tompkins, Extremal problems for Berge hypergraphs

Room B232 IBS (기초과학연구원)

Given a graph G, there are several natural hypergraph families one can define. Among the least restrictive is the family BG of so-called Berge copies of the graph G. In this talk, we discuss Turán problems for families BG in r-uniform hypergraphs for various graphs G. In particular, we are interested in general results in …

Continue Reading

Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

Room B232 IBS (기초과학연구원)

A graph or graph property is ℓ-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting ℓ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each ℓ∈N, there is an integer n=n(ℓ) such that every graph with at least n vertices is ℓ-reconstructible. We show that for …

Continue Reading

Zi-Xia Song (宋梓霞), Ramsey numbers of cycles under Gallai colorings

Room B232 IBS (기초과학연구원)

For a graph H and an integer k≥1, the k-color Ramsey number Rk(H) is the least integer N such that every k-coloring of the edges of the complete graph KN contains a monochromatic copy of H. Let Cm denote the cycle on m≥4 vertices. For odd cycles, Bondy and Erd\H{o}s in 1973 conjectured that …

Continue Reading
DIMAG on YouTube

We use YouTube Live to broadcast seminar talks live if the speaker agrees.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.