cs.DM

arXiv:2210.09227v2 Announce Type: replace-cross Abstract: Ramsey theory is a central and active branch of combinatorics. Although Ramsey numbers for graphs have been extensively investigated since Ramsey's work in the 1930s, there is still an exponential gap between the best known lower and upper bounds. For $k$-uniform hypergraphs, the bounds are of tower-type, where the height grows with $k$. Here, we give a multidimensional generalisation of Ramsey's Theorem to Cartesian products of graphs, proving that a doubly exponential upper bound suffices in every dimension. More precisely, we prove that for every positive integers $r,n,d$, in any $r$-colouring of the edges of the Cartesian product $\square^{d} K_N$ of $d$ copies of $K_N$, there is a copy of $\square^{d} K_n$ such that the edges in each direction are monochromatic, provided that $N\geq 2^{2^{C_drn^{d}}}$. As an application of our approach we also obtain improvements on the multidimensional Erd\H{o}s-Szekeres Theorem proved by Fishburn and Graham $30$ years ago. Their bound was recently improved by Buci\'c, Sudakov, and Tran, who gave an upper bound that is triply exponential in four or more dimensions. We improve upon their results showing that a doubly expoenential upper bounds holds any number of dimensions.

arXiv:2501.00784v1 Announce Type: cross Abstract: In 2009 Benoit Cloitre introduced a certain self-generating sequence $$(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots,$$ with the property that the sum of the terms appearing in the $n$'th run equals twice the $n$'th term of the sequence. We give a connection between this sequence and the paperfolding sequence, and then prove Cloitre's conjecture about the density of $1$'s appearing in $(a_n)_{n \geq 1}$.

arXiv:2412.14784v2 Announce Type: replace-cross Abstract: In this paper, we study the following question. Let $\mathcal G$ be a family of planar graphs and let $k\geq 3$ be an integer. What is the largest value $f_k(n)$ such that every $n$-vertex graph in $\mathcal G$ has an induced subgraph with degree at most $k$ and with $f_k(n)$ vertices? Similar questions, in which one seeks a large induced forest, or a large induced linear forest, or a large induced $d$-degenerate graph, rather than a large induced graph of bounded degree, have been studied for decades and have given rise to some of the most fascinating and elusive conjectures in Graph Theory. We tackle our problem when $\mathcal G$ is the class of the outerplanar graphs or the class of the planar graphs. In both cases, we provide upper and lower bounds on the value of $f_k(n)$. For example, we prove that every $n$-vertex planar graph has an induced subgraph with degree at most $3$ and with $\frac{5n}{13}>0.384n$ vertices, and that there exist $n$-vertex planar graphs whose largest induced subgraph with degree at most $3$ has $\frac{4n}{7}+O(1)<0.572n+O(1)$ vertices.

arXiv:2411.04479v2 Announce Type: replace-cross Abstract: We prove that the number of partitions of the hypercube ${\bf Z}_q^n$ into $q^m$ subcubes of dimension $n-m$ each for fixed $q$, $m$ and growing $n$ is asymptotically equal to $n^{(q^m-1)/(q-1)}$. For the proof, we introduce the operation of the bang of a star matrix and demonstrate that any star matrix, except for a fractal, is expandable under some bang, whereas a fractal remains to be a fractal under any bang.

arXiv:2411.06857v2 Announce Type: replace Abstract: We study algebraic properties of partition functions, particularly the location of zeros, through the lens of rapidly mixing Markov chains. The classical Lee-Yang program initiated the study of phase transitions via locating complex zeros of partition functions. Markov chains, besides serving as algorithms, have also been used to model physical processes tending to equilibrium. In many scenarios, rapid mixing of Markov chains coincides with the absence of phase transitions (complex zeros). Prior works have shown that the absence of phase transitions implies rapid mixing of Markov chains. We reveal a converse connection by lifting probabilistic tools for the analysis of Markov chains to study complex zeros of partition functions. Our motivating example is the independence polynomial on $k$-uniform hypergraphs, where the best-known zero-free regime has been significantly lagging behind the regime where we have rapidly mixing Markov chains for the underlying hypergraph independent sets. Specifically, the Glauber dynamics is known to mix rapidly on independent sets in a $k$-uniform hypergraph of maximum degree $\Delta$ provided that $\Delta \lesssim 2^{k/2}$. On the other hand, the best-known zero-freeness around the point $1$ of the independence polynomial on $k$-uniform hypergraphs requires $\Delta \le 5$, the same bound as on a graph. By introducing a complex extension of Markov chains, we lift an existing percolation argument to the complex plane, and show that if $\Delta \lesssim 2^{k/2}$, the Markov chain converges in a complex neighborhood, and the independence polynomial itself does not vanish in the same neighborhood. In the same regime, our result also implies central limit theorems for the size of a uniformly random independent set, and deterministic approximation algorithms for the number of hypergraph independent sets of size $k \le \alpha n$ for some constant $\alpha$.

arXiv:2109.08745v4 Announce Type: replace Abstract: We initiate the study of sublinear-time algorithms that access their input via an online adversarial erasure oracle. After answering each input query, such an oracle can erase $t$ input values. Our goal is to understand the complexity of basic computational tasks in extremely adversarial situations, where the algorithm's access to data is blocked during the execution of the algorithm in response to its actions. Specifically, we focus on property testing in the model with online erasures. We show that two fundamental properties of functions, linearity and quadraticity, can be tested for constant $t$ with asymptotically the same complexity as in the standard property testing model. For linearity testing, we prove tight bounds in terms of $t$, showing that the query complexity is $\Theta(\log t).$ In contrast to linearity and quadraticity, some other properties, including sortedness and the Lipschitz property of sequences, cannot be tested at all, even for $t=1$. Our investigation leads to a deeper understanding of the structure of violations of linearity and other widely studied properties. We also consider implications of our results for algorithms that are resilient to online adversarial corruptions instead of erasures.

arXiv:2501.00161v1 Announce Type: new Abstract: The $H$-Induced Minor Containment problem ($H$-IMC) consists in deciding if a fixed graph $H$ is an induced minor of a graph $G$ given as input, that is, whether $H$ can be obtained from $G$ by deleting vertices and contracting edges. Several graphs $H$ are known for which $H$-IMC is \NP-complete, even when $H$ is a tree. In this paper, we investigate which conditions on $H$ and $G$ are sufficient so that the problem becomes polynomial-time solvable. Our results identify three infinite classes of graphs such that, if $H$ belongs to one of these classes, then $H$-IMC can be solved in polynomial time. Moreover, we show that if the input graph $G$ excludes long induced paths, then $H$-IMC is polynomial-time solvable for any fixed graph $H$. As a byproduct of our results, this implies that $H$-IMC is polynomial-time solvable for all graphs $H$ with at most $5$ vertices, except for three open cases.

arXiv:2501.00991v1 Announce Type: new Abstract: We investigate the structure of graphs of twin-width at most $1$, and obtain the following results: - Graphs of twin-width at most $1$ are permutation graphs. In particular they have an intersection model and a linear structure. - There is always a $1$-contraction sequence closely following a given permutation diagram. - Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a $1$-contraction sequence of a graph, or guarantees that it has twin-width more than $1$. - We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs.

arXiv:2501.00144v1 Announce Type: cross Abstract: It is well-known by now that any state of the $3\times 3 \times 3$ Rubik's Cube can be solved in at most 20 moves, a result often referred to as "God's Number". However, this result took Rokicki et al. around 35 CPU years to prove and is therefore very challenging to reproduce. We provide a novel approach to obtain a worse bound of 36 moves with high confidence, but that offers two main advantages: (i) it is easy to understand, reproduce, and verify, and (ii) our main idea generalizes to bounding the diameter of other vertex-transitive graphs by at most twice its true value, hence the name "demigod number". Our approach is based on the fact that, for vertex-transitive graphs, the average distance between vertices is at most half the diameter, and by sampling uniformly random states and using a modern solver to obtain upper bounds on their distance, a standard concentration bound allows us to confidently state that the average distance is around $18.32 \pm 0.1$, from where the diameter is at most $36$.

arXiv:2501.00157v1 Announce Type: cross Abstract: Given a hypergraph $H=(V,E)$, define for every edge $e\in E$ a linear expression with arguments corresponding with the vertices. Next, let the polynomial $p_H$ be the product of such linear expressions for all edges. Our main goal was to find a relationship between the Alon-Tarsi number of $p_H$ and the edge density of $H$. We prove that $AT(p_H)=\lceil ed(H)\rceil+1$ if all the coefficients in $p_H$ are equal to $1$. Our main result is that, no matter what those coefficients are, they can be permuted within the edges so that for the resulting polynomial $p_H^\prime$, $AT(p_H^\prime)\leq 2\lceil ed(H)\rceil+1$ holds. We conjecture that, in fact, permuting the coefficients is not necessary. If this were true, then in particular a significant generalization of the famous 1-2-3 Conjecture would follow.

arXiv:2406.13902v3 Announce Type: replace-cross Abstract: We prove the existence of signed combinatorial interpretations for several large families of structure constants. These families include standard bases of symmetric and quasisymmetric polynomials, as well as various bases in Schubert theory. The results are stated in the language of computational complexity, while the proofs are based on the effective M\"obius inversion.

arXiv:2403.13393v2 Announce Type: replace Abstract: On the one side, the formalism of Global Transformations comes with the claim of capturing any transformation of space that is local, synchronous and deterministic.The claim has been proven for different classes of models such as mesh refinements from computer graphics, Lindenmayer systems from morphogenesis modeling and cellular automata from biological, physical and parallel computation modeling.The Global Transformation formalism achieves this by using category theory for its genericity, and more precisely the notion of Kan extension to determine the global behaviors based on the local ones.On the other side, Causal Graph Dynamics describe the transformation of port graphs in a synchronous and deterministic way and has not yet being tackled.In this paper, we show the precise sense in which the claim of Global Transformations holds for them as well.This is done by showing different ways in which they can be expressed as Kan extensions, each of them highlighting different features of Causal Graph Dynamics.Along the way, this work uncovers the interesting class of Monotonic Causal Graph Dynamics and their universality among General Causal Graph Dynamics.

arXiv:2412.17930v1 Announce Type: cross Abstract: The paperfolding sequences form an uncountable class of infinite sequences over the alphabet $\{ -1, 1 \}$ that describe the sequence of folds arising from iterated folding of a piece of paper, followed by unfolding. In this note we observe that the sequence of run lengths in such a sequence, as well as the starting and ending positions of the $n$'th run, is $2$-synchronized and hence computable by a finite automaton. As a specific consequence, we obtain the recent results of Bunder, Bates, and Arnold, in much more generality, via a different approach. We also prove results about the critical exponent and subword complexity of these run-length sequences.

arXiv:2412.18595v1 Announce Type: cross Abstract: Let $B$ be a set of Eulerian subgraphs of a graph $G$. We say $B$ forms a $k$-basis if it is a minimum set that generates the cycle space of $G$, and any edge of $G$ lies in at most $k$ members of $B$. The basis number of a graph $G$, denoted by $b(G)$, is the smallest integer such that $G$ has a $k$-basis. A graph is called 1-planar (resp. planar) if it can be embedded in the plane with at most one crossing (resp. no crossing) per edge. MacLane's planarity criterion characterizes planar graphs based on their cycle space, stating that a graph is planar if and only if it has a $2$-basis. We study here the basis number of 1-planar graphs, demonstrate that it is unbounded in general, and show that it is bounded for many subclasses of 1-planar graphs.

arXiv:2412.18599v1 Announce Type: new Abstract: Theoretical guarantees for double spending probabilities for the Nakamoto consensus under the $k$-deep confirmation rule have been extensively studied for zero/bounded network delays and fixed mining rates. In this paper, we introduce a ruin-theoretical model of double spending for Nakamoto consensus under the $k$-deep confirmation rule when the honest mining rate is allowed to be an arbitrary function of time including the block delivery periods, i.e., time periods during which mined blocks are being delivered to all other participants of the network. Time-varying mining rates are considered to capture the intrinsic characteristics of the peer to peer network delays as well as dynamic participation of miners such as the gap game and switching between different cryptocurrencies. Ruin theory is leveraged to obtain the double spend probabilities and numerical examples are presented to validate the effectiveness of the proposed analytical method.

arXiv:2412.18109v1 Announce Type: new Abstract: Today, several people and organizations rely on cloud platforms. The reliability of cloud platforms depends heavily on the performance of their internal programs (agents). To better prevent regressions in cloud platforms, the design of pre-production testing environments (that test new agents, new hardwares, and other changes) must take into account the diversity of server/node properties (hardware model, virtual machine type, etc.) across the fleet and dynamically emphasize or de-emphasize the prevalence of certain node properties based on current testing priorities. This paper formulates this task as the "environment design" problem and presents the EnvDesign model, a method that uses graph theory and optimization algorithms to solve the environment design problem. The EnvDesign model was built on context and techniques that apply to combinatorial testing in general, so it can support combinatorial testing in other domains.

arXiv:2412.18571v1 Announce Type: cross Abstract: Hard combinatorial optimization problems, often mapped to Ising models, promise potential solutions with quantum advantage but are constrained by limited qubit counts in near-term devices. We present an innovative quantum-inspired framework that dynamically compresses large Ising models to fit available quantum hardware of different sizes. Thus, we aim to bridge the gap between large-scale optimization and current hardware capabilities. Our method leverages a physics-inspired GNN architecture to capture complex interactions in Ising models and accurately predict alignments among neighboring spins (aka qubits) at ground states. By progressively merging such aligned spins, we can reduce the model size while preserving the underlying optimization structure. It also provides a natural trade-off between the solution quality and size reduction, meeting different hardware constraints of quantum computing devices. Extensive numerical studies on Ising instances of diverse topologies show that our method can reduce instance size at multiple levels with virtually no losses in solution quality on the latest D-wave quantum annealers.

arXiv:2412.16789v1 Announce Type: new Abstract: Projection ghosts are discrete arrays of signed values positioned so that their discrete projections vanish for some chosen set of n projection angles. Minimal ghosts are designed to be compact, with no internal pixels having value zero. Here we control the shape, number of boundary pixels and area that each minimal ghost encloses. Binary minimal ghosts and their boundaries can themselves be inflated by tiling copies of themselves to make ghosts with larger sizes and different shapes, whilst still retaining the same set of n zero projection angles. The intricate perimeters of minimal ghosts are formed by three strings of connected pixels that are defined by the minimal projection angles. We show that large changes to the ghost areas can be made whilst keeping the length of their segmented perimeters fixed. These inflated boundary ghosts may prove useful as secure watermarks to embed into digital image data. Boundary ghosts may also help guide the selection of angles used to reconstruct images where the object domain is confined to oval shaped arcs.

arXiv:2412.17140v1 Announce Type: cross Abstract: The presented work focuses on problems from determinant theory, set theory and topology. The term graph is the binding element that connects these problems. Graphs are distinguished by their geometrical simplicity, which helps in showing the equivalence between various seemingly unrelated problems, besides providing solutions to several open questions discussed here.

arXiv:2412.17115v1 Announce Type: new Abstract: Whether or not the Sparsest Cut problem admits an efficient $O(1)$-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture. We design an $O(1)$-approximation algorithm to Sparsest Cut for the class of Cayley graphs over Abelian groups, running in time $n^{O(1)}\cdot \exp\{d^{O(d)}\}$ where $d$ is the degree of the graph. Previous work has centered on solving cut problems on graphs which are ``expander-like'' in various senses, such as being a small-set expander or having low threshold rank. In contrast, low-degree Abelian Cayley graphs are natural examples of non-expanding graphs far from these assumptions (e.g. the cycle). We demonstrate that spectral and semidefinite programming-based methods can still succeed in these graphs by analyzing an eigenspace enumeration algorithm which searches for a sparse cut among the low eigenspace of the Laplacian matrix. We dually interpret this algorithm as searching for a hyperplane cut in a low-dimensional embedding of the graph. In order to analyze the algorithm, we prove a bound of $d^{O(d)}$ on the number of eigenvalues ``near'' $\lambda_2$ for connected degree-$d$ Abelian Cayley graphs. We obtain a tight bound of $2^{\Theta(d)}$ on the multiplicity of $\lambda_2$ itself which improves on a previous bound of $2^{O(d^2)}$ by Lee and Makarychev.