More Like this

1. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke; Thomas, Robin (December 2018, Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less
2. A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs

   https://doi.org/10.4230/LIPICS.ISAAC.2024.54  

   Paul-Pena, Daniel; Seshadhri, C (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mestre, Julián; Wirth, Anthony (Ed.)

   Counting the number of homomorphisms of a pattern graph H in a large input graph G is a fundamental problem in computer science. In many applications in databases, bioinformatics, and network science, we need more than just the total count. We wish to compute, for each vertex v of G, the number of H-homomorphisms that v participates in. This problem is referred to as homomorphism orbit counting, as it relates to the orbits of vertices of H under its automorphisms. Given the need for fast algorithms for this problem, we study when near-linear time algorithms are possible. A natural restriction is to assume that the input graph G has bounded degeneracy, a commonly observed property in modern massive networks. Can we characterize the patterns H for which homomorphism orbit counting can be done in near-linear time? We discover a dichotomy theorem that resolves this problem. For pattern H, let 𝓁 be the length of the longest induced path between any two vertices of the same orbit (under the automorphisms of H). If 𝓁 ≤ 5, then H-homomorphism orbit counting can be done in near-linear time for bounded degeneracy graphs. If 𝓁 > 5, then (assuming fine-grained complexity conjectures) there is no near-linear time algorithm for this problem. We build on existing work on dichotomy theorems for counting the total H-homomorphism count. Surprisingly, there exist (and we characterize) patterns H for which the total homomorphism count can be computed in near-linear time, but the corresponding orbit counting problem cannot be done in near-linear time. 

   more » « less
3. GENERICALLY FREE REPRESENTATIONS II: IRREDUCIBLE REPRESENTATIONS

   https://doi.org/10.1007/s00031-020-09591-3  

   Garibaldi, S.; Guralnick, R. (January 2020, Transformation groups)

   We determine which faithful irreducible representations V of a simple linear algebraic group G are generically free for Lie(G), i.e., which V have an open subset consisting of vectors whose stabilizer in Lie(G) is zero. This relies on bounds on dim V obtained in prior work (part I), which reduce the problem to a finite number of possibilities for G and highest weights for V , but still infinitely many characteristics. The remaining cases are handled individually, some by computer calculation. These results were previously known for fields of characteristic zero, although new phenomena appear in prime characteristic; we provide a shorter proof that gives the result with very mild hypotheses on the characteristic. (The few characteristics not treated here are settled in part III.) These results are related to questions about invariants and the existence of a stabilizer in general position. 

   more » « less
4. Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids

   https://doi.org/10.15607/RSS.2018.XIV.013  

   Yu, Jingjin (June 2018, 2018 Robotics: Science and Systems)

   Let G = (V, E) be an m_1 \times \ldots \times m_k grid for some arbitrary constant k. We establish that O(\sum_{i=1}^km_i) (makespan) time-optimal labeled (i.e., each robot has a specific goal) multi-robot path planning can be realized on G in O(|V|^2) running time, even when vertices of G are fully occupied by robots. When all dimensions are of equal sizes, the running time approaches O(|V|). Using this base line algorithm, which provides average case O(1)-approximate (i.e., constant-factor) time-optimal solutions, we further develop a first worst case O(1)-approximate algorithm that again runs in O(|V|^2) time for two and three dimensions. We note that the problem has a worst case running time lower bound of \Omega(|V|^2). 

   more » « less
5. Universal Tensor Categories Generated by Dual Pairs

   https://doi.org/10.1007/s10485-021-09640-2  

   Chirvasitu, Alexandru; Penkov, Ivan (October 2021, Applied Categorical Structures)

   Abstract Let $$V_*\otimes V\rightarrow {\mathbb {C}}$$ V ∗ ⊗ V → C be a non-degenerate pairing of countable-dimensional complex vector spaces V and $$V_*$$ V ∗ . The Mackey Lie algebra $${\mathfrak {g}}=\mathfrak {gl}^M(V,V_*)$$ g = gl M ( V , V ∗ ) corresponding to this pairing consists of all endomorphisms $$\varphi $$ φ of V for which the space $$V_*$$ V ∗ is stable under the dual endomorphism $$\varphi ^*: V^*\rightarrow V^*$$ φ ∗ : V ∗ → V ∗ . We study the tensor Grothendieck category $${\mathbb {T}}$$ T generated by the $${\mathfrak {g}}$$ g -modules V , $$V_*$$ V ∗ and their algebraic duals $$V^*$$ V ∗ and $$V^*_*$$ V ∗ ∗ . The category $${{\mathbb {T}}}$$ T is an analogue of categories considered in prior literature, the main difference being that the trivial module $${\mathbb {C}}$$ C is no longer injective in $${\mathbb {T}}$$ T . We describe the injective hull I of $${\mathbb {C}}$$ C in $${\mathbb {T}}$$ T , and show that the category $${\mathbb {T}}$$ T is Koszul. In addition, we prove that I is endowed with a natural structure of commutative algebra. We then define another category $$_I{\mathbb {T}}$$ I T of objects in $${\mathbb {T}}$$ T which are free as I -modules. Our main result is that the category $${}_I{\mathbb {T}}$$ I T is also Koszul, and moreover that $${}_I{\mathbb {T}}$$ I T is universal among abelian $${\mathbb {C}}$$ C -linear tensor categories generated by two objects X , Y with fixed subobjects $$X'\hookrightarrow X$$ X ′ ↪ X , $$Y'\hookrightarrow Y$$ Y ′ ↪ Y and a pairing $$X\otimes Y\rightarrow {\mathbf{1 }}$$ X ⊗ Y → 1 where 1 is the monoidal unit. We conclude the paper by discussing the orthogonal and symplectic analogues of the categories $${\mathbb {T}}$$ T and $${}_I{\mathbb {T}}$$ I T . 

   more » « less