|(GMT-3)||November 25th, Thursday|
|14:50||Inauguration Ceremony |
General Chair speech
MDA Steering Committee speech
LAWCG Steering Committee speech
|15:20||Network Science: a primer |
chair: Sulamita Klein
speaker: João Meidanis, UNICAMP, Brazil
|16:10||Best poster award winners|
|16:30||A Survey on Independent Sets in Graphs |
chair: Jayme Szwarcfiter
speakers: Carmen Ortiz, UV, Chile, and Mónica Villanueva, USACH, Chile
Network Science: a primer
João Meidanis, UNICAMP, Brazil
Euler's work on the Bridges of Koenigsberg problem is usually regarded as the birth of Graph Theory. But combinatorialists were not alone studying graph-like structures. In the beginning of the 20th century, sociologists started studying social networks. The idea of "six degrees of separation" (any human on Earth can reach any other by at most six acquaintance links) is from this period. More recently, physicists took to looking at real networks focusing on degree distributions, hubs, communities, preferential growth and other evolution hypotheses, and the like. In this lecture we will review the main points of modern Network Science, exploring scale-free networks, degree correlations, robustness and its relationship to spreading phenomena, e.g., pandemic modeling.
A Survey on Independent Sets in Graphs
Carmen Ortiz, UV, Chile
Mónica Villanueva, USACH, Chile
An independent set of G = (V;E) is a subset S of V such that no two vertices are adjacent. S ⊆ V is a maximal independent set (mis for short) if it is not properly contained in any other independent set of G. The family of mis of G is denoted by M(G) and its cardinality is μ(G). Prodinger and Tichy (1982) introduced the Fibonacci number f(G) of a graph G as the number of independent sets of G, not necessarily maximal, including the empty set. Valiant (1979) showed that the problem of counting the number of mis is #P-complete for a general graph. Füredi (1987) determined a bound for μ(G) when G is a connected graph with at least 50 vertices. Independently, Griggs et al. (1988) established the same bound and characterized the extremal graphs that attain this bound for graphs with six or more vertices. This problem has been studied for various graph classes, including trees (Wilf (1986)), graphs with at most one cycle (Jou and Chang (1997)), graphs with r cycles (Sagan and Vatter (2006) and Goh et al. (2006)), bipartite graphs (Liu (1993)), triangle-free graphs (Hujter and Tuza (1993) and Chang and Jou (1999)) and unicyclic graphs (Koh et al. (2008) and Pedersen and Vestergaard (2005)). Euler (2005) calculated μ(G) when G is a grid graph with up to five rows. The problem of enumerating all maximal independent sets of a graph has also been considered by different authors. For a general connected graphs Tsukiyama et al. (1977) developed the best algorithm. Leung (1984) enumerated all mis of interval graphs, chordal graphs and circular arc graphs. Yu and Chen (1993) solved the problem for permutation graphs. Hota et al. (1999) did the same for trapezoid graphs. The intersection graph I(G) of the family of all maximal independent sets of a graph G is called the Independent Graph of G. Each vertex of I(G) corresponds to a mis of G and two vertices are adjacent in I(G) if their corresponding mis have non-empty intersection in G. Analogously, the Clique Graph K(G) is the intersection graph of all cliques of G. Ortiz and Villanueva (2012) determined μ(G) and generated the family of mis in a caterpillar graph and characterized the independent graph. Ortiz and Villanueva (2017) did the same for grid graphs with two rows. In this work we survey results on these problems related to independent sets: counting independent sets and enumerating maximal independent sets.
- 08/02/2021 Check the Schedule with the uploaded videos!
- 08/02/2021 Second Call for extended abstracts to the special issue of Matemática Contemporânea.
- 06/12/2020 Invitation to submit original contributions for a special issue of Matemática Contemporânea.
- 23/11/2020 Popular voting for the best poster award is closed!
- 16/11/2020 Popular voting for the best poster award is open!
- 16/11/2020 Gallery of Posters available!
- 16/11/2020 Book of Abstracts available!
- 15/10/2020 Registration is open!
- 08/08/2020 Conference Program is available now!
- Easychair opening date: February 23rd, 2021 (00:00 in GMT)
- Easychair closing date: April 11th, 2021 (23:59 in GMT)
- Poster submissions open on August 25th, 2020
- Closing date for poster submissions on October 1st, 2020
- Notification of acceptance until October 15th, 2020
- Registration open on October 15th, 2020
- Proceedings available on November 15th, 2020
- Popular voting for the best poster award: November 15th - 22nd, 2020
- Conference on November 25th, 2020