2026-07-23T16:33:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22772 2025-10-02T11:31:35Z ddc:004 open_access

On the VC Dimension of First-Order Logic with Counting and Weight Aggregation van Bergerem, Steffen Schweikardt, Nicole VC dimension VC density stability nowhere dense graphs first-order logic with weight aggregation first-order logic with counting We prove optimal upper bounds on the Vapnik-Chervonenkis density of formulas in the extensions of first-order logic with counting (FOC_1) and with weight aggregation (FOWA_1) on nowhere dense classes of (vertex- and edge-)weighted finite graphs. This lifts a result of Pilipczuk, Siebertz, and Toruńczyk [Michał Pilipczuk et al., 2018] from first-order logic on ordinary finite graphs to substantially more expressive logics on weighted finite graphs. Moreover, this proves that every FOC_1 formula and every FOWA_1 formula has bounded Vapnik-Chervonenkis dimension on nowhere dense classes of weighted finite graphs; thereby, it lifts a result of Adler and Adler [Hans Adler and Isolde Adler, 2014] from first-order logic to FOC_1 and FOWA_1. Generalising another result of Pilipczuk, Siebertz, and Toruńczyk [Michał Pilipczuk et al., 2018], we also provide an explicit upper bound on the ladder index of FOC_1 and FOWA_1 formulas on nowhere dense classes. This shows that nowhere dense classes of weighted finite graphs are FOC_1-stable and FOWA_1-stable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Steffen van Bergerem and Nicole Schweikardt 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.15 urn:nbn:de:0030-drops-227722 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode