Results 131 to 140 of about 145,190 (272)
Journal of Combinatorial Designs, Volume 33, Issue 8, Page 300-309, August 2025.ABSTRACT We investigate the lazy burning process for Latin squares by studying their associated hypergraphs. In lazy burning, a set of vertices in a hypergraph is initially burned, and that burning spreads to neighboring vertices over time via a specified propagation rule.
Anthony Bonato +3 more
wiley +1 more source
Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem
Journal of Graph Theory, Volume 109, Issue 4, Page 466-480, August 2025.ABSTRACT Given a hypergraph ℋ, the dual hypergraph of ℋ is the hypergraph of all minimal transversals of ℋ. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs.
Endre Boros +3 more
wiley +1 more source
Packing Paths in Sparse Random Graphs
Random Structures &Algorithms, Volume 67, Issue 1, August 2025.ABSTRACT We consider an algorithmic problem on the Erdős–Rényi random graph G∼G(n,p)$$ G\sim G\left(n,p\right) $$ with p=(1+ε)/n$$ p=\left(1+\varepsilon \right)/n $$ for some fixed constant ε>0$$ \varepsilon >0 $$. At the start of the algorithm, it is not disclosed which pairs of vertices are adjacent or not. In each step of the algorithm, we can query
Vesna Iršič Chenoweth +2 more
wiley +1 more source
Hook young diagrams, combinatorics and representations of Lie superalgebras [PDF]
, 1983 Allan Berele, Amitai Regev
openalex +1 more source
Leaf Stripping on Uniform Attachment Trees
Random Structures &Algorithms, Volume 67, Issue 1, August 2025.ABSTRACT In this note, we analyze the performance of a simple root‐finding algorithm in uniform attachment trees. The leaf‐stripping algorithm recursively removes all leaves of the tree for a carefully chosen number of rounds. We show that, with probability 1−ε$$ 1-\varepsilon $$, the set of remaining vertices contains the root and has a size only ...
Louigi Addario‐Berry +4 more
wiley +1 more source
Tight Anti‐Concentration of Rademacher Sums
Random Structures &Algorithms, Volume 67, Issue 1, August 2025.ABSTRACT We consider lower bounds on anti‐concentration probabilities of the form ℙ(|X|≥x)$$ \mathbb{P}\left(|X|\ge x\right) $$, where X=∑i=1naiεi$$ X={\sum}_{i=1}^n{a}_i{\varepsilon}_i $$ is a Rademacher sum; ai$$ {a}_i $$ are positive constants normalised so ∑i=1nai2=1$$ {\sum}_{i=1}^n{a}_i^2=1 $$, and εi$$ {\varepsilon}_i $$ are independent and ...
Lawrence Hollom, Julien Portier
wiley +1 more source
Reconfiguration of Independent Transversals
Random Structures &Algorithms, Volume 67, Issue 1, August 2025.ABSTRACT Given integers Δ≥2$$ \Delta \ge 2 $$ and t≥2Δ$$ t\ge 2\Delta $$, consider a graph of maximum degree Δ$$ \Delta $$ and a partition of its vertices into blocks of size at least t$$ t $$. By a seminal result of Haxell, there is an independent set of the graph that is transversal to the blocks, a so‐called independent transversal. We show that, if
Pjotr Buys, Ross J. Kang, Kenta Ozeki
wiley +1 more source
Sequentially Constrained Hamilton Cycles in Random Graphs
Random Structures &Algorithms, Volume 67, Issue 1, August 2025.ABSTRACT We discuss the existence of Hamilton cycles in the random graph Gn,p$$ {G}_{n,p} $$ where there are restrictions caused by (i) coloring sequences, (ii) a subset of vertices must occur in a specific order, and (iii) there is a bound on the number of inversions in the associated permutation.
Alan Frieze, Wesley Pegden
wiley +1 more source
Structure of Lower Tails in Sparse Random Graphs
Random Structures &Algorithms, Volume 67, Issue 1, August 2025.ABSTRACT We study the typical structure of a sparse Erdős–Rényi random graph conditioned on the lower tail subgraph count event. We show that in certain regimes, a typical graph sampled from the conditional distribution resembles the entropy minimizer of the mean field approximation in the sense of both subgraph counts and cut norm.
Byron Chin
wiley +1 more source