More Like this

1. Equivalent regular partitions of three‐uniform hypergraphs

   https://doi.org/10.1002/rsa.21229  

   Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias (May 2024, Random Structures & Algorithms)

   Abstract Theregularity methodwas pioneered by Szemerédi for graphs and is an important tool in extremal combinatorics. Over the last two decades, several extensions to hypergraphs were developed which were based on seemingly different notions ofquasirandomhypergraphs. We consider the regularity lemmata for three‐uniform hypergraphs of Frankl and Rödl and of Gowers, and present a new proof that the concepts behind these approaches are equivalent. 

   more » « less
2. RAMSEY GROWTH IN SOME NIP STRUCTURES

   https://doi.org/10.1017/S1474748019000100  

   Chernikov, Artem; Starchenko, Sergei; Thomas, Margaret E. (January 2021, Journal of the Institute of Mathematics of Jussieu)

   null (Ed.)

   Abstract We investigate bounds in Ramsey’s theorem for relations definable in NIP structures. Applying model-theoretic methods to finitary combinatorics, we generalize a theorem of Bukh and Matousek ( Duke Mathematical Journal 163 (12) (2014), 2243–2270) from the semialgebraic case to arbitrary polynomially bounded $$o$$ -minimal expansions of $$\mathbb{R}$$ , and show that it does not hold in $$\mathbb{R}_{\exp }$$ . This provides a new combinatorial characterization of polynomial boundedness for $$o$$ -minimal structures. We also prove an analog for relations definable in $$P$$ -minimal structures, in particular for the field of the $$p$$ -adics. Generalizing Conlon et al.  ( Transactions of the American Mathematical Society 366 (9) (2014), 5043–5065), we show that in distal structures the upper bound for $$k$$ -ary definable relations is given by the exponential tower of height $k-1$ . 

   more » « less
3. Conditions for a Bigraph to be Super-Cyclic

   https://doi.org/10.37236/9683  

   Kostochka, Alexandr; Lavrov, Mikhail; Luo, Ruth; Zirlin, Dara (January 2021, The Electronic Journal of Combinatorics)

   A hypergraph $$\mathcal H$$ is super-pancyclic if for each $$A \subseteq V(\mathcal H)$$ with $$|A| \geqslant 3$$, $$\mathcal H$$ contains a Berge cycle with base vertex set $$A$$. We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient. In particular, they are sufficient for every hypergraph $$\mathcal H$$ with $$ \delta(\mathcal H)\geqslant \max\{|V(\mathcal H)|, \frac{|E(\mathcal H)|+10}{4}\}$$. We also consider super-cyclic bipartite graphs: those are $(X,Y)$-bigraphs $$G$$ such that for each $$A \subseteq X$$ with $$|A| \geqslant 3$$, $$G$$ has a cycle $$C_A$$ such that $$V(C_A)\cap X=A$$. Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs. 

   more » « less
4. Indiscernibles in monadically NIP theories

   https://doi.org/10.1112/blms.70155  

   Braunfeld, Samuel; Laskowski, Michael C (July 2025, Bulletin of the London Mathematical Society)

   Abstract We prove various results around indiscernibles in monadically NIP theories. First, we provide several characterizations of monadic NIP in terms of indiscernibles, mirroring previous characterizations in terms of the behavior of finite satisfiability. Second, we study (monadic) distality in hereditary classes and complete theories. Here, via finite combinatorics, we prove a result implying that every planar graph admits a distal expansion. Finally, we prove a result implying that no monadically NIP theory interprets an infinite group, and note an example of a (monadically) stable theory with no distal expansion that does not interpret an infinite group. 

   more » « less
5. Splitting-Off in Hypergraphs

   https://doi.org/10.4230/LIPIcs.ICALP.2024.23  

   Bérczi, Kristóf; Chandrasekaran, Karthekeyan; Király, Tamás; Kulkarni, Shubhang (July 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)

   The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of that vertex while preserving their degrees. Lovász [Lov{á}sz, 1974; Lov{á}sz, 1993] and Mader [Mader, 1978] showed the existence of this operation while preserving global and local connectivities respectively in graphs under certain conditions. These results have far-reaching applications in graph algorithms literature [Lovász, 1976; Mader, 1978; Frank, 1993; Frank and Király, 2002; Király and Lau, 2008; Frank, 1992; Goemans and Bertsimas, 1993; Frank, 1994; Bang-Jensen et al., 1995; Frank, 2011; Nagamochi and Ibaraki, 2008; Nagamochi et al., 1997; Henzinger and Williamson, 1996; Goemans, 2001; Jordán, 2003; Kriesell, 2003; Jain et al., 2003; Chan et al., 2011; Bhalgat et al., 2008; Lau, 2007; Chekuri and Shepherd, 2008; Nägele and Zenklusen, 2020; Blauth and Nägele, 2023]. In this work, we introduce a splitting-off operation in hypergraphs. We show that there exists a local connectivity preserving complete splitting-off in hypergraphs and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs. We illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications: (1) we give a constructive characterization of k-hyperedge-connected hypergraphs and (2) we give an alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau [Király and Lau, 2008]). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams' strong orientation theorem and uses tools developed for hypergraphs. 

   more » « less