Loading Events

« All Events

:

Édouard Bonnet, Twin-width and ordered binary structures

March 24 Wednesday @ 5:00 PM - 6:00 PM KST

Zoom ID: 934 3222 0374 (ibsdimag)

The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G), and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y.  Twin-width is closely tied to total orders on the vertices, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures, or if you prefer, matrices on a finite alphabet. This turns out to be key in understanding combinatorial, algorithmic, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows.

  • Enumerative combinatorics: All the classes of 0,1-matrices with superexponential growth have growth at least n! (in turn resolving a conjecture of Balogh, Bollobás, and Morris on the growth of hereditary classes of ordered graphs).
  • Algorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded.
  • Finite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same.

In addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum, which is still missing for unordered graphs.

Joint work with Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Similar results have been obtained independently by Pierre Simon and Szymon Toruńczyk.

Details

Date:
March 24 Wednesday
Time:
5:00 PM - 6:00 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 934 3222 0374 (ibsdimag)

Organizer

O-joung Kwon (권오정)
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.