Search

In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set $${\mathcal {S}}$$ and $$k \le n$$ with respect to $$\mu $$ -similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$ with $$ \mid C \mid = k$$ and then separate $${\mathcal {S}}$$ into k clusters according to C, such that the sum of $$\mu $$ -similar Bregman divergence from each point in $${\mathcal {S}}$$ to its nearest center is minimized. We propose a $$\mu $$ -similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy $$\mu $$ -similar Bregman k-means++ (noisy $$\mu $$ -BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between $$1-\varepsilon _1$$ and $$1+ \varepsilon _2$$ for $$\varepsilon _1 \in [0,1)$$ and $$\varepsilon _2 \ge 0$$ , and obtain an approximation ratio of $$O(\log ^2 k)$$ in expectation.

In their study of the equivariant K-theory of the generalized flag varieties G/P, where G is a complex semisimple Lie group, and P is a parabolic subgroup of G, Lenart and Postnikov introduced a combinatorial tool, called the alcove path model. It provides a model for the highest weight crystals with dominant integral highest weights, generalizing the model by semistandard Young tableaux. In this paper, we prove a simple and explicit formula describing the crystal isomorphism between the alcove path model and the Gelfand–Tsetlin pattern model for type A.

In 2011, Nathanson proposed several questions on minimal complements in a group or a semigroup. The notion of minimal complements and being a minimal complement leads to the notion of co-minimal pairs which was considered in a prior work of the authors. In this article, we study which type of subsets in the integers and free abelian groups of higher rank can be a part of a co-minimal pair. We show that a majority of lacunary sequences have this property. From the conditions established, one can show that any infinite subset of any finitely generated abelian group has uncountably many subsets which is a part of a co-minimal pair. Further, the uncountable collection of sets can be chosen so that they satisfy certain algebraic properties.

The computationally hard problem of finite language decomposition is investigated. A finite language L is decomposable if there are two languages L1 and L2 such that L = L1L2. Otherwise, L is prime. The main contribution of the paper is an adaptive parallel algorithm for finding all decompositions L1L2 of L. The algorithm is based on an exhaustive search and incorporates several original methods for pruning the search space. Moreover, the algorithm is adaptive since it changes its behavior based on the runtime acquired data related to its performance. Comprehensive computational experiments on more than 4000 benchmark languages generated over alphabets of various sizes have been carried out. The experiments showed that by using the power of parallel computing the decompositions of languages containing more than 200000 words can be found. Decompositions of languages of that size have not been reported in the literature so far.

Due to their ubiquity and extensive applications, graph routing problems have been widely studied in the fields of operations research, computer science and engineering. An important example of a routing problem is the traveling salesman problem. In this paper, we consider two variants of the general cluster routing problem. In these variants, we are given a complete undirected graph $$G=(V,E)$$ with a metric cost function c and a partition $$V=C_{1}\cup C_{2}\cdots \cup C_{k}$$ of the vertex set. For a given subset $$V^{'}$$ of V and subset $$E^{'}$$ of E, the task is to find a walk T with minimum cost such that it visits each vertex in $$V^{\prime }$$ exactly once and covers each edge in $$E^{\prime }$$ at least once. Besides, for every $$i\in [k]$$ , all the vertices in $$T\cap C_i$$ are required to be visited consecutively in T. We design two combinatorial approximation algorithms with ratios 21/11 and 2.75 for the two variants, respectively; both ratios match the approximation ratios for the corresponding variants of the cluster traveling salesman problem, a special case of general cluster routing problem.

In strategic situations, agents base actions on knowledge and beliefs. This includes knowledge about others’ strategies and preferences over strategy profiles, but also about other external factors. Bernheim and Pearce in 1984 independently defined the game theoretic solution concept of rationalizability, which is built on the premise that rational agents will only take actions that are the best response to some situation that they consider possible. This accounts for other agents’ rationality as well, limiting the strategies to which a particular agent must respond, enabling further elimination until the strategies stabilize. We seek to generalize rationalizability to account not only for actions, but knowledge of the world as well. This will enable us to examine the interplay between action based and knowledge based rationality. We give an account of what it means for an action to be rational relative to a particular state of affairs, and in turn relative to a state of knowledge. We present a class of games, Epistemic Messaging Games (EMG), with a communication stage that clarifies the epistemic state among the players prior to the players’ actions. We use a history based model, which frames individual knowledge in terms of local projections of a global history. With this framework, we give an account of rationalizability for subclasses of EMG.

This paper studies Menon–Sury’s identity in a general case, i.e., the Menon–Sury’s identity involving Dirichlet characters in residually finite Dedekind domains. By using the filtration of the ring $${\mathfrak {D}}/{\mathfrak {n}}$$ and its unit group $$U({\mathfrak {D}}/{\mathfrak {n}})$$ , we explicitly compute the following two summations: $$\begin{aligned} \sum _{\begin{array}{c} a\in U({\mathfrak {D}}/{\mathfrak {n}}) \\ b_1, \ldots , b_r\in {\mathfrak {D}}/{\mathfrak {n}} \end{array}} N(\langle a-1,b_1, b_2, \ldots , b_r \rangle +{\mathfrak {n}})\chi (a) \end{aligned}$$ and $$\begin{aligned} \sum _{\begin{array}{c} a_{1},\ldots , a_{s}\in U({\mathfrak {D}}/{\mathfrak {n}}) \\ b_1, \ldots , b_r\in {\mathfrak {D}}/{\mathfrak {n}} \end{array}} N(\langle a_{1}-1,\ldots , a_{s}-1,b_1, b_2, \ldots , b_r \rangle +{\mathfrak {n}})\chi _{1}(a_1) \cdots \chi _{s}(a_s), \end{aligned}$$ where $${\mathfrak {D}}$$ is a residually finite Dedekind domain and $${\mathfrak {n}}$$ is a nonzero ideal of $${\mathfrak {D}}$$ , $$N({\mathfrak {n}})$$ is the cardinality of quotient ring $${\mathfrak {D}}/{\mathfrak {n}}$$ , $$\chi _{i}~(1\le i\le s)$$ are Dirichlet characters mod $${\mathfrak {n}}$$ with conductor $${\mathfrak {d}}_i$$ .

In the history of secret sharing schemes many constructions are based on geometric objects. In this paper we investigate generalizations of threshold schemes and related finite geometric structures. In particular, we analyse compartmented and hierarchical schemes, and deduce some more general results, especially bounds for special arcs and novel constructions for conjunctive 2-level and 3-level hierarchical schemes.

Let G be a 3-connected graph. An edge (a triangle) of G is said to be a 3-contractible edge (a 3-contractible triangle) if the contraction of it results in a 3-connected graph. We denote by $$E_{c}(G)$$ and $$\mathcal {T}_{c}(G)$$ the set of 3-contractible edges of G and the set of 3-contractible triangles of G, respectively. We prove that if $$|V(G)|\ge 7$$ , then $$|E_{c}(G)|+ \frac{15}{14}|\mathcal {T}_{c}(G)|\ge \frac{6}{7}|V(G)|.$$ We also determine the extremal graphs.

Quantum synchronizable codes (QSCs) are special quantum error-correcting codes that can correct the effects of both quantum noise on qubits and misalignment in block synchronization. In this paper, using the factorizations of cyclotomic polynomials ${{\varPhi }}_{p_{1}p_{2}}(x)$ , where p1 and p2 are distinct odd primes, we give a new method to construct QSCs whose synchronization capabilities can reach the best attainable tolerance against misalignment.

The problem, also known as the multiterminal cut problem, is defined on an edge-weighted graph with k distinct vertices called “terminals.” The goal is to remove a minimum weight collection of edges from the graph such that there is no path between any pair of terminals. The problem is APX-hard. Isolating cuts are minimum cuts which separate one terminal from the rest. The union of all the isolating cuts, except the largest, is a $$(2-2/k)$$ ( 2 - 2 / k ) -approximation to the optimal k-terminal cut. An instance of is $$\gamma $$ γ -stable if edges in the cut can be multiplied by up to $$\gamma $$ γ without changing the unique optimal solution. In this paper, we show that, in any $$(k-1)$$ ( k - 1 ) -stable instance of , the source sets of the isolating cuts are the source sets of the unique optimal solution to that instance. We conclude that the $$(2-2/k)$$ ( 2 - 2 / k ) -approximation algorithm returns the optimal solution on $$(k-1)$$ ( k - 1 ) -stable instances. Ours is the first result showing that this $$(2-2/k)$$ ( 2 - 2 / k ) -approximation is an exact optimization algorithm on a special class of graphs. We also show that our $$(k-1)$$ ( k - 1 ) -stability result is tight. We construct $$(k-1-\epsilon )$$ ( k - 1 - ϵ ) -stable instances of the problem which only have trivial isolating cuts: that is, the source set of the isolating cuts for each terminal is just the terminal itself. Thus, the $$(2-2/k)$$ ( 2 - 2 / k ) -approximation does not return an optimal solution.

Uniform interpolants have been largely studied in non-classical propositional logics since the nineties; a successive research line within the automated reasoning community investigated uniform quantifier-free interpolants (sometimes referred to as “covers”) in first-order theories. This further research line is motivated by the fact that uniform interpolants offer an effective solution to tackle quantifier elimination and symbol elimination problems, which are central in model checking infinite state systems. This was first pointed out in ESOP 2008 by Gulwani and Musuvathi, and then by the authors of the present contribution in the context of recent applications to the verification of data-aware processes. In this paper, we show how covers are strictly related to model completions, a well-known topic in model theory. We also investigate the computation of covers within the Superposition Calculus, by adopting a constrained version of the calculus and by defining appropriate settings and reduction strategies. In addition, we show that computing covers is computationally tractable for the fragment of the language used when tackling the verification of data-aware processes. This observation is confirmed by analyzing the preliminary results obtained using the mcmt tool to verify relevant examples of data-aware processes. These examples can be found in the last version of the tool distribution.

We study the reachability problem for queue automata and lossy queue automata. Concretely, we consider the set of queue contents which are forwards resp. backwards reachable from a given set of queue contents. Here, we prove the preservation of regularity if the queue automaton loops through some special sets of transformation sequences. This is a generalization of the results by Boigelot et al. and Abdulla et al. regarding queue automata looping through a single sequence of transformations. We also prove that our construction is possible in polynomial time.

We study the -hard graph problemCollapsed k-Corewhere, given an undirected graphGand integersb,x, andk, we are asked to removebvertices such that thek-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degreek, has size at mostx.Collapsed k-Corewas introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs.Collapsed k-Coreis a generalization ofr-Degenerate Vertex Deletion(which is known to be -hard for allr≥ 0) where, given an undirected graphGand integersbandr, we are asked to removebvertices such that the remaining graph isr-degenerate, that is, every its subgraph has minimum degree at mostr. We investigate the parameterized complexity ofCollapsed k-Corewith respect to the parametersb,x, andk, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity ofCollapsed k-Corefork≤ 2 andk≥ 3. For the latter case it is known that for allx≥ 0Collapsed k-Coreis -hard when parameterized byb. Fork≤ 2 we show thatCollapsed k-Coreis -hard when parameterized byband in when parameterized by (b+x). Furthermore, we outline thatCollapsed k-Coreis in when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.

We consider three types of set-systems that have interesting applications in algebraic combinatorics and representation theory: maximal collections of the so-called strongly, weakly, and chord separated subsets of a set $$[n]=\{1,2,\ldots ,n\}$$ . These collections are known to admit nice geometric interpretations; namely, they are, respectively, in bijection with rhombus tilings on the zonogon Z(n, 2), combined tilings on Z(n, 2), and fine zonotopal tilings (or “cubillages”) on the 3-dimensional zonotope Z(n, 3). We describe interrelations between these three types of set-systems in $$2^{[n]}$$ , working in terms of their geometric models. In particular, we characterize the sets of rhombus and combined tilings properly embeddable in a fixed 3-dimensional cubillage and give efficient methods of extending a given rhombus or combined tiling to a cubillage, etc.

This paper is devoted to studying the symmetric 2-adic complexity of sequences with optimal autocorrelation magnitude and period 8q, where q is a prime satisfying q ≡ 5 (mod 8). These sequences were constructed by interleaving technique from Ding-Helleseth-Martinsen sequences and almost perfect binary sequences. They were presented by Krengel and Ivanov in 2016 and have been proved to have high linear complexity. Our result shows that they also have high symmetric 2-adic complexity.

One way to study the Kronecker coefficients is to focus on the Kronecker cone, which is generated by the triples of partitions corresponding to non-zero Kronecker coefficients. In this article we are interested in producing particular faces of this cone, formed of stable triples (a notion defined by J. Stembridge in 2014), using some geometric notions—principally those of dominant and well-covering pairs—and results of N. Ressayre. This extends a result obtained independently by L. Manivel and E. Vallejo in 2014 or 2015, expressed in terms of additive matrices. To illustrate the fact that it allows to produce quite a few new faces of the Kronecker cone, we give at the end of the article details about what our results yield for “small dimensions”.

A nonzero integral flow f is conformally decomposable if $$f=f_1+f_2$$ , where $$f_1,f_2$$ are nonzero integral flows, both are nonnegative or both are nonpositive. Conformally indecomposable flows on ordinary graphs are simply graph circuit flows. However, on signed graphs without outer-edges (compact case), conformally indecomposable flows, classified by Chen and Wang (arXiv:1112.0642, 2013) and by Chen et al. (Discret Math 340:1271–1286, 2017), are signed-graph circuit flows plus an extra class of characteristic flows of so-called Eulerian circle-trees. This paper is to classify indecomposable conformal integral flows on signed graphs with outer-edges (non-compact case). A notable feature is that with outer-edges the treatment is natural and results become stronger but proofs are simpler than that without outer-edges.

COVID19 is the most impactful pandemic of recent times worldwide. It is a highly infectious disease that is caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2 virus), To date there is specific drug nor vaccination against COVID19. Therefor the need for novel and pioneering anti-COVID19 is of paramount importance. In this direction, computer-aided drug design constitutes a very promising antiviral approach for the discovery and analysis of drugs and molecules with biological activity against SARS-CoV2. In silico modelling takes advantage of the massive amounts of biological and chemical data available on the nature of the interactions between the targeted systems and molecules, as well as the rapid progress of computational tools and software. Herein, we describe the potential of the merging of mathematical modelling, artificial intelligence and learning techniques into seamless computational pipelines for the rapid and efficient discovery and design of potent anti- SARS-CoV-2 modulators.

