math.CO
81 postsarXiv:2210.14100v4 Announce Type: replace Abstract: The Additive-Multiplicative Matrix Channel (AMMC) was introduced by Silva, Kschischang and K\"otter in 2010 to model data transmission using random linear network coding. The input and output of the channel are $n\times m$ matrices over a finite field $\mathbb{F}_q$. On input the matrix $X$, the channel outputs $Y=A(X+W)$ where $A$ is a uniformly chosen $n\times n$ invertible matrix over $\mathbb{F}_q$ and where $W$ is a uniformly chosen $n\times m$ matrix over $\mathbb{F}_q$ of rank $t$. Silva \emph{et al} considered the case when $2n\leq m$. They determined the asymptotic capacity of the AMMC when $t$, $n$ and $m$ are fixed and $q\rightarrow\infty$. They also determined the leading term of the capacity when $q$ is fixed, and $t$, $n$ and $m$ grow linearly. We generalise these results, showing that the condition $2n\geq m$ can be removed. (Our formula for the capacity falls into two cases, one of which generalises the $2n\geq m$ case.) We also improve the error term in the case when $q$ is fixed.
arXiv:2411.19351v2 Announce Type: replace-cross Abstract: This article presents examples of an application of the finite field method for the computation of the characteristic polynomial of the matching arrangement of a graph. Weight functions on edges of a graph with weights from a finite field are divided into proper and improper functions in connection with proper colorings of vertices of the matching polytope of a graph. An improper weight function problem is introduced, a proof of its NP-completeness is presented, and a knapsack-like public key cryptosystem is constructed based on the improper weight function problem.
arXiv:2501.11617v1 Announce Type: cross Abstract: For every positive integer $k$, we define the $k$-treedepth as the largest graph parameter $\mathrm{td}_k$ satisfying (i) $\mathrm{td}_k(\emptyset)=0$; (ii) $\mathrm{td}_k(G) \leq 1+ \mathrm{td}_k(G-u)$ for every graph $G$ and every vertex $u \in V(G)$; and (iii) if $G$ is a $(<k)$-clique-sum of $G_1$ and $G_2$, then $\mathrm{td}_k(G) \leq \max \{\mathrm{td}_k(G_1),\mathrm{td}_k(G_2)\}$, for all graphs $G_1,G_2$. This parameter coincides with treedepth if $k=1$, and with treewidth plus $1$ if $k \geq |V(G)|$. We prove that for every positive integer $k$, a class of graphs $\mathcal{C}$ has bounded $k$-treedepth if and only if there is a positive integer $\ell$ such that for every tree $T$ on $k$ vertices, no graph in $\mathcal{C}$ contains $T \square P_\ell$ as a minor. This implies for $k=1$ that a minor-closed class of graphs has bounded treedepth if and only if it excludes a path, for $k=2$ that a minor-closed class of graphs has bounded $2$-treedepth if and only if it excludes as a minor a ladder (Huynh, Joret, Micek, Seweryn, and Wollan; Combinatorica, 2021), and for large values of $k$ that a minor-closed class of graphs has bounded treewidth if and only if it excludes a grid (Grid-Minor Theorem, Robertson and Seymour; JCTB, 1986). As a corollary, we obtain the following qualitative strengthening of the Grid-Minor Theorem in the case of bounded-height grids. For all positive integers $k, \ell$, every graph that does not contain the $k \times \ell$ grid as a minor has $(2k-1)$-treedepth at most a function of $(k, \ell)$.
arXiv:2501.11156v1 Announce Type: cross Abstract: We study hyperplane covering problems for finite grid-like structures in $\mathbb{R}^d$. We call a set $\mathcal{C}$ of points in $\mathbb{R}^2$ a conical grid if the line $y = a_i$ intersects $\mathcal{C}$ in exactly $i$ points, for some $a_1 > \cdots > a_n \in \mathbb{R}$. We prove that the number of lines required to cover every point of such a grid at least $k$ times is at least $nk\left(1-\frac{1}{e}-O(\frac{1}{n}) \right)$. If the grid $\mathcal{C}$ is obtained by cutting an $m \times n$ grid of points into a half along one of the diagonals, then we prove the lower bound of $mk\left(1-e^{-\frac{n}{m}}-O(\frac{n}{m^2})\right)$. Motivated by the Alon-F\"uredi theorem on hyperplane coverings of grids that miss a point and its multiplicity variations, we study the problem of finding the minimum number of hyperplanes required to cover every point of an $n \times \cdots \times n$ half-grid in $\mathbb{R}^d$ at least $k$ times while missing a point $P$. For almost all such half-grids, with $P$ being the corner point, we prove asymptotically sharp upper and lower bounds for the covering number in dimensions $2$ and $3$. For $k = 1$, $d = 2$, and an arbitrary $P$, we determine this number exactly by using the polynomial method bound for grids.
arXiv:2403.09122v2 Announce Type: replace Abstract: A monitoring edge-geodetic set, or simply an MEG-set, of a graph $G$ is a vertex subset $M \subseteq V(G)$ such that given any edge $e$ of $G$, $e$ lies on every shortest $u$-$v$ path of $G$, for some $u,v \in M$. The monitoring edge-geodetic number of $G$, denoted by $meg(G)$, is the minimum cardinality of such an MEG-set. This notion provides a graph theoretic model of the network monitoring problem. In this article, we compare $meg(G)$ with some other graph theoretic parameters stemming from the network monitoring problem and provide examples of graphs having prescribed values for each of these parameters. We also characterize graphs $G$ that have $V(G)$ as their minimum MEG-set, which settles an open problem due to Foucaud \textit{et al.} (CALDAM 2023), and prove that some classes of graphs fall within this characterization. We also provide a general upper bound for $meg(G)$ for sparse graphs in terms of their girth, and later refine the upper bound using the chromatic number of $G$. We examine the change in $meg(G)$ with respect to two fundamental graph operations: clique-sum and subdivisions. In both cases, we provide a lower and an upper bound of the possible amount of changes and provide (almost) tight examples.
arXiv:2403.15987v2 Announce Type: replace-cross Abstract: We define term rewriting systems on the vertices and faces of nestohedra, and show that the former are confluent and terminating. While the associated posets on vertices generalize Barnard--McConville's flip order for graph-associahedra, the preorders on faces generalize the facial weak order for permutahedra and the generalized Tamari order for associahedra. Moreover, we define and study contextual families of nestohedra, whose local confluence diagrams satisfy a certain uniformity condition. Among them are associahedra and operahedra, whose associated proofs of confluence for their rewriting systems reproduce proofs of categorical coherence theorems for monoidal categories and categorified operads.
arXiv:2501.11226v1 Announce Type: cross Abstract: Small-world networks, known for their high local clustering and short average path lengths, are a fundamental structure in many real-world systems, including social, biological, and technological networks. We apply the theory of local convergence (Benjamini-Schramm convergence) to derive the limiting behavior of the local structures for two of the most commonly studied small-world network models: the Watts-Strogatz model and the Kleinberg model. Establishing local convergence enables us to show that key network measures, such as PageRank, clustering coefficients, and maximum matching size, converge as network size increases with their limits determined by the graph's local structure. Additionally, this framework facilitates the estimation of global phenomena, such as information cascades, using local information from small neighborhoods. As an additional outcome of our results, we observe a critical change in the behavior of the limit exactly when the parameter governing long-range connections in the Kleinberg model crosses the threshold where decentralized search remains efficient, offering a new perspective on why decentralized algorithms fail in certain regimes.
arXiv:2501.11437v1 Announce Type: cross Abstract: This paper explores a full generalization of the classical corner-vector method for constructing weighted spherical designs, which we call the {\it generalized corner-vector method}. First we establish a uniform upper bound for the degree of designs obtained from the proposed method. Our proof is a hybrid argument that employs techniques in analysis and combinatorics, especially a famous result by Xu(1998) on the interrelation between spherical designs and simplical designs, and the cross-ratio comparison method for Hilbert identities introduced by Nozaki and Sawa(2013). We extensively study conditions for the existence of designs obtained from our method, and present many curious examples of degree $7$ through $13$, some of which are, to our surprise, characterized in terms of integral lattices.
arXiv:2501.11192v1 Announce Type: new Abstract: We prove new parameterized complexity results for the FO Model Checking problem and in particular for Independent Set, for two recently introduced subclasses of $H$-graphs, namely proper $H$-graphs and non-crossing $H$-graphs. It is known that proper $H$-graphs, and thus $H$-graphs, may have unbounded twin-width. However, we prove that for every connected multigraph $H$ with no self-loops, non-crossing $H$-graphs have bounded proper mixed-thinness, and thus bounded twin-width. Consequently, we can apply a well-known result of Bonnet, Kim, Thomass\'e, and Watrigant (2021) to find that the FO Model Checking problem is in $\mathsf{FPT}$ for non-crossing $H$-graphs when parameterized by $\Vert H \Vert+\ell$, where $\Vert H \Vert$ is the size of $H$ and $\ell$ is the size of a formula. In particular, this implies that Independent Set is in $\mathsf{FPT}$ on non-crossing $H$-graphs when parameterized by $\Vert H \Vert+k$, where $k$ is the solution size. In contrast, Independent Set for general $H$-graphs is $\mathsf{W[1]}$-hard when parameterized by $\Vert H \Vert +k$. We strengthen the latter result by proving thatIndependent Set is $\mathsf{W[1]}$-hard even on proper $H$-graphs when parameterized by $\Vert H \Vert+k$. In this way, we solve, subject to $\mathsf{W[1]}\neq \mathsf{FPT}$, an open problem of Chaplick (2023), who asked whether there exist problems that can be solved faster for non-crossing $H$-graphs than for proper $H$-graphs.
arXiv:2501.10852v1 Announce Type: new Abstract: The formalisation of mathematics is starting to become routine, but the value of this technology to the work of mathematicians remains to be shown. There are few examples of using proof assistants to verify brand-new work. This paper reports the formalisation of a major new result (arXiv:2303.09521) about Ramsey numbers that was announced in 2023. One unexpected finding was the heavy need for computer algebra techniques.
arXiv:2501.11978v1 Announce Type: new Abstract: In this paper, we determine the complete weight distribution of the space $ \mathbb{F}_q^N $ endowed by the weighted coordinates poset block metric ($(P,w,\pi)$-metric), also known as the $(P,w,\pi)$-space, thereby obtaining it for $(P,w)$-space, $(P,\pi)$-space, $\pi$-space, and $P$-space as special cases. Further, when $P$ is a chain, the resulting space is called as Niederreiter-Rosenbloom-Tsfasman (NRT) weighted block space and when $P$ is hierarchical, the resulting space is called as weighted coordinates hierarchical poset block space. The complete weight distribution of both the spaces are deduced from the main result. Moreover, we define an $I$-ball for an ideal $I$ in $P$ and study the characteristics of it in $(P,w,\pi)$-space. We investigate the relationship between the $I$-perfect codes and $t$-perfect codes in $(P,w,\pi)$-space. Given an ideal $I$, we investigate how the maximum distance separability (MDS) is related with $I$-perfect codes and $t$-perfect codes in $(P,w,\pi)$-space. Duality theorem is derived for an MDS $(P,w,\pi)$-code when all the blocks are of same length. Finally, the distribution of codewords among $r$-balls is analyzed in the case of chain poset, when all the blocks are of same length.
arXiv:2501.10918v1 Announce Type: cross Abstract: In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted digraph, the minimum weight of a dicut is equal to the maximum size of a packing of dijoins. This has been disproved. However, the unweighted version conjectured by Woodall remains open. We prove that the Edmonds-Giles conjecture is true if the underlying undirected graph is chordal. We also give a strongly polynomial time algorithm to construct such a packing.
arXiv:2501.10828v1 Announce Type: cross Abstract: The (strong) isometric path complexity is a recently introduced graph invariant that captures how arbitrary isometric paths (i.e. shortest paths) of a graph can be viewed as a union of few ``rooted" isometric paths (i.e. isometric paths with a common end-vertex). It is known that this parameter can be computed optimally in polynomial time. Seemingly unrelated graph classes studied in metric graph theory (e.g. hyperbolic graphs), geometric intersection graph theory (e.g. outerstring graphs), and structural graph theory (e.g. (theta, prism, pyramid)-free graphs) have been shown to have bounded strong isometric path complexity [Chakraborty et al., MFCS '23]. We show that important graph classes studied in \emph{coarse graph theory} (as introduced by [Georgakopoulos & Papasoglu '23]) have bounded strong isometric path complexity. We show that the strong isometric path complexity of $K_{2,t}$-asymptotic minor-free graphs is bounded. Let $U_t$ denote the graph obtained by adding a universal vertex to a path of $t-1$ edges. We show that the strong isometric path complexity of $U_t$-asymptotic minor-free graphs is bounded. This implies $K_4^-$-asymptotic minor-free graphs, i.e. graphs that are quasi-isometric to a cactus [Fujiwara & Papasoglu '23] have bounded strong isometric path complexity. On the other hand, $K_4$-minor-free graphs have unbounded strong isometric path complexity. We show that graphs whose all induced cycles of length at least 4 have the same length (also known as monoholed graphs as defined by [Cook et al., JCTB '24]) form a subclass of $U_4$-asymptotic minor-free graphs. Hence, the strong isometric path complexity of monoholed graphs is bounded. We show that even-hole free graphs have unbounded strong isometric path complexity. We show that the strong isometric path complexity is preserved under the fixed power, line graph, and clique-sums operators.
arXiv:2501.12062v1 Announce Type: new Abstract: Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an $\ell$-colouring of a $k$-colourable $r$-uniform hypergraph is NP-hard for all constant $2\leq k\leq \ell$ and $r\geq 3$. This provides a shorter proof of a celebrated result by Dinur et al. [FOCS'02/Combinatorica'05]. Secondly, we show that finding an $\ell$-conflict-free colouring of an $r$-uniform hypergraph that admits a $k$-conflict-free colouring is NP-hard for all constant $3\leq k\leq\ell$ and $r\geq 4$, except for $r=4$ and $k=2$ (and any $\ell$); this case is solvable in polynomial time. The case of $r=3$ is the standard nonmonochromatic colouring, and the case of $r=2$ is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an $\ell$-linearly-ordered colouring of an $r$-uniform hypergraph that admits a $k$-linearly-ordered colouring is NP-hard for all constant $3\leq k\leq\ell$ and $r\geq 4$, thus improving on the results of Nakajima and \v{Z}ivn\'y~[ICALP'22/ACM TocT'23].
arXiv:2408.00933v2 Announce Type: replace-cross Abstract: The bad science matrix problem consists in finding, among all matrices $A \in \mathbb{R}^{n \times n}$ with rows having unit $\ell^2$ norm, one that maximizes $\beta(A) = \frac{1}{2^n} \sum_{x \in \{-1, 1\}^n} \|Ax\|_\infty$. Our main contribution is an explicit construction of an $n \times n$ matrix $A$ showing that $\beta(A) \geq \sqrt{\log_2(n+1)}$, which is only 18% smaller than the asymptotic rate. We prove that every entry of any optimal matrix is a square root of a rational number, and we find provably optimal matrices for $n \leq 4$.
arXiv:2501.11380v1 Announce Type: new Abstract: Temporal graphs arise when modeling interactions that evolve over time. They usually come in several flavors, depending on the number of parameters used to describe the temporal aspects of the interactions: time of appearance, duration, delay of transmission. In the point model, edges appear at specific points in time, while in the more general interval model, edges can be present over multiple time intervals. In both models, the delay for traversing an edge can change with each edge appearance. When time is discrete, the two models are equivalent in the sense that the presence of an edge during an interval is equivalent to a sequence of point-in-time occurrences of the edge. However, this transformation can drastically change the size of the input and has complexity issues. Indeed, we show a gap between the two models with respect to the complexity of the classical problem of computing a fastest temporal path from a source vertex to a target vertex, i.e. a path where edges can be traversed one after another in time and such that the total duration from source to target is minimized. It can be solved in near-linear time in the point model, while we show that the interval model requires quadratic time under classical assumptions of fine-grained complexity. With respect to linear time, our lower bound implies a factor of the number of vertices, while the best known algorithm has a factor of the number of underlying edges. Interestingly, we show that near-linear time is possible in the interval model when restricted to all delays being zero, i.e. traversing an edge is instantaneous.
arXiv:2501.11281v1 Announce Type: cross Abstract: A proper edge coloring of a graph without any bichromatic cycles is said to be an acyclic edge coloring of the graph. The acyclic chromatic index of a graph $G$ denoted by $a'(G)$, is the minimum integer $k$ such that $G$ has an acyclic edge coloring with $k$ colors. Fiam\v{c}\'{\i}k conjectured that for a graph $G$ with maximum degree $\Delta$, $a'(G) \le \Delta+2$. A graph $G$ is said to be $3$-sparse if every edge in $G$ is incident on at least one vertex of degree at most $3$. We prove the conjecture for the class of $3$-sparse graphs. Further, we give a stronger bound of $\Delta +1$, if there exists an edge $xy$ in the graph with $d_G(x)+ d_G(y) 3$, the $3$-sparse graphs where no such edge exists is the set of bipartite graphs where one partition has vertices with degree exactly $3$ and the other partition has vertices with degree exactly $\Delta$.
arXiv:2501.11386v1 Announce Type: cross Abstract: This paper proves the minimum size of a supersequence over a set of eight elements is 52. This disproves a conjecture that the lower bound of the supersequence is the partial sum of the geometric Connell sequence. By studying the internal distribution of individual elements within sub-strings of the supersequence called segments, the proof provides important results on the internal structure that could help to understand the general lower bound problem for finite sets.
arXiv:2501.10633v1 Announce Type: new Abstract: We introduce the meta-problem Sidestep$(\Pi, \mathsf{dist}, d)$ for a problem $\Pi$, a metric $\mathsf{dist}$ over its inputs, and a map $d: \mathbb N \to \mathbb R_+ \cup \{\infty\}$. A solution to Sidestep$(\Pi, \mathsf{dist}, d)$ on an input $I$ of $\Pi$ is a pair $(J, \Pi(J))$ such that $\mathsf{dist}(I,J) \leqslant d(|I|)$ and $\Pi(J)$ is a correct answer to $\Pi$ on input $J$. This formalizes the notion of answering a related question (or sidestepping the question), for which we give some practical and theoretical motivations, and compare it to the neighboring concepts of smoothed analysis, planted problems, and edition problems. Informally, we call hardness radius the ``largest'' $d$ such that Sidestep$(\Pi, \mathsf{dist}, d)$ is NP-hard. This framework calls for establishing the hardness radius of problems $\Pi$ of interest for the relevant distances $\mathsf{dist}$. We exemplify it with graph problems and two distances $\mathsf{dist}_\Delta$ and $\mathsf{dist}_e$ (the edge edit distance) such that $\mathsf{dist}_\Delta(G,H)$ (resp. $\mathsf{dist}_e(G,H)$) is the maximum degree (resp. number of edges) of the symmetric difference of $G$ and $H$ if these graphs are on the same vertex set, and $+\infty$ otherwise. We show that the decision problems Independent Set, Clique, Vertex Cover, Coloring, Clique Cover have hardness radius $n^{\frac{1}{2}-o(1)}$ for $\mathsf{dist}_\Delta$, and $n^{\frac{4}{3}-o(1)}$ for $\mathsf{dist}_e$, that Hamiltonian Cycle has hardness radius 0 for $\mathsf{dist}_\Delta$, and somewhere between $n^{\frac{1}{2}-o(1)}$ and $n/3$ for $\mathsf{dist}_e$, and that Dominating Set has hardness radius $n^{1-o(1)}$ for $\mathsf{dist}_e$. We leave several open questions.
arXiv:2501.07558v1 Announce Type: new Abstract: We prove that the class of 3D-grids is cannot be transduced from planar graphs, and more generally, from any class of graphs of bounded Euler genus. To prove our result, we introduce a new structural tool called slice decompositions, and show that every graph class transducible from a class of graphs of bounded Euler genus is a perturbation of a graph class that admits slice decompositions.