More Like this

1. On the Multigraph Overfull Conjecture

   https://doi.org/10.1002/jgt.23221  

   Plantholt, Michael J; Shan, Songling (June 2025, Journal of Graph Theory)

   ABSTRACT A subgraph of a multigraph is overfull if Analogous to the Overfull Conjecture proposed by Chetwynd and Hilton in 1986, Stiebitz et al. formed the multigraph version of the conjecture as follows: Let be a multigraph with maximum multiplicity and maximum degree . Then has chromatic index if and only if contains no overfull subgraph. In this paper, we prove the following three results toward the Multigraph Overfull Conjecture for sufficiently large and even , where . (1) If is ‐regular with , then has a 1‐factorization. This result also settles a conjecture of the first author and Tipnis from 2001 up to a constant error in the lower bound of . (2) If contains an overfull subgraph and , then , where is the fractional chromatic index of . (3) If the minimum degree of is at least for any and contains no overfull subgraph, then . The proof is based on the decomposition of multigraphs into simple graphs and we prove a slightly weaker version of a conjecture due to the first author and Tipnis from 1991 on decomposing a multigraph into constrained simple graphs. The result is also of independent interest. 

   more » « less
2. Companions and an Essential Motion of a Reaction System

   https://doi.org/10.3233/FI-2020-1953  

   Genova, Daniela; Hoogeboom, Hendrik Jan; Jonoska, Nataša (September 2020, Fundamenta Informaticae)

   ter Beek, Maurice; Koutny, Maciej; Rozenberg, Grzegorz (Ed.)

   For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices. 

   more » « less
3. Explicit Abelian Lifts and Quantum LDPC Codes

   https://doi.org/10.4230/LIPIcs.ITCS.2022.88  

   Jeronimo, Fernando Granha (January 2022, Leibniz international proceedings in informatics)

   Braverman, Mark (Ed.)

   For an abelian group H acting on the set [𝓁], an (H,𝓁)-lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit d-regular expander graphs G obtained from an (H,𝓁)-lift of a (suitable) base n-vertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d-1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion. 

   more » « less
4. Minimum L_∞ Hausdorff distance of point sets under translation: Generalizing Klee's measure problem

   https://doi.org/10.4230/LIPIcs.SoCG.2023.24  

   Chan, Timothy M. (June 2023, Proc. 39th Sympos. Computational Geometry (SoCG))

   Chambers, Erin W.; Gudmundsson, Joachim (Ed.)

   We present a (combinatorial) algorithm with running time close to O(n^d) for computing the minimum directed L_∞ Hausdorff distance between two sets of n points under translations in any constant dimension d. This substantially improves the best previous time bound near O(n^{5d/4}) by Chew, Dor, Efrat, and Kedem from more than twenty years ago. Our solution is obtained by a new generalization of Chan’s algorithm [FOCS'13] for Klee’s measure problem. To complement this algorithmic result, we also prove a nearly matching conditional lower bound close to Ω(n^d) for combinatorial algorithms, under the Combinatorial k-Clique Hypothesis. 

   more » « less
5. On the large charge sector in the critical O(N) model at large N

   https://doi.org/10.1007/JHEP09(2021)184  

   Giombi, Simone; Hyman, Jonah (September 2021, Journal of High Energy Physics)

   A bstract We study operators in the rank- j totally symmetric representation of O ( N ) in the critical O ( N ) model in arbitrary dimension d , in the limit of large N and large charge j with j/N ≡ $$ \hat{j} $$ j ̂ fixed. The scaling dimensions of the operators in this limit may be obtained by a semiclassical saddle point calculation. Using the standard Hubbard-Stratonovich description of the critical O ( N ) model at large N , we solve the relevant saddle point equation and determine the scaling dimensions as a function of d and $$ \hat{j} $$ j ̂ , finding agreement with all existing results in various limits. In 4 < d < 6, we observe that the scaling dimension of the large charge operators becomes complex above a critical value of the ratio j/N , signaling an instability of the theory in that range of d . Finally, we also derive results for the correlation functions involving two “heavy” and one or two “light” operators. In particular, we determine the form of the “heavy-heavy-light” OPE coefficients as a function of the charges and d . 

   more » « less