The development of domain-independent planners within the AI planning community is leading to “off-the-shelf” technology that can be used in a wide range of applications. Moreover, it allows a modular approach—in which planners and domain knowledge are modules of larger software applications—that facilitates substitutions or improvements of individual modules without changing the rest of the system. This approach also supports the use of reformulation and configuration techniques, which transform how a model is represented in order to improve the efficiency of plan generation. In this article, we investigate how the performance of domain-independent planners is affected by domain model configuration, i.e. the order in which elements are ordered in the model, particularly in the light of planner comparisons. We then introduce techniques for the online and offline configuration of domain models, and we analyse the impact of domain model configuration on other reformulation approaches, such as macros.

Formalism in the philosophy of mathematics has taken a variety of forms and has been advocated for widely divergent reasons. In Sects. 1 and 2, I briefly introduce the major formalist doctrines of the late nineteenth and early twentieth centuries. These are what I call empirico-semantic formalism (advocated by Heine), game formalism (advocated by Thomae) and instrumental formalism (advocated by Hilbert). After describing these views, I note some basic points of similarity and difference between them. In the remainder of the paper, I turn my attention to Hilbert’s instrumental formalism. My primary aim there will be to develop its formalist elements more fully. These are, in the main, (i) its rejection of the axiom-centric focus of traditional model-construction approaches to consistency problems, (ii) its departure from the traditional understanding of the basic nature of proof and (iii) its distinctively descriptive or observational orientation with regard to the consistency problem for arithmetic. More specifically, I will highlight what I see as the salient points of connection between Hilbert’s formalist attitude and his finitist standard for the consistency proof for arithmetic. I will also note what I see as a significant tension between Hilbert’s observational approach to the consistency problem for arithmetic and his expressed hope that his solution of that problem would dispense with certain epistemological concerns regarding arithmetic once and for all.

