Networks

14th Networks - day

On Tuesday June 21tst, the 14th NETWORKS-day is organized by Jop Briët, Stella Kapodistria and Suman Chakraborty. This will be an on-site event for all members and affiliated members. 

 

Programme

09.30-09.45 Opening
09.45-10.45 Krystal Guo
10.45-11.00 Coffee break
11.00-12.00 Pim van der Hoorn
12.00-13.30 Lunch
13.00-14.00 Introduction of new Networks members (tentative)
14.00-15.00 Dion Gijswijt
15.00-15.15 Coffee break
15.15-16.15 Royi Jacobovic
16.15-?? Social

 

Abstracts

Speaker: Krystal Guo

Title: Transversal polynomial of graphs.

 

Abstract: We explore the interplay between algebraic combinatorics and some algorithmic problems in graph theory. We define a polynomial with connections to correspondence colouring, a recent generalization of list-colouring, and the Unique Games Conjecture. Like the chromatic polynomial of a graph, we are able to evaluate this polynomial at -r+1 modulo r^n, despite the complexity of computing this polynomial. This is based on joint work with Chris Godsil and Gordon Royle.

 

Speaker: Pim van der Hoorn.
Title: Two decades of studying network assortativity. What have we learned?

Abstract: It has been about 20 years since Mark Newman added networks assortativity, the correlation between the degrees of connected nodes, to the list of important network properties. Since then, many researchers have studied these correlations in many real-world systems, development methods to measure them and models for networks with specific correlations profiles. So what have we learned and what challenges still remain?
In this talk I will provide a partial overview of the study of degree-degree correlations in networks. I will discuss what they are, why we care, how to quantify/measure them from data and how to construct networks with given correlation patterns. Here a good part will be spend on measuring network assortativity and interpreting the results. It turns out that when the networks have power-law like degree distributions this is not straightforward. I will introduce several different measures and discuss their strengths and weaknesses. I shall end with some remaining open research questions on this interesting topic.

 

Speaker: Dion Gijswijt

Title: Constructing tree decompositions for graphs of bounded gonality.

 

Abstract: Divisorial gonality is a graph parameter that has its origins in algebraic geometry. It is a combinatorial analogue and lower bound for gonality of algebraic curves. In terms of the classical chip-firing game of Björner-Lovász-Shor it relates to chip configurations that result in a finite game, even after adding a chip at an arbitrary position. In this talk we will show that gonality is an upper bound for the treewidth. Moreover, we give an algorithmic proof that produces a tree-decomposition of width equal to the gonality. We will conclude with some open problems. Joint work with: Hans Bodlaender, Josse van Dobben de Bruyn, and Harry Smit.

 

Speaker: Royi Jacobovic

Title: Externalities in queues as stochastic processes: The case of M/G/1. 

    

Abstract: Externalities are the costs that a user of a common resource imposes on others. For example, consider a FCFS M/G/1 queue and a customer with service demand of x>=0 minutes who arrived into the system when the workload level was u>=0 minutes. Let E_v(x) be the total waiting time which could be saved if this customer gave up on his service demand. In this work, we analyse the externalities process {E_v(x); x>=0}. The analysis includes a decomposition which yields several results: Convexity of E_v(.), an exact expression for the auto-covariance and a Gaussian approximation of E_v(.). Finally, we also consider the extended framework when   is a general nonnegative random variable which is independent from the arrival process and the service demands. This leads to a generalization of an existing result from a previous work of Haviv and Ritov (1998). 

This is based on joint work with Michel Mandjes.

 

 

 

If you have any questions please feel free to contact:

Jop Briet (J.Briet@cwi.nl)

Suman Chakraborty (s.chakraborty1@tue.nl)

Stella Kapodistria (S.Kapodistria@tue.nl)

    

    

    

 

    

    

              

Details
When: Tuesday June 21st, 2022
Time: 09:30 - 17:00
Where: CWI, Science park 123, Amsterdam (Room: L016, L017)
Location

cwi

 

CWI (Room: L016, L017)

Science Park 123
1098 XG Amsterdam
NETHERLANDS

Directions