### Schedule

(GMT-3) | November 25th, Thursday |
---|---|

14:40 | Opening Time |

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 |

17:20 | Closing Ceremony |

### Abstracts

### 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.

### News

- 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.
- 06/12/2020
- 06/12/2020
- 25/11/2020
- 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!

### Important Dates

- 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