This is a follow-up paper of arXiv:1805.00115, where rational curves in surfaces that satisfy general positioned point and cross-ratio conditions were enumerated. A suitable correspondence theorem provided in arXiv:1509.07453 allowed us to use tropical geometry, and, in particular, a degeneration technique called floor diagrams. This correspondence theorem also holds in higher dimension. In the current paper, we introduce so-called cross-ratio floor diagrams and show that they allow us to determine the number of rational space curves that satisfy general positioned point and cross-ratio conditions. Moreover, graphical contributions are introduced which provide a novel and structured way of understanding multiplicities of floor decomposed curves in $\mathbb{R}^3$. Additionally, so-called condition flows on a tropical curve are used to reflect how conditions imposed on a tropical curve yield different types of edges. This concept is applicable in arbitrary dimension., 36 pages, 15 figures; fixed minor issues, added references

Motivated by the works on truncated theta series of Andrews–Merca and Guo–Zeng, the authors of this paper investigated some Hecke–Rogers type double series in their earlier paper. As a continuation of their study, in this paper, a further investigation on double series will be presented.

Recently, Mc Laughlin proved some results on vanishing coefficients in the series expansions of certain infinite q-products for arithmetic progressions modulo 5, modulo 7 and modulo 11 by grouping the results into several families. In this paper, we prove some new results on vanishing coefficients for arithmetic progressions modulo 7, which are not listed by Mc Laughlin. For example, we prove that if $$t \in \{1,2,3\}$$ and the sequence $$\{A_n\}$$ is defined by $$\sum _{n=0}^{\infty }A_nq^n := (-q^t,-q^{7-t};q^7)_{\infty }(q^{7-2t},q^{7+2t};q^{14})^3_{\infty },$$ then $$A_{7n+4t}=A_{7n+6t^2+4t}=0$$ for all n. Also, we prove four families of results with negative signs for arithmetic progressions modulo 7 classified by Mc Laughlin.

