TY - JOUR A1 - Gishboliner, Lior A1 - Glock, Stefan A1 - Sgueglia, Amedeo T1 - Tight Hamilton cycles with high discrepancy JF - Combinatorics, Probability and Computing (1469-2163) N2 - In this paper, we study discrepancy questions for spanning subgraphs of k-uniform hypergraphs. Our main result is that, for any integers k ≥ 3 and r ≥ 2, any r-colouring of the edges of a k-uniform n-vertex hypergraph G with minimum (k−1)-degree δ(G) ≥ (1/2+o(1))n contains a tight Hamilton cycle with high discrepancy, that is, with at least n/r +� (n) edges of one colour. The minimum degree condition is asymptotically best possible and our theorem also implies a corresponding result for perfect matchings. Our tools combine various structural techniques such as Turán-type problems and hypergraph shadows with probabilistic techniques such as random walks and the nibble method. We also propose several intriguing problems for future research. KW - Discrepancy KW - tight Hamilton cycles KW - random walks KW - nibble method Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19166 SN - 1469-2163 VL - 34 (2025) IS - 4 SP - 565 EP - 584 PB - Cambridge University Press CY - Cambridge ER - TY - JOUR A1 - Chen, Yijia A1 - Müller, Moritz A1 - Yokoyama, Keita T1 - A parameterized halting problem, Δ0 truth and the MRDP theorem JF - The Journal of Symbolic Logic (ISSN 1943-5886) N2 - We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given Δ0-formula ϕ(x); the parameter is the size of ϕ. This parameterization focusses attention on instances where n is large compared to the size of ϕ.We show unconditionally that this problem does not belong to the parameterized analogue of AC0. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that IΔ0 proves the MRDP theorem in a certain weak sense. KW - bounded arithmetical truth KW - parameterized halting KW - descriptive complexity KW - weak arithmetic KW - MRDP theorem Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19308 SN - 1943-5886 VL - 90 (2025) IS - 2 SP - 483 EP - 508 PB - Cambridge University Press CY - Cambridge ER - TY - JOUR A1 - Łatuszyński, Krzysztof A1 - Rudolf, Daniel T1 - Convergence of hybrid slice sampling via spectral gap JF - Advances in Applied Probability N2 - It is known that the simple slice sampler has robust convergence properties; however, the class of problems where it can be implemented is limited. In contrast, we consider hybrid slice samplers which are easily implementable and where another Markov chain approximately samples the uniform distribution on each slice. Under appropriate assumptions on the Markov chain on the slice, we give a lower bound and an upper bound of the spectral gap of the hybrid slice sampler in terms of the spectral gap of the simple slice sampler. An immediate consequence of this is that the spectral gap and geometric ergodicity of the hybrid slice sampler can be concluded from the spectral gap and geometric ergodicity of the simple version, which is very well understood. These results indicate that robustness properties of the simple slice sampler are inherited by (appropriately designed) easily implementable hybrid versions. We apply the developed theory and analyze a number of specific algorithms, such as the stepping-out shrinkage slice sampling, hit-and-run slice sampling on a class of multivariate targets, and an easily implementable combination of both procedures on multidimensional bimodal densities. KW - Slice sampler KW - spectral gap KW - geometric ergodicity Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19264 SN - 1475-6064 VL - 56 (2024) IS - 4 SP - 1440 EP - 1466 PB - Cambridge University Press CY - Cambridge ER - TY - JOUR A1 - Hofstadler, Julian T1 - Optimal convergence rates of MCMC integration for functions with unbounded second moment JF - Journal of Applied Probability N2 - We study the Markov chain Monte Carlo estimator for numerical integration for func- tions that do not need to be square integrable with respect to the invariant distribution. For chains with a spectral gap we show that the absolute mean error for L^p functions, with p ∈ (1, 2), decreases like n^(1/p)−1 , which is known to be the optimal rate. This improves currently known results where an additional parameter δ > 0 appears and the convergence is of order n^((1+δ)/p)−1 . KW - Markov chain KW - Monte Carlo KW - spectral gap KW - absolute mean error Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19310 VL - 62 (2025) IS - 3 SP - 1069 EP - 1075 PB - Cambridge University Press CY - Cambridge ER -