TY - CHAP A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - New Ramsey Multiplicity Bounds and Search Heuristics T2 - Discrete Mathematics Days N2 - We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we improve the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of K4 and K5 and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic K4 or K5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs. Y1 - 2022 ER - TY - CHAP A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - Fully Computer-assisted Proofs in Extremal Combinatorics T2 - Proceedings of the AAAI Conference on Artificial Intelligence N2 - We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have so far lacked a computational counterpart to derive matching constructive bounds. We demonstrate that common search heuristics are capable of finding constructions far beyond the reach of human intuition. Additionally, the most obvious downside of such heuristics, namely a missing guarantee of global optimality, can often be fully eliminated in this case through lower bounds and stability results coming from the Flag Algebra approach. To illustrate the potential of this approach, we study two related and well-known problems in Extremal Graph Theory that go back to questions of Erdős from the 60s. Most notably, we present the first major improvement in the upper bound of the Ramsey multiplicity of the complete graph on 4 vertices in 25 years, precisely determine the first off-diagonal Ramsey multiplicity number, and settle the minimum number of independent sets of size four in graphs with clique number strictly less than five. Y1 - 2023 U6 - https://doi.org/10.1609/aaai.v37i10.26470 VL - 37 IS - 10 SP - 12482 EP - 12490 ER - TY - JOUR A1 - Gebhard, Oliver A1 - Hahn-Klimroth, Max A1 - Penschuck, Manuel A1 - Rolvien, Maurice A1 - Scarlett, Jonathan A1 - Tan, Nelvin A1 - Parczyk, Olaf T1 - Near optimal sparsity-constrained group testing: improved bounds JF - IEEE Transactions on Information Theory Y1 - 2022 ER - TY - JOUR A1 - Hahn-Klimroth, Max A1 - Person, Yury A1 - Parczyk, Olaf T1 - Minimum degree conditions for containing an r-regular r-connected subgraph JF - European Journal of Combinatorics Y1 - 2024 ER - TY - JOUR A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - New Ramsey multiplicity bounds and search heuristics JF - Foundations of Computational Mathematics Y1 - 2024 ER - TY - JOUR A1 - Böttcher, Julia A1 - Sgueglia, Amedeo A1 - Skokan, Jozef A1 - Parczyk, Olaf T1 - Triangles in randomly perturbed graphs JF - Combinatorics, Probability and Computing Y1 - 2022 ER - TY - JOUR A1 - Gupta, Pranshu A1 - Hamann, Fabian A1 - Müyesser, Alp A1 - Sgueglia, Amedeo A1 - Parczyk, Olaf T1 - A general approach to transversal versions of Dirac-type theorems JF - Bulletin of the London Mathematical Society Y1 - 2023 ER - TY - JOUR A1 - Barros, Gabriel F. A1 - Cavalar, Bruno P. A1 - Mota, Guilherme O. A1 - Parczyk, Olaf T1 - Anti-Ramsey threshold of cycles for sparse graphs JF - Discrete Applied Mathematics Y1 - 2022 ER - TY - JOUR A1 - Kohayakawa, Yoshiharu A1 - Mota, Guilherme O. A1 - Schnitzer, Jakob A1 - Parczyk, Olaf T1 - Anti-Ramsey threshold of complete graphs for sparse graphs JF - Discrete Mathematics Y1 - 2023 ER - TY - JOUR A1 - Allen, Peter A1 - Pfenninger, Vincent A1 - Parczyk, Olaf T1 - Resilience for tight Hamiltonicity JF - Combinatorial Theory Y1 - 2024 U6 - https://doi.org/10.5070/C64163846 VL - 4 IS - 1 ER -