For any positive integer m > 2 and an odd prime p, let $\mathbb {F}_{p^{m}}$ be the finite field with pm elements and let $ \text {Tr}^{m}_{e}$ be the trace function from $\mathbb {F}_{p^{m}}$ onto $\mathbb {F}_{p^{e}}$ for a divisor e of m. In this paper, for the defining set $D=\{x\in \mathbb {F}_{p^{m}}:\text {Tr}^{m}_{e}(x)=1\text { and } \text {Tr}^{m}_{e}(x^{2})=0\}=\{d_{1}, d_{2}, \ldots , d_{n}\}$ (say), we define a pe-ary linear code $\mathcal {C}_{D}$ by $$ \mathcal{C}_{D}=\{\textbf{c}_{a} =\left( \text{Tr}^{m}_{e}(ad_{1}), \text{Tr}^{m}_{e}(ad_{2}),\ldots,\text{Tr}^{m}_{e}(ad_{n})\right) : a\in \mathbb{F}_{p^{m}}\}. $$ Then we determine the complete weight enumerator and weight distribution of the linear code $\mathcal {C}_{D}$ . The presented code is optimal with respect to the Griesmer bound provided that $\frac {m}{e}=3$ . In fact, it is MDS when $\frac {m}{e}=3$ . This paper gives the results of S. Yang, X. Kong and C. Tang (Finite Fields Appl. 48 (2017)) if we take e = 1. In addition to the generalization of the results of Yang et al., we study the dual code $\mathcal {C}_{D}^{\perp }$ of the code $\mathcal {C}_{D}$ as well as find some optimal constant composition codes.

