Search

The eternal vertex cover problem is a variant of the classical vertex cover problem defined in terms of an infinite attacker–defender game played on a graph. In each round of the game, the defender reconfigures guards from one vertex cover to another in response to a move by the attacker. The minimum number of guards required in any winning strategy of the defender when this game is played on a graph G is the eternal vertex cover number of G , denoted by evc ( G ) . It is known that given a graph G and an integer k , checking whether evc ( G ) ≤ k is NP-hard. Further, it is known that for any graph G , mvc ( G ) ≤ evc ( G ) ≤ 2 mvc ( G ) , where mvc ( G ) is the vertex cover number of G . Though a characterization is known for graphs for which evc ( G ) = 2 mvc ( G ) , a characterization of graphs for which evc ( G ) = mvc ( G ) remained as an open problem, since 2009. We achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For biconnected chordal graphs, our characterization leads to a polynomial time algorithm for precisely determining evc ( G ) and an algorithm for determining a safe strategy for guard movement in each round of the game using only evc ( G ) guards. Though the eternal vertex cover problem is only known to be in PSPACE in general, it follows from our new characterization that the problem is in NP for locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs. We also provide reductions establishing NP-completeness of the problem for biconnected internally triangulated planar graphs. As far as we know, this is the first NP-completeness result known for the problem for any graph class.

The atom-bond connectivity (ABC) index is a degree-based molecular descriptor that found diverse chemical applications. Characterizing trees with minimum ABC-index remained an elusive open problem even after serious attempts and is considered by some as one of the most intriguing open problems in mathematical chemistry. In this paper, we describe the exact structure of the extremal trees with sufficiently many vertices and we show how their structure evolves when the number of vertices grows. An interesting fact is that their radius is at most 5 and that all vertices except for one have degree at most 54. In fact, all but at most O ( 1 ) vertices have degree 1, 2, 4, or 53. Let γ n = min ⁡ { ABC ( T ) : T is a tree of order n } . It is shown that γ n = 1 365 1 53 ( 1 + 26 55 + 156 106 ) n + O ( 1 ) ≈ 0.67737178 n + O ( 1 ) .

The directed power graph $$\vec {\mathcal {G}}( G)$$ of a group G is the simple digraph with vertex set G in which $$x\rightarrow y$$ if y is a power of x, and the power graph is the underlying simple graph $$\mathcal {G}( G)$$ . In this paper, three versions of the definition of the power graph are discussed, and it is proved that the power graph by any of the three versions of the definition determines the other two up to isomorphism. It is also proved that if G is a torsion-free group of nilpotency class 2 and if H is a group such that $$\mathcal {G}( H)\cong \mathcal {G}( G)$$ , then G and H have isomorphic directed power graphs, which was an open problem proposed by Cameron, Guerra and Jurina [9].

An $L(h_1, h_2, \ldots, h_l)$-labelling of a graph $G$ is a mapping $\phi: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that for $1\le i\le l$ and each pair of vertices $u, v$ of $G$ at distance $i$, we have $|\phi(u) - \phi(v)| \geq h_i$. The span of $\phi$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $\phi$, and $\lambda_{h_1, h_2, \ldots, h_l}(G)$ is defined as the minimum span over all $L(h_1, h_2, \ldots, h_l)$-labellings of $G$. In this paper we study $\lambda_{h, 1, \ldots, 1}$ for Cartesian products of graphs, where $(h, 1, \ldots, 1)$ is an $l$-tuple with $l \ge 3$. We prove that, under certain natural conditions, the value of this and three related invariants on a graph $H$ which is the Cartesian product of $l$ graphs attain a common lower bound. In particular, the chromatic number of the $l$-th power of $H$ equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of $H$ which contain a certain subgraph of $H$. All these results apply in particular to the class of Hamming graphs: if $q_1\ge \cdots \ge q_d\ge 2$ and $3\le l\le d$ then the Hamming graph $H=H_{q_1,q_2,\ldots ,q_d}$ satisfies $\lambda_{q_l,1,\ldots,1}(H) = q_1q_2\ldots q_l-1$ whenever $q_1q_2\ldots q_{l-1}>3(q_{l-1}+1)q_l\ldots q_d$. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes., Comment: Final version published in Discrete Applied Mathematics

