More Like this

1. A Hypergraph Analog of Dirac's Theorem for Long Cycles in 2-Connected Graphs, II: Large Uniformities

   https://doi.org/10.37236/12486  

   Kostochka, Alexandr; Luo, Ruth; McCourt, Grace (January 2025, The Electronic Journal of Combinatorics)

   Dirac proved that each $$n$$-vertex $$2$$-connected graph with minimum degree $$k$$ contains a cycle of length at least $$\min\{2k, n\}$$. We obtain analogous results for Berge cycles in hypergraphs. Recently, the authors proved an exact lower bound on the minimum degree ensuring a Berge cycle of length at least $$\min\{2k, n\}$$ in $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraphs when $$k \geq r+2$$. In this paper we address the case $$k \leq r+1$$ in which the bounds have a different behavior. We prove that each $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraph $$H$$ with minimum degree $$k$$ contains a Berge cycle of length at least $$\min\{2k,n,|E(H)|\}$$. If $$|E(H)|\geq n$$, this bound coincides with the bound of the Dirac's Theorem for 2-connected graphs. 

   more » « less
2. Breaking reflection symmetry: evolving long dynamical cycles in Boolean systems

   https://doi.org/10.1088/1367-2630/ad1bdd  

   Ouellet, Mathieu; Kim, Jason Z.; Guillaume, Harmange; Shaffer, Sydney M.; Bassett, Lee C.; Bassett, Dani S. (February 2024, New Journal of Physics)

   Abstract In interacting dynamical systems, specific local interaction rules for system components give rise to diverse and complex global dynamics. Long dynamical cycles are a key feature of many natural interacting systems, especially in biology. Examples of dynamical cycles range from circadian rhythms regulating sleep to cell cycles regulating reproductive behavior. Despite the crucial role of cycles in nature, the properties of network structure that give rise to cycles still need to be better understood. Here, we use a Boolean interaction network model to study the relationships between network structure and cyclic dynamics. We identify particular structural motifs that support cycles, and other motifs that suppress them. More generally, we show that the presence ofdynamical reflection symmetryin the interaction network enhances cyclic behavior. In simulating an artificial evolutionary process, we find that motifs that break reflection symmetry are discarded. We further show that dynamical reflection symmetries are over-represented in Boolean models of natural biological systems. Altogether, our results demonstrate a link between symmetry and functionality for interacting dynamical systems, and they provide evidence for symmetry’s causal role in evolving dynamical functionality. 

   more » « less
3. Even pairs in Berge graphs with no balanced skew-partitions

   https://doi.org/10.1016/j.disc.2024.114388  

   Abrishami, Tara; Chudnovsky, Maria; Tang, Yaqian (May 2025, Discrete Mathematics)

   Let G be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph G with no balanced skew-partition is either complete or has an even pair. 

   more » « less
4. Smallest Synthetic Witnesses for Conjunctive Queries

   https://doi.org/10.1145/3725250  

   Esmailpour, Aryan; Glavic, Boris; Hu, Xiao; Sintos, Stavros (June 2025, Proceedings of the ACM on Management of Data)

   Given a self-join-free conjunctive queryQand a set of tuplesS, asynthetic witness Dis a database instance such that the result ofQonDisS. In this work, we are interested in two problems. First, the existence problem ESW decides whether any synthetic witnessDexists. Second, given that a synthetic witness exists, the minimization problem SSW computes a synthetic witness of minimal size. The SSW problem is related to thesmallest witness problemrecently studied by Hu and Sintos [22]; however, the objective and the results are inherently different. More specifically, we show that SSW is poly-time solvable for a wider range of queries. Interestingly, in some cases, SSW is related to optimization problems in other domains, such as therole miningproblem in data mining and theedge concentrationproblem in graph drawing. Solutions to ESW and SSW are of practical interest, e.g., fortest database generationfor applications accessing a database and fordata compressionby encoding a datasetSas a pair of a queryQand databaseD. We prove that ESW is in P, presenting a simple algorithm that, given anyS, decides whether a synthetic witness exists in polynomial time in the size ofS. Next, we focus on the SSW problem. We show an algorithm that computes a minimal synthetic witness in polynomial time with respect to the size ofSfor any queryQthat has thehead-dominationproperty. IfQdoes not have such a property, then SSW is generally hard. More specifically, we show that for the class ofpath queries(of any constant length), SSW cannot be solved in polynomial time unless P = NP. We then extend this hardness result to the class ofBerge-acyclicqueries that do not have the head-domination property, obtaining a full dichotomy of SSW for Berge-acyclic queries. Finally, we investigate the hardness of SSW beyond Berge-acyclic queries by showing that SSW cannot be solved in polynomial time for some cyclic queries unless P = NP. 

   more » « less
5. Off‐Diagonal Ramsey Numbers for Slowly Growing Hypergraphs

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

   Mattheus, Sam; Mubayi, Dhruv; Nie, Jiaxi; Verstraëte, Jacques (January 2025, Random Structures & Algorithms)

   ABSTRACT For ak‐uniform hypergraph and a positive integer , the Ramsey number denotes the minimum such that every ‐vertex ‐free ‐uniform hypergraph contains an independent set of vertices. A hypergraph isslowly growingif there is an ordering of its edges such that for each . We prove that if is fixed and is any non‐k‐partite slowly growing ‐uniform hypergraph, then for ,In particular, we deduce that the off‐diagonal Ramsey number is of order , where is the triple system . This is the only 3‐uniform Berge triangle for which the polynomial power of its off‐diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs and hypergraph containers. 

   more » « less