Modular methods that transform Byzantine consensus protocols for the synchronous model into ones that are fast and communication efficient in failure-free executions are presented. Small and short protocol segments called layers are custom designed to act as a highly efficient preliminary stage that solves Consensus if no failures occur. When composed with a Byzantine consensus protocol of choice, they allow considerable control over the tradeoff in the combined protocol’s behavior in the presence of failures and its performance in their absence. In failure-free executions, they are more efficient than all existing Byzantine consensus protocols. In the presence of failures, they incur a small cost over the complexity of the original consensus protocol being transformed. A key ingredient underlying the efficiency of the new layers is the judicious use of null messages for broadcasting information in failure-free runs. In particular, the notion of a silent validation round, which implements such a broadcast, is defined and used in several ways.

Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to m identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is $$(2-1/m)$$ ( 2 - 1 / m ) -competitive. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201. No deterministic online strategy can obtain a competitiveness smaller than 1.88. In this paper, we study online makespan minimization in the popular random-order model, where the jobs of a given input arrive as a random permutation. It is known that Greedy does not attain a competitive factor asymptotically smaller than 2 in this setting. We present the first improved performance guarantees. Specifically, we develop a deterministic online algorithm that achieves a competitive ratio of 1.8478. The result relies on a new analysis approach. We identify a set of properties that a random permutation of the input jobs satisfies with high probability. Then we conduct a worst-case analysis of our algorithm, for the respective class of permutations. The analysis implies that the stated competitiveness holds not only in expectation but with high probability. Moreover, it provides mathematical evidence that job sequences leading to higher performance ratios are extremely rare, pathological inputs. We complement the results by lower bounds, for the random-order model. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 4/3. Moreover, no deterministic online algorithm can attain a competitiveness smaller than 3/2 with high probability.

We study several special functions in Ramanujan’s generalized modular equation with signature 3. Some sharp inequalities for these functions, including the estimates for the solution of Ramanujan’s generalized modular equation with signature 3 and triplication inequality for the generalized Grotzsch ring function with two parameters, are derived.

The algebraic monoid structure of an incidence algebra is investigated. We show that the multiplicative structure alone determines the algebra automorphisms of the incidence algebra. We present a formula that expresses the complexity of the incidence monoid with respect to the two sided action of its maximal torus in terms of the zeta polynomial of the poset. In addition, we characterize the finite (connected) posets whose incidence monoids have complexity $\leq 1$. Finally, we determine the covering relations of the adherence order on the incidence monoid of a star poset., Comment: The final version of this article will appear in the Semigroup Forum

Let $$P(x)=a_0x^d+a_1x^{d-1}+\cdots +a_d \in {{\mathbb {Q}}}[x]$$ be a polynomial of degree $$d \ge 2$$ , and let $$x_n$$ , $$n=0,1,2,\ldots $$ , be a sequence of integers satisfying $$x_{n+1}=P(x_n)$$ for $$n \ge 0$$ and $$x_n \rightarrow \infty $$ as $$n \rightarrow \infty $$ . Then, by a recent result of Wagner and Ziegler, $$\alpha =\lim _{n\rightarrow \infty } x_n^{d^{-n}}>1$$ is either an integer or an irrational number, and $$x_n$$ is approximately $$a_0^{-1/(d-1)} \alpha ^{d^n}-a_1/(da_0)$$ . Under assumption $$a_0^{1/(d-1)} \in {{\mathbb {Q}}}$$ on the leading coefficient $$a_0$$ of P, we completely characterize all the cases when the limit $$\alpha $$ is an algebraic number. Our results imply that $$\alpha $$ can be an integer, a quadratic Pisot unit with $$\alpha ^{-1}$$ being its conjugate over $${{\mathbb {Q}}}$$ , or a transcendental number. In most cases $$\alpha $$ is transcendental. For each $$d \ge 2$$ all the polynomials P of degree d for which $$\alpha $$ is an integer or a quadratic Pisot unit are described explicitly. The main theorem implies that several constants related to sequences that appear in a paper of Aho and Sloane and in the online Encyclopedia of Integer Sequences are transcendental.