In this paper we give sublinear-time distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be listed in sublinear time, O(n^{5/6+o(1)}) rounds and O(n^{21/22+o(1)}) rounds, respectively. Prior to our work, it was not known whether it was possible to even check if the network contains a 4-clique or a 5-clique in sublinear time. For even-length cycles, C_{2k}, we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from O~(n^{5/6}) to O~(n^{3/4}) rounds. We also show two obstacles on proving lower bounds for C_{2k}-freeness: First, we use the new connection to extremal combinatorics to show that the current lower bound of Omega~(sqrt{n}) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant delta in (0,1/2) such that for any k, a Omega(n^{1/2+delta}) lower bound on C_{2k}-freeness implies new lower bounds in circuit complexity. For general subgraphs, it was shown in [Orr Fischer et al., 2018] that for any fixed k, there exists a subgraph H of size k such that H-freeness requires Omega~(n^{2-Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in O(n^{2 - Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].

The irregularity strength of a graph $G$, $s(G)$, is the least $k$ admitting a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of $G$ via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant $C$ such that $s(G)\leq \frac{n}{d}+C$ for each $d$-regular graph $G$ with $n$ vertices and $d\geq 2$ (while a straightforward counting argument yields $s(G)\geq \frac{n+d-1}{d}$). The best known results towards this imply that $s(G)\leq 6\lceil\frac{n}{d}\rceil$ for every $d$-regular graph $G$ with $n$ vertices and $d\geq 2$, while $s(G)\leq (4+o(1))\frac{n}{d}+4$ if $d\geq n^{0.5}\ln n$. We show that the conjecture of Faudree and Lehel holds asymptotically in the cases when $d$ is neither very small nor very close to $n$. We in particular prove that for large enough $n$ and $d\in [\ln^8n,\frac{n}{\ln^3 n}]$, $s(G)\leq \frac{n}{d}(1+\frac{8}{\ln n})$, and thereby we show that $s(G) = \frac{n}{d}(1+o(1))$ then. We moreover prove the latter to hold already when $d\in [\ln^{1+\varepsilon}n,\frac{n}{\ln^\varepsilon n}]$ where $\varepsilon$ is an arbitrary positive constant., 14 pages

We study the three-dimensional stable matching problem with cyclic preferences. This model involves three types of agents, with an equal number of agents of each type. The types form a cyclic order such that each agent has a complete preference list over the agents of the next type. We consider the open problem of the existence of three-dimensional matchings in which no triple of agents prefer each other to their partners. Such matchings are said to be weakly stable. We show that contrary to published conjectures, weakly stable three-dimensional matchings need not exist. Furthermore, we show that it is NP-complete to determine whether a weakly stable three-dimensional matchings exists. We achieve this by reducing from the variant of the problem where preference lists are allowed to be incomplete. Our results can be generalized to the $k$-dimensional stable matching problem with cyclic preferences for $k \geq 3$.

While presenting a combinatorial point of view to the class of equistable graphs, Miklavic and Milanic pointed out the inclusions among the classes of equistable, general partition and triangle graphs. Orlin conjectured that the first two classes were equivalent, but in 2014, Milanic and Trotignon showed that the three classes are all distinct, leading to the following hierarchy: general partition graphs ⊂ equistable graphs ⊂ triangle graphs. In this paper, we solve an open problem from Anbeek et al. (1997) by showing that all the above classes are equivalent when restricted to planar graphs. Additionally, we present short proofs on some structural properties of the general partition, equistable and triangle classes. In particular, we show that the general partition and triangle classes are both closed under the operations of substitution, induction and contraction of modules which allow us to recover several results in the literature.

We introduce a high-dimensional analogue of the Kirchhoff index which is also known as total effective resistance. This analogue, which we call the simplicial Kirchhoff index K f ( X ) , is defined to be the sum of the simplicial effective resistances of all ( d + 1 ) -subsets of the vertex set of a simplicial complex X of dimension d. This definition generalizes the Kirchoff index of a graph G defined as the sum of the effective resistance between all pairs of vertices of G. For a d-dimensional simplicial complex X with n vertices, we give formulas for the simplicial Kirchhoff index in terms of the pseudoinverse of the Laplacian L X in dimension d − 1 and its eigenvalues: K f ( X ) = n ⋅ tr L X + = n ⋅ ∑ λ ∈ Λ + 1 λ , where L X + is the pseudoinverse of L X , and Λ + is the multi-set of non-zero eigenvalues of L X . Using this formula, we obtain an inequality for a high-dimensional analogue of algebraic connectivity and Kirchhoff index, and propose these quantities as measures of robustness of simplicial complexes. In addition, we derive its integral formula and relate this index to a simplicial dynamical system. We present an open problem for a combinatorial proof of our formula by relating the combinatorial interpretation of R σ to rooted forests in higher dimensions.

We initiate a study, when $F$ is a general APN function, of the Boolean function $\gamma _{F}$ related to the differential spectrum of $F$ (and which is known to be bent if and only if $F$ is almost bent). We first list many open questions about it. We study its algebraic normal form and its bivariate representation. We characterize its linear structures and specify nonexistence cases; we show, for $n$ even, their relation with the bent components of $F$ . We pose three related open problems. We characterize further in terms of $\gamma _{F}$ the fact that a component function of $F$ is bent and study if the number of bent components can be optimal. We consider in particular two classes, one of which is that of APN power functions. We study more deeply the relation between the Walsh transform of $\gamma _{F}$ and the Walsh transform of $F$ . By applying the Titsworth relation to the Walsh transform $W_{\gamma _{F}}$ , we deduce a new relation satisfied by $W_{F}^{2}$ , which is as simple as Chabaud-Vaudenay’s characterization by the fourth moment of the Walsh transform (which is in fact a particular case of the new relation), and provides more information. From this new relation, we deduce, for a sub-class of APN functions, a lower bound on the nonlinearity, which is significantly stronger than $nl(F)>0$ (the only general known bound). This sub-class of APN functions includes all known APN functions. The question (which is another open problem that we state) arises whether this sub-class equals that of all APN functions, but our bound provides at least a beginning of explanation why all known APN functions have non-weak nonlinearity. We finally show how the nonlinearities of $\gamma _{F}$ and $F$ are related by a simple formula; this leads to a last open problem.

The n -vertex unicyclic graphs with extreme values of arithmetic–geometric index or AG index are determined for all values of n . The case regarding the extremal values of the AG index in the class of bicyclic graphs has been stated as open problem.

An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock [DM 1991 and 1992] proved that detecting an even (respectively, odd) hole containing a given vertex is NP-complete. Conforti, Chornu\'ejols, Kappor, and Vu\v{s}kovi\'{c} [FOCS 1997] gave the first known polynomial-time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour [JGT 2005] estimated that Conforti et al.'s algorithm runs in $O(n^{40})$ time on an $n$-vertex graph and reduced the required time to $O(n^{31})$. Subsequently, da~Silva and Vu\v{s}kovi\'{c}~[JCTB 2013], Chang and Lu [JCTB 2017], and Lai, Lu, and Thorup [STOC 2020] improved the time to $O(n^{19})$, $O(n^{11})$, and $O(n^9)$, respectively. The tractability of determining whether a graph contains odd holes has been open for decades until the algorithm of Chudnovsky, Scott, Seymour, and Spirkl [JACM 2020] that runs in $O(n^9)$ time, which Lai et al. also reduced to $O(n^8)$. By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour [Combinatorica 2020 to appear] (respectively, [arXiv 2020]) ensured the tractability of finding a long (respectively, shortest) odd hole. They also ensured the NP-hardness of finding a longest odd hole, whose reduction also works for finding a longest even hole. Recently, Cook and Seymour ensured the tractability of finding a long even hole. An intriguing missing piece is the tractability of finding a shortest even hole, left open for at least 15 years by, e.g., Chudnovsky et al. [JGT 2005] and Johnson [TALG 2005]. We resolve this long-standing open problem by giving the first known polynomial-time algorithm, running in $O(n^{31})$ time, for finding a shortest even hole in an $n$-vertex graph that contains even holes., Comment: 8 pages, 1 figure

In 1749, Leonhard Euler solved a longstanding open problem in number theory, proving Fermat’s 1640 conjecture that any prime number of the form 4m+1 can be written as the sum of two squares. This a...

In the rank modulation scheme for flash memories, permutation codes have been studied. In this paper, we study perfect permutation codes in $$S_n$$ , the set of all permutations on n elements, under the Kendall $$\tau $$ -metric. We answer one open problem proposed by Buzaglo and Etzion. That is, proving the nonexistence of perfect codes in $$S_n$$ , under the Kendall $$\tau $$ -metric, for more values of n. Specifically, we present the polynomial representation of the size of a ball in $$S_n$$ under the Kendall $$\tau $$ -metric for some radius r, and obtain some sufficient conditions of the nonexistence of perfect permutation codes. Further, we prove that there does not exist a perfect t-error-correcting code in $$S_n$$ under the Kendall $$\tau $$ -metric for some n and $$t=2,3,4,5,~\text {or}~\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) $$ .

It is known that the Hurwitz zeta-function $$\zeta(s,\alpha)$$ with transcendental or rational parameter $$\alpha$$ has a discrete universality property; i.e., the shifts $$\zeta(s+ikh,\alpha)$$ , $$k\in\mathbb N_0$$ , $$h> 0$$ , approximate a wide class of analytic functions. The case of algebraic irrational $$\alpha$$ is a complicated open problem. In the paper, some progress in this problem is achieved. It is proved that there exists a nonempty closed set $$F_{\alpha,h}$$ of analytic functions such that the functions in $$F_{\alpha,h}$$ are approximated by the above shifts. Also, the case of certain compositions $$\Phi(\zeta(s,\alpha))$$ is discussed.

The Graceful Tree Conjecture stated by Rosa in the mid 1960s says that every tree can be gracefully labelled. It is one of the best known open problems in Graph Theory. The conjecture has caused a great interest in the study of gracefulness of simple graphs and has led to many new contributions to the list of graceful graphs. However, it has to be acknowledged that not much is known about the structure of graceful graphs after 55 years. Our paper adds an infinite family of classes of graceful graphs to the list of known simple graceful graphs. We introduce classes of \(k\)-enriched fan graphs \(kF_n\) for all integers \(k, n\ge 2\) and we prove that these graphs are graceful. Moreover, we provide characterizations of the \(k\)-enriched fan graphs \(kF_n\) among all simple graphs via Sheppard's labelling sequences introduced in the 1970s, as well as via labelling relations and graph chessboards. These last approaches are new tools for the study of graceful graphs introduced by Haviar and Ivaska in 2015. The labelling relations are closely related to Sheppard's labelling sequences while the graph chessboards provide a nice visualization of graceful labellings. We close our paper with an open problem concerning another infinite family of extended fan graphs.

Characterization of potentially stable sign pattern matrices has been a long-standing open problem. In this paper, we give some sufficient conditions for tree sign pattern matrices with all edges negative to allow a properly signed nest. We also characterize potentially stable star and path sign pattern matrices with all edges negative. We give a conjecture on characterizing potentially stable tree sign pattern matrices with all edges negative in terms of allowing a properly signed nest which is verified to be true for sign pattern matrices up to order 6. Finally, we characterize all 5-by-5 spectrally arbitrary tree sign pattern matrices with all edges negative.

Bounded and compact differences of two composition operators acting from the weighted Bergman space $$A^p_\omega $$ A ω p to the Lebesgue space $$L^q_\nu $$ L ν q , where $$0 0 < q < p < ∞ and $$\omega $$ ω belongs to the class "Equation missing" of radial weights satisfying two-sided doubling conditions, are characterized. On the way to the proofs a new description of q-Carleson measures for $$A^p_\omega $$ A ω p , with $$p>q$$ p > q and "Equation missing", involving pseudohyperbolic discs is established. This last-mentioned result generalizes the well-known characterization of q-Carleson measures for the classical weighted Bergman space $$A^p_\alpha $$ A α p with $$-1 - 1 < α < ∞ to the setting of doubling weights. The case "Equation missing" is also briefly discussed and an open problem concerning this case is posed.

We would like to congratulate the authors for their contribution to this longstanding open problem in mathematical statistics. Their clever implementation of MCMC to obtain simplex-based Dempster–S...

In this paper, we study an inverse eigenvalue problem, referred to as the minimax inverse eigenvalue problem, of constructing matrices whose graph is a special type of tree called a generalized star of depth 2. A scheme of labelling the vertices of such a tree is introduced in order to express the corresponding matrices in a number of special forms. We then solve the minimax inverse eigenvalue problem of constructing such matrices from given eigen data consisting of the minimal and maximal eigenvalues of each of the leading principal submatrices of the required matrices. We pose an open problem of solving the minimax inverse eigenvalue problem for matrices described by arbitrary trees.

In this work, we present necessary and sufficient conditions for oscillation of all solutions of a second-order functional differential equation of type $$ (r(t)(z'(t))^\gamma )' +\sum _{i=1}^m q_i(t)x^{\alpha _i}(\sigma _i(t))=0, \quad t\geq t_0, $$ where $z(t)=x(t)+p(t)x(\tau (t))$. Under the assumption $\int ^{\infty }(r(\eta ))^{-1/\gamma } {\rm d}\eta =\infty $, we consider two cases when $\gamma >\alpha _i$ and $\gamma

The characterization of rigid graphs in R d is known only in the low dimensional cases ( d = 1 , 2 ) and is a major open problem in higher dimensions. In this note we consider the other extreme case when d is close to n , the number of vertices of the graph. It turns out that there is a fairly simple characterization as long as n − d is at most four. We also characterize globally rigid graphs in this range.

We study the decidability of k-provability in $$\hbox {PA}$$ PA —the relation ‘being provable in $$\hbox {PA}$$ PA with at most k steps’—and the decidability of the proof-skeleton problem—the problem of deciding if a given formula has a proof that has a given skeleton (the list of axioms and rules that were used). The decidability of k-provability for the usual Hilbert-style formalisation of $$\hbox {PA}$$ PA is still an open problem, but it is known that the proof-skeleton problem is undecidable for that theory. Using new methods, we present a characterisation of some numbers k for which k-provability is decidable, and we present a characterisation of some proof-skeletons for which one can decide whether a formula has a proof whose skeleton is the considered one. These characterisations are natural and parameterised by unification algorithms.

Let Q n denote the space of all n × n skew-symmetric matrices over the complex field C and T : Q n → Q n be a map satisfying the condition d χ ′ ( T ( A ) + z T ( B ) ) = d χ ( A + z B ) for all matrices A , B ∈ Q n and all constants z ∈ C . Here χ and χ ′ are irreducible characters of the permutation group S n and d χ ( C ) denotes the immanant of the matrix C associated with the character χ. Let P n be the set of permutations with no cycles of odd length in the decomposition into the product of independent cycles. The main goal of this paper is twofold. The first one is to show that there are no maps T satisfying the above conditions if n ≥ 6 is even and χ and χ ′ are not proportional on P n . The second is to characterize such maps T if χ and χ ′ are proportional on P n . In particular, we prove that T is bijective and linear. Observe that the general problem of the characterization for bijective linear maps on Q n , that convert one immanant into another, remained an open problem with the exception for determinant and permanent. Our results include all known characterizations for immanant preserving and converting maps and provide the complete solution of this problem.

Levenshtein introduced the problem of constructing k -deletion correcting codes in 1966, proved that the optimal redundancy of those codes is $ {O}(k~\log ~{N})$ for constant k, and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy k -deletion correcting codes remained open. Our key contribution is a major step towards a complete solution to this longstanding open problem for constant k . We present a k -deletion correcting code that has redundancy $8 {k}\log~{N} + {o}(\log~{N})$ when $ {k}= {o}(\sqrt {\log \log~{N}})$ and encoding/decoding algorithms of complexity $ {O}({N}^{2 {k}+1})$ .

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. Feng et al. determined the maximum number of spanning trees in the class of connected graphs with n vertices and matching number $$\beta $$ for $$2\le \beta \le n/3$$ and $$\beta =\lfloor n/2\rfloor $$ . They also pointed out that it is still an open problem to the case of $$n/3

The Lyapunov rank of a cone is the number of independent equations obtainable from an analogue of the complementary slackness condition in cone programming problems, and more equations are generally thought to be better. Bounding the Lyapunov rank of a proper cone in $$ \mathbb {R}^{n}$$ from above has been an open problem. Gowda and Tao gave an upper bound of $$n^{2} - n$$ that was later improved by Orlitzky and Gowda to $$ \left( {n-1}\right) ^{2}$$ . We settle the matter and show that the Lyapunov rank of $$ \left( {n^{2} - n}\right) /2 + 1$$ corresponding to the Lorentz cone is maximal.

The pure entangled state is of vital importance in the field of quantum information. The process of asymptotically extracting pure entangled states from many copies of mixed states via local operations and classical communication is called entanglement distillation. The entanglement distillability problem, which is a long-standing open problem, asks whether such process exists. The 2-copy undistillability of 4 × 4 Werner states has been reduced to the validity of a conjecture for the following matrix inequality with d = 4 sup X ∈ X d ⁡ σ 1 2 ( X ) + σ 2 2 ( X ) ⩽ 3 d − 4 d 2 , where σ 1 ( X ) and σ 2 ( X ) are the largest two singular values of X, X d is the set of all matrices X = A ⊗ I + I ⊗ B with A , B ∈ C d × d ( d ⩾ 4 ) , Tr ( A ) = Tr ( B ) = 0 and ‖ A ‖ F 2 + ‖ B ‖ F 2 = 1 / d . The latest progress, made by Pankowski et al. (2010) [21] , shows that this conjecture holds when both matrices A and B are normal. In this paper, we prove that the conjecture holds when one of matrices A and B is normal and the other one is arbitrary via optimization techniques. Our work makes solid progress towards this conjecture and thus the distillability problem.

The study of the degree sequences of k-uniform hypergraphs, usually called k-sequences, has been a longstanding open problem for the case of k > 2 , and the corresponding decision version was proved to be NP-complete recently in 2018 [15] . The problem can be formalized as follows: Given a non decreasing sequence of positive integers π = ( d 1 , d 2 , … , d n ) , can π be the degree sequence of a k-uniform simple hypergraph? If the answer is positive, then the sequence π is said to be k-graphic. For k = 2 , that is for simple graphs, Erdos and Gallai [16] provided a characterization of the sequences that are 2-graphic (or simply, graphic). From this characterization, a polynomial time algorithm can be designed to reconstruct the incidence matrix of a graph having a given π as degree sequence (provided this graph exists). Due to the result of [15] and assuming P ≠ N P , an efficiently computable characterization like the one for k = 2 does not even exist for the case of 3-uniform hypergraphs. Necessary or sufficient conditions for π to be k-graphic ( k ≥ 3 ) can be found in the literature. In this paper we prove some different new conditions: first we provide sufficient and also necessary conditions for the case of k-uniform and (almost) regular hypergraphs. Then, for k = 3 , we prove sufficient conditions in the case where π can be decomposed into π ′ and π ″ , and π ′ is graphic. Most of the results are obtained by borrowing tools from discrete tomography, a current research field on discrete mathematics.

In this article, we consider the (double) minimization problem min ⁡ { P ⁢ ( E ; Ω ) + λ ⁢ W p ⁢ ( E , F ) : E ⊆ Ω , F ⊆ R d , | E ∩ F | = 0 , | E | = | F | = 1 } , \min\{P(E;\Omega)+\lambda W_{p}(E,F):E\subseteq\Omega,\,F\subseteq\mathbb{R}^{d},\,\lvert E\cap F\rvert=0,\,\lvert E\rvert=\lvert F\rvert=1\}, where λ ⩾ 0 \lambda\geqslant 0 , p ⩾ 1 p\geqslant 1 , Ω is a (possibly unbounded) domain in R d \mathbb{R}^{d} , P ⁢ ( E ; Ω ) P(E;\Omega) denotes the relative perimeter of 𝐸 in Ω and W p W_{p} denotes the 𝑝-Wasserstein distance. When Ω is unbounded and d ⩾ 3 d\geqslant 3 , it is an open problem proposed by Buttazzo, Carlier and Laborde in the paper On the Wasserstein distance between mutually singular measures. We prove the existence of minimizers to this problem when the dimension d ⩾ 1 d\geqslant 1 , 1 p + 2 d > 1 \frac{1}{p}+\frac{2}{d}>1 , Ω = R d \Omega=\mathbb{R}^{d} and 𝜆 is sufficiently small.

In the Cluster Deletion problem the goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on ( $$P_5$$ -free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of a polynomial-time algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of $$P_5$$ -free chordal graphs. Although the later result arises from the already-known reduction for $$P_5$$ -free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs.

The group testing problem consists of determining a small set of defective items from a larger set of items based on tests on groups of items, and is relevant in applications such as medical testing, communication protocols, pattern matching, and many more. While rigorous group testing algorithms have long been known with runtime at least linear in the number of items, a recent line of works has sought to reduce the runtime to ${\mathrm{ poly}}({k} \log {n})$ , where n is the number of items and k is the number of defectives. In this paper, we present such an algorithm for non-adaptive group testing termed bit mixing coding (BMC), which builds on techniques that encode item indices in the test matrix, while incorporating novel ideas based on erasure-correction coding. We show that BMC achieves asymptotically vanishing error probability with ${O}({k} \log {n})$ tests and ${O}({k}^{2} \cdot \log {k} \cdot \log {n})$ runtime, in the limit as ${n} \to \infty $ (with k having an arbitrary dependence on n). This closes an open problem of simultaneously achieving ${\mathrm{ poly}}({k} \log {n})$ decoding time using ${O}({k} \log {n})$ tests without any assumptions on k. In addition, we show that the same scaling laws can be attained in a commonly-considered noisy setting, in which each test outcome is flipped with constant probability.

Let $$f$$ be a transcendental meromorphic function such that $$N_{1)}(r,0;f')+N(r,\infty ;f)=S(r,f)$$ . Let $$k\in \mathbb {N}\setminus \{1\}$$ and $$n\in \mathbb {N}$$ such that $$n\ge k+1$$ . If $$f^{n}$$ and $$(f^{n})^{(k)}$$ share 1 IM, then $$f^{n}\equiv (f^{n})^{(k)}$$ and f assumes the form $$f(z)=ce^{\frac{\lambda }{n}z}$$ , where $$c\in \mathbb {C}\setminus \{0\}$$ and $$\lambda ^{k}=1$$ .

The indicated coloring game is played on a simple graph G by two players, with a fixed set C of colors. In each round of the game Ann indicates an uncolored vertex, and Ben colors it using a color from C , obeying just the proper coloring rule. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent this. The minimum cardinality of the set of colors C for which Ann has a winning strategy is called the indicated chromatic number, χ i ( G ) , of a graph G . In this paper, we prove that the indicated chromatic number of the Cartesian product G □ K n , m is equal to 3 if χ i ( G ) = 3 . We also prove that χ i ( G □ T ) = χ ( G ) , where G is a block graph and T is a tree. Indicated colorings in some other classes of Cartesian products of graphs are also studied. The investigations lead us to propose a Sabidussi-type equality as an open problem.

The Fixed-Tree BMEP (FT-BMEP) is a special case of the Balanced Minimum Evolution Problem (BMEP) that consists of finding the assignment of a set of n taxa to the n leaves of a given unrooted binary tree so as to minimize the BMEP objective function. Deciding the computational complexity of the FT-BMEP has been an open problem for almost a decade. Here, we show that a few modifications to Fiorini and Joret’s proof of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {NP}$$\end{document}NP-hardness of the BMEP suffice to prove the general \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {NP}$$\end{document}NP-hardness of the FT-BMEP as well as its strong inapproximability.

A k -cone c -cyclic graph is the join of the complete graph K k and a c -cyclic graph (if k = 0 , we get the usual connected graph). A k -apex tree (resp., k -apex unicyclic graph) is defined as a connected graph G with a k -subset V k ⊆ V ( G ) such that G − V k is a tree (resp., unicylic graph), but G − X is not a tree (resp., unicylic graph) for any X ⊆ V ( G ) with | X | k . In this paper, we extend those extremal results and majorization theorems concerning connected graphs of Liu et al. (2019) to k -cone c -cyclic graphs. We also use a unified method to characterize the extremal maximum and minimum results of many topological indices in the class of k -apex trees and k -apex unicyclic graphs, respectively. The later results extend the main results of Javaid et al. (2019); Liu et al. (2020) and partially answer the open problem of Javaid et al. (2019). Except for the new majorization theorem, some new techniques are also established to deal with the minimum extremal results of this paper.

Galled trees are studied as a recombination model in population genetics. This class of phylogenetic networks is generalized into tree-child and galled network classes by relaxing a structural condition imposed on galled trees. We provide a solution to an open problem that is how to count and enumerate tree-child networks with fixed number of leaves and reticulations. Explicit counting formulas are also given for galled trees through their relationship to ordered trees and phylogenetic networks in which the child of each reticulation is a leaf.

We revisit the approximate Voronoi cells approach for solving the closest vector problem with preprocessing (CVPP) on high-dimensional lattices, and settle the open problem of Doulgerakis-Laarhoven-De Weger [PQCrypto, 2019] of determining exact asymptotics on the volume of these Voronoi cells under the Gaussian heuristic. As a result, we obtain improved upper bounds on the time complexity of the randomized iterative slicer when using less than $2^{0.076d + o(d)}$ memory, and we show how to obtain time-memory trade-offs even when using less than $2^{0.048d + o(d)}$ memory. We also settle the open problem of obtaining a continuous trade-off between the size of the advice and the query time complexity, as the time complexity with subexponential advice in our approach scales as $d^{d/2 + o(d)}$, matching worst-case enumeration bounds, and achieving the same asymptotic scaling as average-case enumeration algorithms for the closest vector problem., Comment: 18 pages, 1 figure

We generalize the example of linear set presented by the last two authors in “Vertex properties of maximum scattered linear sets of PG (1, q n ) " (2019) to a more general family, proving that such linear sets are maximum scattered when q is odd and, apart from a special case, they are new. This solves an open problem posed in “Vertex properties of maximum scattered linear sets of PG (1, q n ) " (2019). As a consequence of Sheekey’s results in “A new family of linear maximum rank distance codes" (2016), this family yields to new MRD-codes with parameters (6, 6, q ; 5) .

Having a convex cone K in an infinite-dimensional real linear space X, Adan and Novo stated (in J Optim Theory Appl 121:515–540, 2004) that the relative algebraic interior of K is nonempty if and only if the relative algebraic interior of the positive dual cone of K is nonempty. In this paper, we show that the direct implication is not true even if K is closed with respect to the finest locally convex topology $$\tau _{c}$$ on X, while the reverse implication is not true if K is not $$\tau _{c}$$ -closed. However, in the main result of this paper, we prove that the latter implication is true if the algebraic interior of the positive dual cone of K is nonempty; the general case remains an open problem. As a by-product, a result about separation of cones is obtained that improves Theorem 2.2 of the work mentioned above.

Given a sequence of independent standard Gaussian variables (Zn), the classical Pisier algebra P is the class of all continuous functions f on the unit circle T such that for each t ∈ 𝕋, the random Fourier series $$ {\sum}_{n\in \mathrm{\mathbb{Z}}}{Z}_n\hat{f}(n)\times \exp \left(2\pi \mathrm{i} nt\right) $$ converges in L2 and the corresponding sums constitute a Gaussian process that admits a continuous version. It was constructed by Pisier in 1979 to answer a long-standing question raised by Katznelson. In this paper, we consider the general random Fourier series $$ {\sum}_{n\in \mathrm{\mathbb{Z}}}{Z}_n\hat{f}(n)\times \exp \left(2\pi \mathrm{i} nt\right) $$ where ξ = (ξn) is a discrete Gaussian process of standard Gaussian random variables but with the restriction of independence relaxed and study the corresponding class P(ξ) of continuous functions f on 𝕋. We obtain sufficient conditions (based on some spectral properties of the covariance matrix of (ξn)) for each of the relations 𝒫 ⊂ (ξ), 𝒫(ξ) ⊂ 𝒫, and 𝒫 = 𝒫(ξ). We illustrate these results by the classical fractional Gaussian noise. Whether in general (ξ) is also a Banach algebra is an open problem.

It has been known that sharp Sobolev embeddings into weak Lebesgue spaces are non-compact but the question of whether the measure of non-compactness of such an embedding equals to its operator norm constituted a well-known open problem. The existing theory suggested an argument that would possibly solve the problem should the target norms be disjointly superadditive, but the question of disjoint superadditivity of spaces $L^{p,\infty}$ has been open, too. In this paper, we solve both these problems. We first show that weak Lebesgue spaces are never disjointly superadditive, so the suggested technique is ruled out. But then we show that, perhaps somewhat surprisingly, the measure of non-compactness of a sharp Sobolev embedding coincides with the embedding norm nevertheless, at least as long as $p, 18 pages

The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We show that the switch chain for sampling simple undirected graphs with a given degree sequence is rapidly mixing when the degree sequence is so-called strongly stable. Strong stability is satisfied by all degree sequences for which the switch chain was known to be rapidly mixing based on Sinclair's multicommodity flow method up until a recent manuscript of Erdős and coworkers in 2019. Our approach relies on an embedding argument, involving a Markov chain defined by Jerrum and Sinclair in 1990. This results in a much shorter proof that unifies (almost) all the rapid mixing results for the switch chain in the literature, and extends them up to sharp characterizations of P-stable degree sequences. In particular, our work resolves an open problem posed by Greenhill and Sfragara in 2017.

The t-admissibility problem aims to decide whether a graph G has a spanning tree T in which the distance between any two adjacent vertices of G is at most t. Regarding its optimization version, the smallest t for which G is t-admissible is the stretch index of G, denoted by σ T ( G ) . The problem of deciding whether σ T ( G ) ≤ t , t ≥ 4 is NP -complete and polynomial-time solvable for t = 2 . However, deciding if t = 3 is an open problem. We determine 3-admissible graph classes by studying graphs with few P 4 's, and we partially classify the P vs NP -complete dichotomy of the t-admissibility problem for ( k , l ) -graphs. These graph classes generalize some others in which the computational complexity of the t-admissibility problem was already determined. Moreover, we determine the stretch index for cycle-power graphs and for ( 2 , 1 ) -chordal graphs, which are subclasses of ( k , l ) -graphs and the t-admissibility problem is NP -complete.

Let α be a real number with 0 ≤ α 1 , G be a uniform hypergraph, and A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) , where D ( G ) and A ( G ) are the diagonal degree tensor and the adjacency tensor of G , respectively. The spectral radius of A α ( G ) is called the α -spectral radius of G . In this paper, some properties for the α -spectral radius of connected k -uniform hypergraphs are investigated, the unique k -uniform supertree with the largest α -spectral radius among all k -uniform supertrees with a given degree sequence is characterized, and the majorization theorem for k -uniform supertrees is obtained. By applying the majorization theorem, we determine the k -uniform supertrees obtaining the three largest α -spectral radius among all k -uniform supertrees with n vertices, give a new proof ordering the eight largest spectral radius among all k -uniform supertrees with n vertices, propose an open problem for further research, and characterize the unique k -uniform supertree with the largest α -spectral radius among all k -uniform supertrees with given different parameters, e.g., the maximum degree △ , or the number of pendent vertices.

Let G be a simple graph of order n . The energy of a graph G , denoted by E ( G ) , is defined as the sum of the absolute values of all eigenvalues of G . The Laplacian energy of the graph G is defined as L E = L E ( G ) = ∑ i = 1 n μ i − d ¯ , where μ 1 , μ 2 , … , μ n − 1 , μ n = 0 are the Laplacian eigenvalues, and d ¯ is the average degree of graph G . In this paper we present some lower and upper bounds on E ( G ) of chain graph G . From this we prove that the star gives the minimal energy of connected chain graphs of order n . We present a lower bound on L E ( G ) of chain graphs G in terms of order n , and characterize the extremal graphs. Moreover, we obtain the maximal Laplacian energy among all connected chain graphs of order n with n edges. Finally, we propose an open problem on Laplacian energy of chain graphs.

We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set. For p ≥ 3 and m ≥ 2, the classical Ramsey number R(p; m) is the smallest positive integer n such that any m-coloring of the edges of Kn, the complete graph on n vertices, contains a monochromatic Kp. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p; m) ≤ 2cm, where c = c(p). We prove that this is true if each color class is defined semi-algebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemeredi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdős and Shelah.

We consider the problem of $T$ -Private Information Retrieval with private side information (TPIR-PSI). In this problem, $N$ replicated databases store $K$ independent messages, and a user, equipped with a local cache that holds $M$ messages as side information, wishes to retrieve one of the other $K-M$ messages. The desired message index and the side information must remain jointly private even if any $T$ of the $N$ databases collude. We show that the capacity of TPIR-PSI is $\left ({1+\frac {T}{N}+\cdots +\left ({\frac {T}{N}}\right)^{K-M-1}}\right)^{-1}$ . As a special case obtained by setting $T=1$ , this result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We also consider the problem of symmetric-TPIR with private side information (STPIR-PSI), where the answers from all $N$ databases reveal no information about any other message besides the desired message. We show that the capacity of STPIR-PSI is $1-\frac {T}{N}$ if the databases have access to common randomness (not available to the user) that is independent of the messages, in an amount that is at least $\frac {T}{N-T}$ bits per desired message bit. Otherwise, the capacity of STPIR-PSI is zero.

Every word in a free group $F$ induces a probability measure on every finite group in a natural manner. It is an open problem whether two words that induce the same measure on every finite group, necessarily belong to the same orbit of $\mathrm{Aut}F$. A special case of this problem, when one of the words is the primitive word $x$, was settled positively by the third author and Parzanchevski [arXiv:1202.3269]. Here we extend this result to the case where one of the words is $x^d$ or $\left[x,y\right]^{d}$ for an arbitrary $d\in\mathbb{Z}$., Comment: 16 pages, minor changes, journal version