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. An algorithmic hypergraph regularity lemma

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

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

   Abstract Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended tok‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs. 

   more » « less
3. 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
4. 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
5. 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