A fractional matching of a graph G is a function f giving each edge a number in [0, 1] so that $$\sum _{e\in \Gamma _G (v)} f(e)\le 1 $$ for each $$v \in V(G)$$ , where $$\Gamma _G (v)$$ is the set of edges incident to v in G. The fractional matching number of G, denoted by $$\mu _f(G)$$ , is the maximum of $$\sum _{e\in E(G)} f(e)$$ over all fractional matchings f. A fractional matching f of G is called a maximum fractional matching if $$\sum _{e\in E(G)} f(e)=\mu _f(G)$$ . In this paper, as a supplement of known results in Liu et al. (J Comb Optim 40:59–68, 2020), we further study the maximum fractional matching, and give some sufficient and necessary conditions to characterize the maximum fractional matching. Furthermore, as applications, the sharp lower bounds of the fractional matching number for Cartesian product, strong product, lexicographic product and direct product are obtained.

A set S of vertices of a connected graph G is a doubly connected dominating set (DCDS) if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and $$V-S$$ are connected. The doubly connected domination number $$\gamma _{cc}(G)$$ is the minimum size of such a set. The doubly connected domination subdivision number $$\hbox {sd}_{\gamma _{cc}}(G)$$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) to increase the doubly connected domination number. It was conjectured (Karami et al. in Mat Vesnic 64:232–239, 2012) that the doubly connected domination subdivision number of a connected planar graph is at most two. In this paper, we disprove this conjecture by showing that the doubly connected domination subdivision number of the regular icosahedron graph is three.

The graph Cheeger constant and Cheeger inequalities are generalized to the case of hypergraphs whose edges have the same cardinality. In particular, it is shown that the second largest eigenvalue of the generalized normalized Laplacian is bounded both above and below by the generalized Cheeger constant, and the corresponding eigenfunctions can be used to approximate the Cheeger cut.

Given ann-sided polygonPon the plane withn≥4n≥4, a quadrangulation ofPis a geometric plane graph such that the boundary of the outer face isPand that each finite face is quadrilateral. Clearly,Pis quadrangulatable (i.e., admits a quadrangulation) only ifnis even, but there is a non-quadrangulatable even-sided polygon. Ramaswami et al. [Comp Geom 9:257–276, (1998)] proved that everyn-sided polygonPwithn≥4n≥4even admits a quadrangulation with at most⌊n−24⌋⌊n−24⌋Steiner points, where a Steiner point forPis an auxiliary point which can be put in any position in the interior ofP. In this paper, introducing the notion of the spirality ofPto control a structure ofP(independent ofn), we estimate the number of Steiner points to quadrangulateP., This is a post-peer-review, pre-copyedit version of an article published in Graphs and Combinatorics. The final authenticated version is available online at: https://doi.org/10.1007/s00373-021-02346-1

Revocable identity-based encryption (RIBE) is an extension of IBE that satisfies a key revocation mechanism to manage a number of users dynamically and efficiently. To resist quantum attacks, two adaptively secure lattice-based RIBE schemes are known in the (quantum) random oracle model ((Q)ROM). Wang et al.’s scheme that is secure in the ROM has large secret keys depending on the depth of a binary tree and its security reduction is not tight. Ma and Lin’s scheme that is secure in the QROM has large ciphertexts depending on the length of identities and is not anonymous. In this paper, we propose an adaptively secure lattice-based RIBE scheme that is secure in the QROM. Our scheme has compact parameters, where the ciphertext-size is smaller than Wang et al.’s scheme and the secret key size is the same as Ma and Lin’s scheme. Moreover, our scheme is anonymous and its security reduction is completely tight. We design the proposed scheme by modifying Ma–Lin’s scheme instantiated by the Gentry–Peikert–Vaikuntanathan (GPV) IBE. We can obtain the advantages of our scheme by making use of Katsumata et al.’s proof technique of the GPV IBE in the QROM.

