Combinatorics
See recent articles
Showing new listings for Friday, 4 October 2024
- [1] arXiv:2410.02105 [pdf, html, other]
-
Title: Equivariant cohomology and orbit harmonicsComments: 29 pagesSubjects: Combinatorics (math.CO); Algebraic Geometry (math.AG)
Given integers $n \geq k \geq d$, let $X_{n,k,d}$ be the moduli space of $n$-tuples of lines $(\ell_1, \dots, \ell_n)$ in $\mathbb{C}^k$ such that $\ell_1 + \cdots + \ell_n$ has dimension $d$. We give a quotient presentation of the torus-equivariant cohomology of $X_{n,k,d}$. The form of this presentation, and in particular the torus parameters appearing therein, will arise from the orbit harmonics method of combinatorial representation theory.
- [2] arXiv:2410.02109 [pdf, other]
-
Title: Decompositions of the wreath product of certain directed graphs into directed hamiltonian cyclesComments: 25 Pages, 4 figuresSubjects: Combinatorics (math.CO)
We affirm several special cases of a conjecture that first appears in Alspach et al.~(1987) which stipulates that the wreath (lexicographic) product of two hamiltonian decomposable directed graphs is also hamiltonian decomposable. Specifically, we show that the wreath product of hamiltonian decomposable directed graph $G$, such that $|V(G)|$ is even and $|V(G)|\geqslant 3$, with a directed $m$-cycle such that $m \geqslant 4$ or the complete symmetric directed graph on $m$ vertices such that $m\geqslant 3$, is hamiltonian decomposable. We also show the wreath product of a directed $n$-cycle, where $n$ is even, with a directed $m$-cycle, where $m \in \{2,3\}$, is not hamiltonian decomposable.
- [3] arXiv:2410.02124 [pdf, html, other]
-
Title: An optimal construction for complete graph embeddings with duals of low connectivityComments: 10 pages, 3 figuresSubjects: Combinatorics (math.CO)
We describe a construction for embeddings of complete graphs where the dual has a cutvertex and the genus is close to the minimum genus of the primal graph. When the number of vertices is congruent to 5 modulo 12, we further guarantee that the dual is simple and that the genera of the resulting embeddings match a lower bound of Brinkmann, Noguchi, and Van den Camp, showing that their lower bound is tight infinitely often.
- [4] arXiv:2410.02336 [pdf, html, other]
-
Title: On strong odd colorings of graphsComments: 26 pagesSubjects: Combinatorics (math.CO)
A strong odd coloring of a simple graph $G$ is a proper coloring of the vertices of $G$ such that for every vertex $v$ and every color $c$, either $c$ is used an odd number of times in the open neighborhood $N_G(v)$ or no neighbor of $v$ is colored by $c$. The smallest integer $k$ for which $G$ admits a strong odd coloring with $k$ colors is the strong odd chromatic number, $\chi_{soc}(G)$. These coloring notion and graph parameter were recently defined in [H. Kwon and B. Park, Strong odd coloring of sparse graphs, arXiv:2401.11653v2]. We answer a question raised by the originators concerning the existence of a constant bound for the strong odd chromatic number of all planar graphs. We also consider strong odd colorings of trees, unicyclic graphs and graph products.
- [5] arXiv:2410.02409 [pdf, html, other]
-
Title: Additive word complexity and WalnutComments: 21 pages, 6 figures; this is the authors' version (with appendices) of the same-titled article published in the proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
In combinatorics on words, a classical topic of study is the number of specific patterns appearing in infinite sequences. For instance, many works have been dedicated to studying the so-called factor complexity of infinite sequences, which gives the number of different factors (contiguous subblocks of their symbols), as well as abelian complexity, which counts factors up to a permutation of letters. In this paper, we consider the relatively unexplored concept of additive complexity, which counts the number of factors up to additive equivalence. We say that two words are additively equivalent if they have the same length and the total weight of their letters is equal. Our contribution is to expand the general knowledge of additive complexity from a theoretical point of view and consider various famous examples. We show a particular case of an analog of the long-standing conjecture on the regularity of the abelian complexity of an automatic sequence. In particular, we use the formalism of logic, and the software Walnut, to decide related properties of automatic sequences. We compare the behaviors of additive and abelian complexities, and we also consider the notion of abelian and additive powers. Along the way, we present some open questions and conjectures for future work.
- [6] arXiv:2410.02437 [pdf, html, other]
-
Title: Chromatic number and regular subgraphsSubjects: Combinatorics (math.CO)
In 1992, Erdős and Hajnal posed the following natural problem: Does there exist, for every $r\in \mathbb{N}$, an integer $F(r)$ such that every graph with chromatic number at least $F(r)$ contains $r$ edge-disjoint cycles on the same vertex set? We solve this problem in a strong form, by showing that there exist $n$-vertex graphs with fractional chromatic number $\Omega\left(\frac{\log \log n}{\log \log \log n}\right)$ that do not even contain a $4$-regular subgraph. This implies that no such number $F(r)$ exists for $r\ge 2$. We show that assuming a conjecture of Harris, the bound on the fractional chromatic number in our result cannot be improved.
- [7] arXiv:2410.02460 [pdf, html, other]
-
Title: Wiring switches to more light bulbsComments: 22 pages, 6 figuresSubjects: Combinatorics (math.CO)
Given $n$ buttons and $n$ bulbs so that the $i$th button toggles the $i$th bulb and perhaps some other bulbs, we compute the sharp lower bound on the number of bulbs that can be lit regardless of the action of the buttons. In the previous article we dealt with the case where each button affects at most 2 or 3 bulbs. In the present article we give sharp lower bounds for up to 4 or 5 wires per switch, and we show that the sharp asymptotic bound for an arbitrary number of wires is $\frac12$. (Even if you've found their buttons, you can please no more than half the people all the time!)
- [8] arXiv:2410.02494 [pdf, html, other]
-
Title: Polyhedral volume ratios, Izmestiev's Colin de Verdiere matrices and Spectral GapsSubjects: Combinatorics (math.CO)
We present a relation between volumes of certain lower dimensional simplices associated to a full-dimensional primal and polar dual polytope in R^k. We then discuss an application of this relation to a geometric construction of a Colin de Verdiere matrix by Ivan Izmestiev. In the second part of the paper, we introduce a variation of vertex transitive polytopes, translate their associated Colin de Verdiere matrices into random walk matrices, and investigate extremality properties of the spectral gaps of these random walk matrices in two concrete examples - permutahedra of Coxeter groups and polytopes associated to the pure rotational tetrahedral group - where maximal spectral gaps correspond to equilateral polytopes.
- [9] arXiv:2410.02545 [pdf, html, other]
-
Title: The bunkbed conjecture is falseComments: 12 pages, 2 figuresSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Probability (math.PR)
We give an explicit counterexample to the Bunkbed Conjecture introduced by Kasteleyn in 1985. The counterexample is given by a planar graph on $7222$ vertices, and is built on the recent work of Hollom (2024).
- [10] arXiv:2410.02593 [pdf, html, other]
-
Title: Multidimensional central sets theorem near zeroSubjects: Combinatorics (math.CO)
In [B] Beiglböck gave a Multidimension Central sets theorem. Recently, [GP] extended this result for polynomials. They proved the Multidimensional Polynomial Central sets theorem. Earlier, Hindman and Leader introduced the near zero concept and proved the Central sets theorem near 0 in [HL]. In this article, we generalize the Multidimensional Central sets theorem for near 0.
- [11] arXiv:2410.02624 [pdf, html, other]
-
Title: Normal trees of digraphComments: 14 pagesSubjects: Combinatorics (math.CO)
In this paper we investigate normal trees of directed graphs, which extend the fundamental concept of normal trees of undirected graphs and form a special case of normal trees of connectoids.
We show that a directed graph $D$ has a normal spanning tree if and only if the topological space $|D|$ is metrizable. This generalises Diestel's result for undirected graphs.
We further show that the existence of normal arborescences implies the existence of normal trees in directed graphs and the converse does not hold true in general. Furthermore, we discuss properties of normal trees that carry over from connectoids to directed graphs. - [12] arXiv:2410.02695 [pdf, other]
-
Title: Fractional list packing for layered graphsComments: 20 pagesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
The fractional list packing number $\chi_{\ell}^{\bullet}(G)$ of a graph $G$ is a graph invariant that has recently arisen from the study of disjoint list-colourings. It measures how large the lists of a list-assignment $L:V(G)\rightarrow 2^{\mathbb{N}}$ need to be to ensure the existence of a `perfectly balanced' probability distribution on proper $L$-colourings, i.e., such that at every vertex $v$, every colour appears with equal probability $1/|L(v)|$. In this work we give various bounds on $\chi_{\ell}^{\bullet}(G)$, which admit strengthenings for correspondence and local-degree versions. As a corollary, we improve theorems on the related notion of flexible list colouring. In particular we study Cartesian products and $d$-degenerate graphs, and we prove that $\chi_{\ell}^{\bullet}(G)$ is bounded from above by the pathwidth of $G$ plus one. The correspondence analogue of the latter is false for treewidth instead of pathwidth.
- [13] arXiv:2410.02738 [pdf, html, other]
-
Title: Identities involving partitions with distinct even parts and $4$-regular partitionsComments: 7 pages, Accepted for publicationSubjects: Combinatorics (math.CO); Number Theory (math.NT)
It is well known that the number of partitions into distinct even parts equals the number of $4$-regular partitions. In this paper we prove identities relating certain restricted partitions into distinct even parts with restricted $4$-regular partitions.
New submissions (showing 13 of 13 entries)
- [14] arXiv:2410.01863 (cross-list from math.PR) [pdf, html, other]
-
Title: Convergence of distributions on pathsComments: 24 pages, proofs at the endJournal-ref: In: Fernau, H., Jansen, K. (eds) Fundamentals of Computation Theory. FCT 2023. Lecture Notes in Computer Science, vol 14292. SpringerSubjects: Probability (math.PR); Combinatorics (math.CO)
We study the convergence of distributions on finite paths of weighted digraphs, namely the family of Boltzmann distributions and the sequence of uniform distributions. Targeting applications to the convergence of distributions on paths, we revisit some known results from reducible nonnegative matrix theory and obtain new ones, with a systematic use of tools from analytic combinatorics. In several fields of mathematics, computer science and system theory, including concurreny theory, one frequently faces non strongly connected weighted digraphs encoding the elements of combinatorial structures of interest; this motivates our study.
- [15] arXiv:2410.01961 (cross-list from cs.CC) [pdf, other]
-
Title: Characterizing and Testing Principal Minor Equivalence of MatricesSubjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
Two matrices are said to be principal minor equivalent if they have equal corresponding principal minors of all orders. We give a characterization of principal minor equivalence and a deterministic polynomial time algorithm to check if two given matrices are principal minor equivalent. Earlier such results were known for certain special cases like symmetric matrices, skew-symmetric matrices with {0, 1, -1}-entries, and matrices with no cuts (i.e., for any non-trivial partition of the indices, the top right block or the bottom left block must have rank more than 1).
As an immediate application, we get an algorithm to check if the determinantal point processes corresponding to two given kernel matrices (not necessarily symmetric) are the same. As another application, we give a deterministic polynomial-time test to check equality of two multivariate polynomials, each computed by a symbolic determinant with a rank 1 constraint on coefficient matrices. - [16] arXiv:2410.02114 (cross-list from math.NT) [pdf, html, other]
-
Title: Iterated Radical Expansions and ConvergenceComments: 11 pagesSubjects: Number Theory (math.NT); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
We treat three recurrences involving square roots, the first of which arises from an infinite simple radical expansion for the Golden mean, whose precise convergence rate was made famous by Richard Bruce Paris in 1987. A never-before-seen proof of an important formula is given. The other recurrences are non-exponential yet equally interesting. Asymptotic series developed for each of these two examples feature a constant, dependent on the initial condition but otherwise intrinsic to the function at hand.
- [17] arXiv:2410.02135 (cross-list from math.AG) [pdf, html, other]
-
Title: Fine multidegrees of matrix Schubert varietiesSubjects: Algebraic Geometry (math.AG); Commutative Algebra (math.AC); Combinatorics (math.CO)
We introduce fine Schubert polynomials, which record the multidegrees of the closures of matrix Schubert varieties in $(\mathbb{P}^1)^{n^2}$. We compute the fine Schubert polynomials of permutations $w$ where the coefficients of the Schubert polynomials of $w$ and $w^{-1}$ are all either 0 or 1. We give a criterion for a collection of polynomials to be a universal Gröbner basis for an ideal in terms of the multidegree of the closure of the corresponding affine variety in $(\mathbb{P}^1)^n$. This criterion gives simple proofs of several existing results on universal Gröbner bases. We use this criterion to give a universal Gröbner basis for the ideal of a matrix Schubert variety of a permutation $w$ where the coefficients of the Schubert polynomial of $w$ and $w^{-1}$ are all either 0 or 1.
- [18] arXiv:2410.02569 (cross-list from math.GR) [pdf, html, other]
-
Title: Kronecker classes, normal coverings and chief factors of groupsComments: 6 pagesSubjects: Group Theory (math.GR); Combinatorics (math.CO)
For a group $G$, a subgroup $U \leq G$ and a group $\mathrm{Inn}(G) \leq A \leq \mathrm{Aut}(G)$, we say that $U$ is an $A$-covering group of $G$ if $G = \bigcup_{a\in A}U^a$. A theorem of Jordan (1872) implies that if $G$ is a finite group, $A = \mathrm{Inn}(G)$ and $U$ is an $A$-covering group of $G$, then $U = G$. Motivated by a question concerning Kronecker classes of field extensions, Neumann and Praeger (1988) conjectured that, more generally, there is an integer function $f$ such that if $G$ is a finite group and $U$ is an $A$-covering subgroup of $G$, then $|G:U| \leq f(|A:\mathrm{Inn}(G)|)$. A key piece of evidence for this conjecture is a theorem of Praeger (1994), which asserts that there is a two-variable integer function $g$ such that if $G$ is a finite group and $U$ is an $A$-covering subgroup of $G$, then $|G:U|\leq g(|A:\mathrm{Inn}(G)|,c)$ where $c$ is the number of $A$-chief factors of~$G$. Unfortunately, the proof of this result contains an error. In this paper, using a different argument, we give a correct proof of this theorem.
Cross submissions (showing 5 of 5 entries)
- [19] arXiv:2305.15207 (replaced) [pdf, html, other]
-
Title: Symmetry in complex unit gain graphs and their spectraSubjects: Combinatorics (math.CO)
Complex unit gain graphs may exhibit various kinds of symmetry. In this work, we explore structural symmetry, spectral symmetry and sign-symmetry in such graphs, and their respective relations to one-another. Our main result is a construction that transforms an arbitrary complex unit gain graph into infinitely many switching-distinct ones whose spectral symmetry does not imply sign-symmetry. This provides a more general answer to the analogue of an existence question that was recently treated in the context of signed graphs.
- [20] arXiv:2403.17110 (replaced) [pdf, html, other]
-
Title: Fixed points and cycles of parking functionsComments: 7 pagesSubjects: Combinatorics (math.CO)
A parking function of length $n$ is a sequence $\pi=(\pi_1,\dots, \pi_n)$ of positive integers such that if $\lambda_1\leq\cdots\leq \lambda_n$ is the increasing rearrangement of $\pi_1,\dots,\pi_n$, then $\lambda_i\leq i$ for $1\leq i\leq n$. The index $i$ is a fixed point of the parking function $\pi$ if $\pi_i=i$. More generally, for $m\geq 1$, the indices $(i_1, \dots, i_m)$ where the $i_j$'s are all distinct constitute an $m$-cycle of the parking function $\pi$ if $\pi_{i_1}=i_2, \pi_{i_2}=i_3, \dots, \pi_{i_{m-1}}=i_m, \pi_{i_m}=i_1$. In this paper we obtain some exact results on the number of fixed points and cycles of parking functions. Our derivations will be based on generalizations of Pollak's argument and the symmetry of parking coordinates. Extensions of our techniques are discussed.
- [21] arXiv:2404.01504 (replaced) [pdf, html, other]
-
Title: On the orthogonal Gr\"unbaum partition problem in dimension threeSubjects: Combinatorics (math.CO); Computational Geometry (cs.CG)
Grünbaum's equipartition problem asked if for any measure $\mu$ on $\mathbb{R}^d$ there are always $d$ hyperplanes which divide $\mathbb{R}^d$ into $2^d$ $\mu$-equal parts. This problem is known to have a positive answer for $d\le 3$ and a negative one for $d\ge 5$. A variant of this question is to require the hyperplanes to be mutually orthogonal. This variant is known to have a positive answer for $d\le 2$ and there is reason to expect it to have a negative answer for $d\ge 3$. In this note we exhibit measures that prove this. Additionally, we describe an algorithm that checks if a set of $8n$ in $\mathbb{R}^3$ can be split evenly by $3$ mutually orthogonal planes. To our surprise, it seems the probability that a random set of $8$ points chosen uniformly and independently in the unit cube does not admit such a partition is less than $0.001$.
- [22] arXiv:2404.11533 (replaced) [pdf, html, other]
-
Title: Improved Tverberg theorems for certain families of polytopesComments: 10 pagesSubjects: Combinatorics (math.CO)
A theorem of Grünbaum, which states that every $m$-polytope is a refinement of an $m$-simplex, implies the following generalization of Tverberg's theorem: if $f$ is a linear function from an $m$-dimensional polytope $P$ to $\mathbb{R}^d$ and $m \ge (d + 1)(r - 1)$, then there are $r$ pairwise disjoint faces of $P$ whose images intersect. Moreover, the topological Tverberg theorem implies that this statement is true whenever the map $f$ is continuous and $r$ is a prime power. In this note, we show that for certain families of polytopes the lower bound on the dimension $m$ of the polytopes can be significantly improved, both in the affine and topological cases.
- [23] arXiv:2405.13893 (replaced) [pdf, html, other]
-
Title: On a new problem about the local irregularity of graphsComments: 37 pages, 8 figuresSubjects: Combinatorics (math.CO)
A graph/multigraph $G$ is locally irregular if endvertices of every its edge possess different degrees. The locally irregular edge coloring of $G$ is its edge coloring with the property that every color induces a locally irregular sub(multi)graph of $G$; if such a coloring of $G$ exists, the minimum number of colors to color $G$ in this way is the locally irregular chromatic index of $G$ (denoted by ${\rm lir}(G)$). We state the following new problem: given a connected graph $G$ distinct from $K_2$ or $K_3$, what is the minimum number of edges of $G$ to be doubled such that the resulting multigraph is locally irregular edge colorable (with no monochromatic multiedges) using at most two colors? This problem is closely related to several open conjectures (like the Local Irregularity Conjecture for graphs and 2-multigraphs, or (2, 2)-Conjecture) and other similar edge coloring concepts. We present the solution of this problem for several graph classes: paths, cycles, trees, complete graphs, complete $k$-partite graphs, split graphs and powers of cycles. Our solution for complete $k$-partite graphs ($k>1$) and powers of cycles (which are not complete graphs) shows that, in this case, the locally irregular chromatic index equals 2. We also consider this problem for special families of cacti and prove that the minimum number of edges in a graph whose doubling yields an local irregularly colorable multigraph does not have a constant upper bound not only for locally irregular uncolorable cacti.
- [24] arXiv:2409.10738 (replaced) [pdf, html, other]
-
Title: S-Glued sums of latticesChristian Herrmann (Technische Universität Darmstadt), Dale R. WorleyComments: 16 pages, 3 figures. German original by Christian Herrmann, English translation by Dale R. Worley. Added a footnote 1 to give more detail about Dilworth's work on the subjectSubjects: Combinatorics (math.CO)
For many equation-theoretical questions about modular lattices, Hall and Dilworth give a useful construction: Let $L_0$ be a lattice with largest element $u_0$, $L_1$ be a lattice disjoint from $L_0$ with smallest element $v_1$, and $a \in L_0$, $b \in L_1$ such that the intervals $[a, u_0]$ and $[v_1, b]$ are isomorphic. Then, after identifying those intervals you obtain $L_0 \cup L_1$, a lattice structure whose partial order is the transitive relation generated by the partial orders of $L_0$ and $L_1$. It is modular if $L_0$ and $L_1$ are modular. Since in this construction the index set $\{0, 1\}$ is essentially a chain, this work presents a method -- termed S-glued -- whereby a general family $L_x\ (x \in S)$ of lattices can specify a lattice with the small-scale lattice structure determined by the $L_x$ and the large-scale structure determined by $S$. A crucial application is representing finite-length modular lattices using projective geometries.
- [25] arXiv:2409.14620 (replaced) [pdf, other]
-
Title: On the second moment of the determinant of random symmetric, Wigner, and Hermitian matricesSubjects: Combinatorics (math.CO); Probability (math.PR)
In this paper, we analyze the second moment of the determinant of random symmetric, Wigner, and Hermitian matrices. Using analytic combinatorics techniques, we determine the second moment of the determinant of Hermitian matrices whose entries on the diagonal are i.i.d and whose entries above the diagonal are i.i.d. and have real expected values. Our results extend previous work analyzing the second moment of the determinant of symmetric and Wigner matrices, providing a unified approach for this analysis.
- [26] arXiv:2401.11807 (replaced) [pdf, html, other]
-
Title: The weakness of finding descending sequences in ill-founded linear ordersComments: This is an extended version of the homonymous paper published in: Twenty Years of Theoretical and Practical Synergies. CiE 2024. Lecture Notes in Computer Science, vol 14773, pp. 339-350Subjects: Logic (math.LO); Logic in Computer Science (cs.LO); Combinatorics (math.CO)
We explore the Weihrauch degree of the problems ``find a bad sequence in a non-well quasi order'' ($\mathsf{BS}$) and ``find a descending sequence in an ill-founded linear order'' ($\mathsf{DS}$). We prove that $\mathsf{DS}$ is strictly Weihrauch reducible to $\mathsf{BS}$, correcting our mistaken claim in [arXiv:2010.03840]. This is done by separating their respective first-order parts. On the other hand, we show that $\mathsf{BS}$ and $\mathsf{DS}$ have the same finitary and deterministic parts, confirming that $\mathsf{BS}$ and $\mathsf{DS}$ have very similar uniform computational strength. We prove that König's lemma $\mathsf{KL}$ and the problem $\mathsf{wList}_{2^{\mathbb{N}},\leq\omega}$ of enumerating a given non-empty countable closed subset of $2^{\mathbb{N}}$ are not Weihrauch reducible to $\mathsf{DS}$ or $\mathsf{BS}$, resolving two main open questions raised in [arXiv:2010.03840]. We also answer the question, raised in [arXiv:1804.10968], on the existence of a ``parallel quotient'' operator, and study the behavior of $\mathsf{BS}$ and $\mathsf{DS}$ under the quotient with some known problems.
- [27] arXiv:2402.12631 (replaced) [pdf, html, other]
-
Title: Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$Comments: The first version of this arXiv submission, titled "Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits", has since been split into two parts: a longer part and a shorter part. The current version of this arXiv submission is the longer part. The shorter part can be found here: arXiv:2410.00027Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Emerging Technologies (cs.ET); Combinatorics (math.CO); Optimization and Control (math.OC)
We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $\theta$, we consider warm-starts where the initial state is a product state where each qubit position is angle $\theta$ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring $b$.
We illustrate through plots how the properties of $b$ and the initialization angle $\theta$ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the classical algorithm used to create the warm-start.
Additionally, we show that at $\theta=60^\circ$, warm-started QAOA is able to (effectively) recover the cut used to generate the warm-start, thus suggesting that in practice, this value could be a promising starting angle to explore alternate solutions in a heuristic fashion. - [28] arXiv:2403.18450 (replaced) [pdf, html, other]
-
Title: Loop homology of moment-angle complexes in the flag caseComments: 32 pages, revised. v.3: Theorem 1.2 strengthened, minor changesSubjects: Algebraic Topology (math.AT); Combinatorics (math.CO); K-Theory and Homology (math.KT); Rings and Algebras (math.RA)
We develop a general homological approach to presentations of connected graded associative algebras, and apply it to the loop homology of moment-angle complexes $Z_K$ that correspond to flag simplicial complexes $K$. For arbitrary coefficient ring, we describe generators of the Pontryagin algebra $H_*(\Omega Z_K)$ and defining relations between them. We prove that such moment-angle complexes are coformal over $\mathbb{Q},$ give a necessary condition for rational formality, and compute their homotopy groups in terms of homotopy groups of spheres.