Results 21 to 30 of about 653 (189)
An Algorithmic Hypergraph Regularity Lemma [PDF]
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2015 AbstractSzemeré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 ...
Brendan Nagle +2 more
openaire +2 more sources
On Regular Hypergraphs of High Girth [PDF]
The Electronic Journal of Combinatorics, 2014 We give lower bounds on the maximum possible girth of an $r$-uniform, $d$-regular hypergraph with at most $n$ vertices, using the definition of a hypergraph cycle due to Berge. These differ from the trivial upper bound by an absolute constant factor (viz., by a factor of between $3/2+o(1)$ and $2 +o(1)$).
ELLIS, DC, Linial, N
openaire +3 more sources
Approximate counting of regular hypergraphs [PDF]
Information Processing Letters, 2013 In this paper we asymptotically count d-regular k-uniform hypergraphs on n vertices, provided k is fixed and d=d(n)=o(n1/2). In doing so, we extend to hypergraphs a switching technique of McKay and Wormald.
Andrzej Dudek +3 more
openaire +2 more sources
Hypergraph regularity and random sampling
Random Structures & Algorithms, 2023 AbstractSuppose that a ‐uniform hypergraph satisfies a certain regularity instance (that is, there is a partition of given by the hypergraph regularity lemma into a bounded number of quasirandom subhypergraphs of prescribed densities). We prove that with high probability a large enough uniform random sample of the vertex set of also admits the same ...
Felix Joos +3 more
openaire +3 more sources
A Spectral Bound on Hypergraph Discrepancy [PDF]
, 2020 Let ℋ be a t-regular hypergraph on n vertices and m edges. Let M be the m × n incidence matrix of ℋ and let us denote λ = max_{v ∈ ^⟂} 1/‖v‖ ‖Mv‖. We show that the discrepancy of ℋ is O(√t + λ).
Potukuchi, Aditya
core +1 more source
Weak hypergraph regularity and linear hypergraphs
Journal of Combinatorial Theory, Series B, 2010 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Yoshiharu Kohayakawa +3 more
openaire +2 more sources
Definable Regularity Lemmas for Nip Hypergraphs [PDF]
The Quarterly Journal of Mathematics, 2021 AbstractWe present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results of Alon-Fischer-Newman and Lov\'asz-Szegedy for graphs of bounded VC-dimension.
Chernikov, Artem, Starchenko, Sergei
openaire +5 more sources
Convex Cone Conditions on the Structure of Designs [PDF]
, 2003 Various known and original inequalities concerning the structure of combinatorial designs are established using polyhedral cones generated by incidence matrices. This work begins by giving definitions and elementary facts concerning t-designs.
Dukes, Peter James
core +1 more source
Mapping change in higher-order networks with multilevel and overlapping communities
Applied Network Science, 2023 New network models of complex systems use layers, state nodes, or hyperedges to capture higher-order interactions and dynamics. Simplifying how the higher-order networks change over time or depending on the network model would be easy with alluvial ...
Anton Holmgren +2 more
doaj +1 more source
ON REGULARITY OF HYPERGRAPH SEQUENCES
Demonstratio Mathematica, 1994 The paper generalizes two notions connected with the asymptotic behaviour of a hypergraph: the regularity of the hypergraph and the independence of its edges. It is proved that the corresponding asymptotic regularity is equivalent to the average independence of its edges. Some applications to information systems are described.
Pomykała, J. A., Pomykała, J. M.
openaire +2 more sources