The problem of classifying linear systems of conics in projective planes dates back at least to Jordan, who classified pencils (one-dimensional systems) of conics over $${\mathbb {C}}$$ C and $$\mathbb {R}$$ R in 1906–1907. The analogous problem for finite fields $$\mathbb {F}_q$$ F q with q odd was solved by Dickson in 1908. In 1914, Wilson attempted to classify nets (two-dimensional systems) of conics over finite fields of odd characteristic, but his classification was incomplete and contained some inaccuracies. In a recent article, we completed Wilson’s classification (for q odd) of nets of rank one, namely those containing a repeated line. The aim of the present paper is to introduce and calculate certain combinatorial invariants of these nets, which we expect will be of use in various applications. Our approach is geometric in the sense that we view a net of rank one as a plane in $$\mathrm {PG}(5,q)$$ PG ( 5 , q ) , q odd, that meets the quadric Veronesean in at least one point; two such nets are then equivalent if and only if the corresponding planes belong to the same orbit under the induced action of $$\mathrm {PGL}(3,q)$$ PGL ( 3 , q ) viewed as a subgroup of $$\mathrm {PGL}(6,q)$$ PGL ( 6 , q ) . Since q is odd, the orbits of lines in $$\mathrm {PG}(5,q)$$ PG ( 5 , q ) under this action correspond to the aforementioned pencils of conics in $$\mathrm {PG}(2,q)$$ PG ( 2 , q ) . The main contribution of this paper is to determine the line-orbit distribution of a plane $$\pi $$ π corresponding to a net of rank one, namely, the number of lines in $$\pi $$ π belonging to each line orbit. It turns out that this list of invariants completely determines the orbit of $$\pi $$ π , and we will use this fact in forthcoming work to develop an efficient algorithm for calculating the orbit of a given net of rank one. As a more immediate application, we also determine the stabilisers of nets of rank one in $$\mathrm {PGL}(3,q)$$ PGL ( 3 , q ) , and hence the orbit sizes.

Projective two-weight linear codes are closely related to finite projective spaces and strongly regular graphs. In this paper, a family of q-ary two-weight linear codes including two subfamilies of projective codes is presented, where q is a prime power. The parameters of both the codes and their duals are excellent. As applications, the codes are used to derive strongly regular graphs with new parameters and secret sharing schemes with interesting access structures.

The objectives of this paper are to survey and extend results on several classes of asymptotically good quasi-twisted codes over finite field with a low index, namely double circulant codes, double negacirculant codes, four circulant codes and four negacirculant codes. For a given length, we summarize the enumerations of the self-dual and LCD codes and supplement some expansion results. The existence of asymptotically good quasi-twisted codes relies on factorizations of special binomials over finite fields; the existence of these factorizations, in turn, with the assumption of Artin primitive root conjecture, or in some cases can be derived unconditionally by using Dickson polynomials.

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work., LIPIcs, Vol. 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 30:1-30:18

In this paper we study the variety of order Hilbert algebras, which is the equivalent algebraic semantics of the order implicational calculus of Bull (J Symb Logic, 29:33–34, 1964).

Let $$D_n(x;a)$$ and $$E_n(x;a)\in {\mathbb {F}}_q[x]$$ be Dickson polynomials of first and second kind respectively, where $${\mathbb {F}}_q$$ is a finite field with q elements. In this article we show explicitly the irreducible factors of these polynomials in the case that every prime divisor of n divides $$q-1$$ . This result generalizes the results found in (Finite Fields Appl. 3:84–96, 1997; Explicit factorization of cyclotomic and Dickson polynomials over finite fields, Springer, Berlin, 2007; Finite Fields Appl. 38:40-56, 2016; Discrete Math. 342:111618, 2019).

An edge-colored graph is called rainbow (or heterochromatic) if all its edges have distinct colors. It is known that if an edge-colored connected graph H has minimum color degree at least |H|/2 and has a certain property, then H has a rainbow spanning tree. In this paper, we prove that if an edge-colored connected bipartite graph G has minimum color degree at least |G|/3 and has a certain property, then G has a rainbow spanning tree. We also give a similar sufficient condition for G to have a properly colored spanning tree. Moreover, we show that these minimum color-degree conditions are sharp.

A graph is called Hamilton-connected if there exists a Hamiltonian path between every pair of its vertices. Determining whether or not a graph is Hamilton-connected is an NP-complete problem. In this paper, we present two methods to show Hamilton-connectivity in graphs. The first method uses the vertex connectivity and Hamiltoniancity of graphs, and, the second is the definition-based constructive method which constructs Hamiltonian paths between every pair of vertices. By employing these proof techniques, we show that the line graphs of the generalized Petersen, anti-prism and wheel graphs are Hamilton-connected. Combining it with some existing results, it shows that some of these families of Hamilton-connected line graphs have their underlying graph families non-Hamilton-connected. This, in turn, shows that the underlying graph of a Hamilton-connected line graph is not necessarily Hamilton-connected. As side results, the detour index being also an NP-complete problem, has been calculated for the families of Hamilton-connected line graphs. Finally, by computer we generate all the Hamilton-connected graphs on $$\le 7$$ vertices and all the Hamilton-laceable graphs on $$\le 10$$ vertices. Our research contributes towards our proposed conjecture that almost all graphs are Hamilton-connected.

