Erik Jan van Leeuwen

Javier Garcia-Bernardo, Eva Jaspers, Weverthon Machado et al.

How much of children's educational attainment remains predictable from the wider social contexts in which they grow up, once parental background is known? Sociological research places households, schools, neighborhoods, and extended kin at the center of intergenerational reproduction, yet whether these contexts add predictive information beyond parental background is rarely tested directly. This matters because the added value of social contexts helps distinguish whether they operate as independent sources of inequality or as channels through which parental advantage is reproduced. Using population-scale administrative data from Statistics Netherlands, we construct a network linking a full cohort of children aged 11-12 to parents, extended kin, classmates, household members, and neighbors, and predict university completion at ages 24-25. We compare logistic regression and gradient boosting, which use individual-level aggregates of these contexts, with graph neural networks (GNNs) operating directly on the network, interpreting differences in out-of-sample performance as prediction gaps. Parental socioeconomic background captures most predictable variation; even GNNs add little once parents are known. Prediction gaps are largest among children without a registered father, especially girls and those with less-educated mothers. Methodologically, we argue that prediction gaps can support sociological theory-building: small gaps show where current theory-based models already explain what can be measured; large gaps identify where targeted mechanism-focused research is warranted.

Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen

The Chromatic Sum problem asks, given a graph $G$ and an integer $k$, whether $G$ admits a colouring $c$ with sum $\sum_{v\in V}c(v) \leq k$. We study the complexity of Chromatic Sum on graph classes defined by some set of forbidden graphs. First, we show that three known frameworks fully classify the complexity of Chromatic Sum on $HH$-minor-free graphs and $HH$-topological-minor-free graphs for any set of graphs $HH$, and on $HH$-subgraph-free graphs for any finite set of graphs $HH$. To show this, we prove a new NP-completeness result for Chromatic Sum on certain subdivisions of planar subcubic graphs. Next, we consider other containment relations. We formalise a novel framework of problems that are NP-complete for planar graphs as well as for graphs of bounded independence number. For every problem in this framework, we obtain an almost complete complexity classification on $H$-induced-minor-free graphs, $H$-induced-topological-minor-free graphs, and $H$-free graphs for every graph $H$. We show that Chromatic Sum belongs to this framework, as do several other problems. We also define a more fine-grained framework for the induced subgraph relation. We apply this to obtain a complete complexity classification for Chromatic Sum on $H$-free graphs, as well as for several other problems. We justify the choice of this framework by proving that Chromatic Sum is NP-complete for graphs of clique-width at most $3$. This result complements a known polynomial-time result for graphs of clique-width at most $2$.