As a subclass of linear codes, cyclic codes have important applications in consumer electronics, data storage systems and communication systems. In this paper, a new family of optimal ternary cyclic codes with minimum distance five are obtained from known perfect nonlinear functions over $\mathbb {F}_{3^{m}}$ . Moreover, we investigate the weight distributions of their duals.

We study games of length ω2 with moves in ℕ and Borel payoff. These are, e.g., games in which two players alternate turns playing digits to produce a real number in [0, 1] infinitely many times, after which the winner is decided in terms of the sequence belonging to a Borel set in the product space [0,1]ℕ. The main theorem is that Borel games of length ω2 are determined if, and only if, for every countable ordinal α, there is a fine-structural, countably iterable model of Zermelo set theory with α-many iterated powersets above a limit of Woodin cardinals.

This paper addresses the job shop scheduling problem including time lag constraints. This is an extension of the job shop scheduling problem with many applications in real production environments, where extra (minimum and maximum) delays can be introduced between operations. It belongs to a category of problems known as NP-hard problems due to the large solution space. Biogeography-based optimization (BBO) is an evolutionary algorithm which is inspired by the migration of species between habitats, recently proposed by Simon (IEEE Trans Evol Comput 12:702–713, 2008) to optimize hard combinatorial optimization problems. BBO has successfully solved optimization problems in many different domains and has demonstrated excellent performance. We propose a hybrid biogeography-based optimization (HBBO) algorithm for solving the job shop scheduling problem with additional time lag constraints while minimizing total completion time. In the proposed HBBO, an effective greedy constructive heuristic is adapted to generate the initial habitat population. A local search metaheuristic is investigated in the mutation step in order to improve the solution quality and enhance the diversity of the population. To assess the performance of the HBBO, a series of experiments are performed on well-known benchmark instances for job shop scheduling problems with time lag constraints. The results prove the efficiency of the proposed algorithm in comparison with various other algorithms.

The aim of this article is to obtain a better understanding and classification of strictly ergodic topological dynamical systems with (measurable) discrete spectrum. To that end, we first determine when an isomorphic maximal equicontinuous factor map of a minimal topological dynamical system has trivial (one point) fibers. In other words, we characterize when minimal mean equicontinuous systems are almost automorphic. Furthermore, we investigate another natural subclass of mean equicontinuous systems, so-called diam-mean equicontinuous systems, and show that a minimal system is diam-mean equicontinuous if and only if the maximal equicontinuous factor is regular (the points with trivial fibers have full Haar measure). Combined with previous results in the field, this provides a natural characterization for every step of a natural hierarchy for strictly ergodic topological models of ergodic systems with discrete spectrum. We also construct an example of a transitive almost diam-mean equicontinuous system with positive topological entropy, and we give a partial answer to a question of Furstenberg related to multiple recurrence.

We continue the study of Rosenthal families initiated by Damian Sobota. We show that every Rosenthal filter is the intersection of a finite family of ultrafilters that are pairwise incomparable in the Rudin-Keisler partial ordering of ultrafilters. We introduce a property of filters, called an $$r$$ -filter, properly between a selective filter and a $$p$$ -filter. We prove that every $$r$$ -ultrafilter is a Rosenthal family. We prove that it is consistent with ZFC to have uncountably many $$r$$ -ultrafilters such that any intersection of finitely many of them is a Rosenthal filter.

Let $\Gamma$ be an amenable countable discrete group. Fix an ergodic free nonsingular action of $\Gamma$ on a nonatomic standard probability space. Let $G$ be a compactly generated locally compact second countable group such that the closure of the group of inner automorphisms of $G$ is compact in the natural topology. It is shown that there exists a {\it bounded} ergodic $G$-valued cocycle of $\Gamma$.

Employee absences are inevitable in practice due to illness, heavy workloads or accidents. These unforeseen events result in the disruption of employee shift rosters, which are then typically repaired using re-rostering methods. Despite their widespread use, repair methods often require last-minute changes to rosters, negatively affecting employees’ personal lives. Robust rosters are thus crucial when it comes to minimizing the negative impact of these unforeseen events. The academic literature, however, currently lacks a metric capable of measuring the robustness of staff rosters. This study introduces two complementary approaches for quantifying roster robustness without the use of simulation. The first metric enables an a priori estimation of how well unexpected employee absences can be accommodated, while the second metric approximates the costs incurred by repair methods. An integer programming-based methodology is proposed for generating robust rosters in a controlled manner. A computational study using public instances based on real-world scenarios demonstrates the effectiveness of the proposed methodology. A significant reduction of costs is observed when enforcing an appropriate level of robustness, compared against when robustness is ignored.