Search

We continue the study of (tw , ω) -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has useful algorithmic implications for the Maximum Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, 164 (2024) 404–442], we introduced the tree-independence number , a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both (tw , ω) -boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Packing problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In particular, this implies polynomial-time solvability of the Maximum Weight Independent Set problem. In this paper, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a K 5 minus an edge or the 4-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most 3 vertices, while excluding a complete bipartite graph K 2 , q implies the existence of a tree decomposition with independence number at most 2 (q − 1). These results are obtained using a variety of tools, including ℓ -refined tree decompositions, SPQR trees, and potential maximal cliques, and actually show that in the bounded cases identified in this work, one can also compute tree decompositions with bounded independence number efficiently. Applying the algorithmic framework provided by the previous paper in the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. In particular, these results apply to the class of 1-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019. [ABSTRACT FROM AUTHOR]

The graph removal lemma is a fundamental result in extremal graph theory which says that for every fixed graph H and ε > 0 , if an n -vertex graph G contains ε n 2 edge-disjoint copies of H then G contains δ n v (H) copies of H for some δ = δ (ε , H) > 0. The current proofs of the removal lemma give only very weak bounds on δ (ε , H) , and it is also known that δ (ε , H) is not polynomial in ε unless H is bipartite. Recently, Fox and Wigderson initiated the study of minimum degree conditions guaranteeing that δ (ε , H) depends polynomially or linearly on ε. In this paper we answer several questions of Fox and Wigderson on this topic. [ABSTRACT FROM AUTHOR]

We say a class C of graphs is clean if for every positive integer t there exists a positive integer w (t) such that every graph in C with treewidth more than w (t) contains an induced subgraph isomorphic to one of the following: the complete graph K t , the complete bipartite graph K t , t , a subdivision of the (t × t) -wall or the line graph of a subdivision of the (t × t) -wall. In this paper, we adapt a method due to Lozin and Razgon (building on earlier ideas of Weißauer) to prove that the class of all H-free graphs (that is, graphs with no induced subgraph isomorphic to a fixed graph H) is clean if and only if H is a forest whose components are subdivided stars. Their method is readily applied to yield the above characterization. However, our main result is much stronger: for every forest H as above, we show that forbidding certain connected graphs containing H as an induced subgraph (rather than H itself) is enough to obtain a clean class of graphs. Along the proof of the latter strengthening, we build on a result of Davies and produce, for every positive integer η , a complete description of unavoidable connected induced subgraphs of a connected graph G containing η vertices from a suitably large given set of vertices in G. This is of independent interest, and will be used in subsequent papers in this series. [ABSTRACT FROM AUTHOR]

The Gyárfás-Sumner conjecture says that for every forest H and every integer k , if G is H -free and does not contain a clique on k vertices then it has bounded chromatic number. (A graph is H-free if it does not contain an induced copy of H.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest H , if G is H -free and does not contain K t , t as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest H , the bound on chromatic number can be taken to be polynomial in t. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree H of radius two and integer d ≥ 2 , if G is H -free and does not contain as a subgraph the complete d -partite graph with parts of cardinality t , then its chromatic number is at most polynomial in t. [ABSTRACT FROM AUTHOR]

The notion of matching minors is a specialisation of minors fit for the study of graphs with perfect matchings. Matching minors have been used to give a structural description of bipartite graphs on which the number of perfect matchings can be computed efficiently, based on a result of Little, by McCuaig et al. in 1999. In this paper we generalise basic ideas from the graph minor series by Robertson and Seymour to the setting of bipartite graphs with perfect matchings. We introduce a version of Erdős-Pósa property for matching minors and find a direct link between this property and planarity. From this, it follows that a class of bipartite graphs with perfect matchings has bounded perfect matching width if and only if it excludes a planar matching minor. We also present algorithms for bipartite graphs of bounded perfect matching width for a matching version of the disjoint paths problem, matching minor containment, and for counting the number of perfect matchings. From our structural results, we obtain that recognising whether a bipartite graph G contains a fixed planar graph H as a matching minor, and that counting the number of perfect matchings of a bipartite graph that excludes a fixed planar graph as a matching minor are both polynomial time solvable. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

This paper is a contribution to the study of hereditary classes of relational structures, these classes being quasi-ordered by embeddability. It deals with the specific case of ordered sets of width two and the corresponding bichains and incomparability graphs. Several open problems about hereditary classes of relational structures which have been considered over the years have a positive answer in this case. For example, well-quasi-ordered hereditary classes of finite bipartite permutation graphs, respectively finite 321-avoiding permutations, have been characterized by Korpelainen, Lozin and Mayhill, respectively by Albert, Brignall, Ruškuc and Vatter. In this paper we present an overview of properties of these hereditary classes in the framework of the Theory of Relations as presented by Roland Fraïssé. We provide another proof of the results mentioned above. It is based on the existence of a countable universal poset of width two, obtained by the first author in 1978, his notion of multichainability (1978) (a kind of analog to letter-graphs), and metric properties of incomparability graphs. Using Laver's theorem (1971) on better-quasi-ordering (bqo) of countable chains we prove that a wqo hereditary class of finite or countable bipartite permutation graphs is necessarily bqo. This gives a positive answer to a conjecture of Nash-Williams (1965) in this case. We extend a previous result of Albert et al. by proving that if a hereditary class of finite, respectively countable, bipartite permutation graphs is wqo, respectively bqo, then the corresponding hereditary classes of posets of width at most two and bichains are wqo, respectively bqo. Several notions of labelled wqo are also considered. We prove that they are all equivalent in the case of bipartite permutation graphs, posets of width at most two and the corresponding bichains. We characterize hereditary classes of finite bipartite permutation graphs which remain wqo when labels from a wqo are added. Hereditary classes of posets of width two, bipartite permutation graphs and the corresponding bichains having finitely many bounds are also characterized. We prove that a hereditary class of finite bipartite permutation graphs is not wqo if and only if it embeds the poset of finite subsets of N ordered by set inclusion. This answers a long standing conjecture of the first author in the case of bipartite permutation graphs. [ABSTRACT FROM AUTHOR]

In this paper we investigate the bipartite analogue of the strong Erdős-Hajnal property. We prove that for every forest H and every τ with 0 < τ ≤ 1 , there exists ε > 0 , such that if G has a bipartition (A , B) and does not contain H as an induced subgraph, and has at most (1 − τ) | A | ⋅ | B | edges, then there is a stable set X of G with | X ∩ A | ≥ ε | A | and | X ∩ B | ≥ ε | B |. No graphs H except forests have this property. [ABSTRACT FROM AUTHOR]

This paper extends the existing theory of perfect reconstruction two-channel filter banks from bipartite graphs to non-bipartite graphs. By generalizing the concept of downsampling/upsampling we establish the frame of two-channel filter bank on arbitrary connected, undirected and weighted graphs. Then the equations for perfect reconstruction of the filter banks are presented and solved under proper conditions. Algorithms for designing orthogonal and biorthogonal banks are given and two typical orthogonal two-channel filter banks are calculated. The locality and approximation properties of such filter banks are discussed theoretically and experimentally. [ABSTRACT FROM AUTHOR]

Let G be a bridgeless cubic graph. The Berge–Fulkerson Conjecture (1970s) states that G admits a list of six perfect matchings such that each edge of G belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan–Raspaud Conjecture (1994), which states that G admits three perfect matchings such that every edge of G belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that G admits two perfect matchings whose deletion yields a bipartite subgraph of G. It can be shown that given an arbitrary perfect matching of G , it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan–Raspaud and the Berge–Fulkerson conjectures, respectively. In this paper, we show that given any 1 + -factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G , there always exists a perfect matching M of G containing e such that G ∖ (F ∪ M) is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in G , there exists a perfect matching of G containing at least one edge of each circuit in this collection. [ABSTRACT FROM AUTHOR]

Let Γ be a connected (X , 2) -arc-transitive bipartite graph with bi-parts Δ 0 and Δ 1 , where X ≤ Aut (Γ). Let X + be the subgroup of X fixing Δ 0 setwise. In this paper, we first prove that if X + is primitive and faithful on Δ 0 and Δ 1 , then the actions of X + on Δ 0 and Δ 1 are primitive of the same type X with X ∈ { HA , SA , PA }. This is then used to prove that if X + is quasiprimitive on Δ 0 of type HA or TW, then either soc (X +) ⊴ Aut (Γ) , or Γ ≅ K q , q (q a prime power) or Γ ≅ K 2 r , 2 r − 2 r K 2 (r ≥ 2). This confirms a conjecture of C. H. Li from 2008. [ABSTRACT FROM AUTHOR]

Many conjectures and open problems in graph theory can either be reduced to cubic graphs or are directly stated for them. Furthermore, it is known that for a lot of problems, a counterexample must be a snark, that is, a bridgeless cubic graph which is not 3-edge-colourable. In this paper we deal with the fact that the family of potential counterexamples to many interesting conjectures can be narrowed even further to the family S ≥ 5 of bridgeless cubic graphs whose edge set cannot be covered with four perfect matchings. The Cycle Double Cover Conjecture, the Shortest Cycle Cover Conjecture and the Fan–Raspaud Conjecture are examples of statements for which S ≥ 5 is crucial. In this paper we study parameters which have the potential to further refine S ≥ 5 and thus enlarge the set of cubic graphs for which the mentioned conjectures can be verified. We show that S ≥ 5 can be naturally decomposed into subsets with increasing complexity, thereby producing a natural scale for proving these conjectures. More precisely, we consider the following parameters and questions: given a bridgeless cubic graph, (i) how many perfect matchings need to be added, (ii) how many copies of the same perfect matching need to be added, and (iii) how many 2-factors need to be added so that the resulting regular graph is Class I? We present new results for these parameters and we also establish some strong relations between these problems and some long-standing conjectures. [ABSTRACT FROM AUTHOR]

• Firstly, we present a new GNN-based model to predict NPI, where NPI's prediction problem is transformed into a link prediction problem. • Secondly, we propose a label trick mechanism in the ncRNA–protein bipartite graph to distinguish heterogeneous nodes ncRNA and protein, which could alleviate the problem of over-coupling. • Thirdly, we propose a self-attention operation that preserves the topology of the input graph during pooling. • Furthermore, We propose a community detection mechanism in the ncRNA–protein bipartite graph, which could represent the cluster (community). ownership relationship of the nodes and to further optimize the node embedding. Non-coding RNA (ncRNA) s play an considerable role in the current biological sciences, such as gene transcription, gene expression, etc. Exploring the ncRNA–protein interactions(NPI) is of great significance, while some experimental techniques are very expensive in terms of time consumption and labor cost. This has promoted the birth of some computational algorithms related to traditional statistics and artificial intelligence. However, these algorithms usually require the sequence or structural feature vector of the molecule. Although graph neural network (GNN) s has been widely used in recent academic and industrial researches, its potential remains unexplored in the field of detecting NPI. Hence, we present a novel GNN-based model to detect NPI in this paper, where the detecting problem of NPI is transformed into the graph link prediction problem. Specifically, the proposed method utilizes two groups of labels to distinguish two different types of nodes: ncRNA and protein, which alleviates the problem of over-coupling in graph network. Subsequently, ncRNA and protein embedding is initially optimized based on the cluster ownership relationship of nodes in the graph. Moreover, the model applies a self-attention mechanism to preserve the graph topology to reduce information loss during pooling. The experimental results indicate that the proposed model indeed has superior performance. [ABSTRACT FROM AUTHOR]

In this paper, we survey some properties, encoding, and bijections involving combinatorial maps, double occurrence words, and chord diagrams. We particularly study quasi-trees from a purely combinatorial point of view and derive a topological representation of maps with a given spanning quasi-tree using two fundamental polygons, which extends the representation of planar maps based on the equivalence with bipartite circle graphs. Then, we focus on Depth-First Search trees and their connection with a poset we define on the spanning quasi-trees of a map. We apply the bijections obtained in the first section to the problem of enumerating loopless rooted maps. Finally, we return to the planar case and discuss a decomposition of planar rooted loopless maps and its consequences on planar rooted loopless map enumeration. [ABSTRACT FROM AUTHOR]

A strengthening of Jaeger's circular flow conjecture, restricted to planar graphs, asserts that every planar graph of odd girth at least 4 k + 1 admits a homomorphism to the odd cycle C 2 k + 1 , and the first case is verified and known as the famous Grötzsch theorem. In this paper, we prove analogous results for signed planar graphs: For k ∈ { 2 , 3 , 4 } every signed bipartite planar graph of negative girth at least 6 k − 4 admits a homomorphism to C − 2 k. Here the negative girth is the length of a shortest cycle with an odd number of negative edges. Note that the k = 2 case was previously obtained in [J. Combin. Theory Ser. B, 153 (2022) 81–104] through a coloring method. Considering the duality between circular colorings and circular flows of planar graphs, our approach is based on the tools developed in the study of flows and group connectivity, and a potential method is applied in handling orientations with special boundaries for planar graphs. Furthermore, our results have several implications for the circular chromatic numbers of signed planar graphs with given girth conditions. [ABSTRACT FROM AUTHOR]

Let H 1 , ..., H k be bipartite graphs. The bipartite Ramsey number b r (H 1 , ... , H k) is the minimum integer N such that any k -edge-coloring of the complete bipartite graph K N , N contains a monochromatic H i in color i for some i ∈ { 1 , 2 , ... , k }. The study of bipartite Ramsey number was initiated in the early 70s by Faudree and Schelp (1975), and they showed that b r (P 2 n , P 2 m) = n + m − 1 , where P n denotes a path with n vertices. Combining their result and the regularity lemma, one can obtain asymptotic value b r (C 2 ⌊ α 1 n ⌋ , C 2 ⌊ α 2 n ⌋ ) = (α 1 + α 2 + o (1)) n for α 1 , α 2 > 0 , where C n denotes a cycle with n vertices. The study of bipartite Ramsey numbers of cycles has also attracted lots of attention recently. For example, Bucić, Letzter and Sudakov (2019) showed that b r (C 2 n , C 2 n , C 2 n) = (3 + o (1)) n and they remarked that it is interesting to determine the exact value of b r (C 2 n , C 2 m). Zhang and Sun (2011), Zhang, Sun, and Wu (2013), and Gholami and Rowshan (2021) determined b r (C 4 , C 2 n) , b r (C 6 , C 2 n) , and b r (C 8 , C 2 n) respectively. In this paper, we determine b r (C 2 n , C 2 m) for all the remaining cases and show that b r (C 2 n , C 2 m) = n + m − 1 for all n > m ≥ 5 and b r (C 2 n , C 2 n) = 2 n if n ≥ 5. It is somehow interesting that b r (C 2 n , C 2 m) is the same as b r (P 2 n , P 2 m) if n ≠ m , and b r (C 2 n , C 2 n) is one more than b r (P 2 n , P 2 n). [ABSTRACT FROM AUTHOR]

Cluster algebra structures for Grassmannians and their (open) positroid strata are controlled by a Postnikov diagram D or, equivalently, a dimer model on the disc, as encoded by either a bipartite graph or the dual quiver (with faces). The associated dimer algebra A , determined directly by the quiver with a certain potential, can also be realised as the endomorphism algebra of a cluster-tilting object in an associated Frobenius cluster category. In this paper, we introduce a class of A -modules corresponding to perfect matchings of the dimer model of D and show that, when D is connected, the indecomposable projective A -modules are in this class. Surprisingly, this allows us to deduce that the cluster category associated to D embeds into the cluster category for the appropriate Grassmannian. We show that the indecomposable projectives correspond to certain matchings which have appeared previously in work of Muller–Speyer. This allows us to identify the cluster-tilting object associated to D , by showing that it is determined by one of the standard labelling rules constructing a cluster of Plücker coordinates from D. By computing a projective resolution of every perfect matching module, we show that Marsh–Scott's formula for twisted Plücker coordinates, expressed as a dimer partition function, is a special case of the general cluster character formula, and thus observe that the Marsh–Scott twist can be categorified by a particular syzygy operation in the Grassmannian cluster category. [ABSTRACT FROM AUTHOR]

A fruitful contemporary paradigm in graph theory is that almost all graphs that do not contain a certain subgraph have common structural characteristics. An example is the well-known result saying that almost all triangle-free graphs are bipartite. The "almost" is crucial, without it such theorems do not hold. In this paper we transfer this paradigm to commutative algebra and make use of deep graph theoretic results. A key tool is the critical graphs introduced relatively recently by Balogh and Butterfield, who proved that almost all graphs not containing a critical subgraph have common structural characteristics analogous to being bipartite. For a graph G , let I G denote its edge ideal, the monomial ideal generated by x i x j for every edge ij of G. In this paper we study the graded Betti numbers of I G , which are combinatorial invariants that measure the complexity of a minimal free resolution of I G. The Betti numbers of the form β i , 2 i + 2 constitute the "main diagonal" of the Betti table. It is well known that for edge ideals any Betti number to the left of this diagonal is always zero. We identify a certain "parabola" inside the Betti table and call parabolic Betti numbers the entries of the Betti table bounded on the left by the main diagonal and on the right by this parabola. Let β i , j be a parabolic Betti number on the r -th row of the Betti table, for r ≥ 3. We prove that almost all graphs G with β i , j (I G) = 0 can be partitioned into r − 2 cliques and one independent set. In particular, for almost all graphs G with β i , j (I G) = 0 , the regularity of I G is r − 1. [ABSTRACT FROM AUTHOR]

For integer k ≥ 2 and prime power q , the algebraic bipartite graph D (k , q) proposed by Lazebnik and Ustimenko in 1993 is useful not only in extremal graph theory but also in coding theory and cryptography. This graph is q -regular, edge-transitive and of girth at least k + 4. Its exact girth g = g (D (k , q)) was conjectured in 1995 to be k + 5 for odd k and q ≥ 4. This conjecture was shown to be valid in 2016 when k + 5 2 | p (q − 1) , where p is the characteristic of F q and m | p n means that m divides p r n for some nonnegative integer r. In this paper, for t ≥ 1 , we prove that (a) g (D (4 t + 2 , q)) = g (D (4 t + 1 , q)) ; (b) g (D (4 t + 3 , q)) = 4 t + 8 if g (D (2 t , q)) = 2 t + 4 ; (c) g (D (8 t , q)) = 8 t + 4 if g (D (4 t − 2 , q)) = 4 t + 2 ; (d) g (D (2 s + 2 t − 5 , q)) = 2 s + 2 t if p ≥ 3 , 2 s | (q − 1) , 2 s + 1 ∤ (q − 1) , 2 ∤ t and t | p (q − 1). A simple upper bound for the girth of D (k , q) is proposed in the end of this paper. [ABSTRACT FROM AUTHOR]

Let k and d be positive integers such that k ≥ d + 2. Consider two k -colourings of a d -degenerate graph G. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper colouring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length. The k -reconfiguration graph of G is the graph whose vertices are the proper k -colourings of G , with an edge between two colourings if they differ on exactly one vertex. Cereceda's conjecture can be reformulated as follows: the diameter of the (d + 2) -reconfiguration graph of any d -degenerate graph on n vertices is O (n 2). So far, there is no proof of a polynomial upper bound on the diameter, even for d = 2. In this paper, we prove that the diameter of the k -reconfiguration graph of a d -degenerate graph is O (n d + 1) for k ≥ d + 2. Moreover, we prove that if k ≥ 3 2 (d + 1) then the diameter of the k -reconfiguration graph is quadratic, improving the previous bound of k ≥ 2 d + 1. We also show that the 5-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs. [ABSTRACT FROM AUTHOR]

In 1994, Erdős, Gyárfás and Łuczak posed the following problem: given disjoint vertex sets V 1 , ... , V n of size k , with exactly one edge between any pair V i , V j , how large can n be such that there will always be an independent transversal? They showed that the maximal n is at most (1 + o (1)) k 2 , by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a 2 e -factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if n ≤ (1 − o (1)) k 2 , there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are 'locally sparse', meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global maximum degree condition for the existence of an independent transversal. We show that this can be relaxed to an average degree condition. We can also use our new theorem to establish tight bounds for a more general version of the Erdős–Gyárfás–Łuczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turán numbers of complete bipartite graphs, which might be of independent interest. [ABSTRACT FROM AUTHOR]

The canonical double cover B (X) of a graph X is the direct product of X and K 2. If Aut (B (X)) ≅ Aut (X) × Z 2 then X is called stable; otherwise X is called unstable. An unstable graph is nontrivially unstable if it is connected, non-bipartite and distinct vertices have different neighborhoods. A circulant is a Cayley graph on a cyclic group. Qin et al. (2019) [18] conjectured that there are no nontrivially unstable circulants of odd order. In this paper we prove this conjecture. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the connectivity of friends-and-strangers graphs, which were introduced by Defant and Kravitz in 2020. We begin by considering friends-and-strangers graphs arising from two random graphs and consider the threshold probability at which such graphs attain maximal connectivity. We slightly improve the lower bounds on the threshold probabilities, thus disproving two conjectures of Alon, Defant and Kravitz. We also improve the upper bound on the threshold probability in the case of random bipartite graphs, and obtain a tight bound up to a factor of n o (1). Further, we introduce a generalization of the notion of friends-and-strangers graphs in which vertices of the starting graphs are allowed to have multiplicities and obtain generalizations of previous results of Wilson and of Defant and Kravitz in this new setting. [ABSTRACT FROM AUTHOR]

A vertex triple (u , v , w) of a graph is called a 2 -geodesic if v is adjacent to both u and w and u is not adjacent to w. A graph is said to be 2 -geodesic transitive if its automorphism group is transitive on the set of 2-geodesics. In this paper, a complete classification of 2-geodesic transitive graphs of order p n is given for each prime p and n ≤ 3. It turns out that all such graphs consist of three small graphs: the complete bipartite graph K 4 , 4 of order 8, the Schläfli graph of order 27 and its complement, and fourteen infinite families: the cycles C p , C p 2 and C p 3 , the complete graphs K p , K p 2 and K p 3 , the complete multipartite graphs K p [ p ] , K p [ p 2 ] and K p 2 [ p ] , the Hamming graph H (2 , p) and its complement, the Hamming graph H (3 , p) , and two infinite families of normal Cayley graphs on the extraspecial group of order p 3 and exponent p. [ABSTRACT FROM AUTHOR]

A family F of sets is union-closed if the union of any two sets from F belongs to F. The union-closed sets conjecture states that if F is a finite union-closed family of finite sets, then there is an element that belongs to at least half of the sets in F. The conjecture has several equivalent formulations in terms of other combinatorial structures such as lattices and graphs. In its whole generality the conjecture remains wide open, but it was verified for various important classes of lattices, such as lower semimodular lattices, and graphs, such as chordal bipartite graphs. In the present paper we develop a Boolean approach to the conjecture and verify it for several classes of Boolean functions, such as submodular functions and double Horn functions. [ABSTRACT FROM AUTHOR]

For positive integers n > d ≥ k , let ϕ (n , d , k) denote the least integer ϕ such that every n -vertex graph with at least ϕ vertices of degree at least d contains a path on k + 1 vertices. Many years ago, Erdős, Faudree, Schelp and Simonovits proposed the study of the function ϕ (n , d , k) , and conjectured that for any positive integers n > d ≥ k , it holds that ϕ (n , d , k) ≤ ⌊ k − 1 2 ⌋ ⌊ n d + 1 ⌋ + ϵ , where ϵ = 1 if k is odd and ϵ = 2 otherwise. In this paper we determine the values of the function ϕ (n , d , k) exactly. This confirms the above conjecture of Erdős et al. for all positive integers k ≠ 4 and in a corrected form for the case k = 4. Our proof utilizes, among others, a lemma of Erdős et al. [3] , a theorem of Jackson [6] , and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin [7] , where the latter two results concern maximum cycles in bipartite graphs. Moreover, we construct examples to provide answers to two closely related questions raised by Erdős et al. [ABSTRACT FROM AUTHOR]

Given a graph H and an integer p , the edge blow-up H p + 1 of H is the graph obtained from replacing each edge in H by a clique of order p + 1 where the new vertices of the cliques are all distinct. The Turán numbers for edge blow-up of matchings were first studied by Erdős and Moon. In this paper, we determine the range of the Turán numbers for edge blow-up of all bipartite graphs and the exact Turán numbers for edge blow-up of all non-bipartite graphs. In addition, we characterize the extremal graphs for edge blow-up of all non-bipartite graphs. Our results also extend several known results, including the Turán numbers for edge blow-up of stars, paths and cycles. The method we used can also be applied to find a family of counter-examples to a conjecture posed by Keevash and Sudakov in 2004 concerning the maximum number of edges not contained in any monochromatic copy of H in a 2-edge-coloring of K n. [ABSTRACT FROM AUTHOR]

Generalizing a graph-theoretical result of Maffray to binary matroids, Oxley and Wetzler proved that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is isomorphic to M (K 4) or F 7 , or M is the cycle matroid of a graph consisting of a collection of triangles all sharing a common edge. In this paper, we show that if M is a 3-connected binary matroid having a 5-element circuit but no larger odd circuit, then M has rank less than six; or M has rank six and is one of nine sporadic matroids; or M can be obtained by attaching together, via generalized parallel connection across a common triangle, a collection of copies of F 7 and M (K 4) and then possibly deleting up to two elements of the common triangle. From this, we deduce that a 3-connected simple graph with a 5-cycle but no larger odd cycle is obtained from K 3 , n for some n ≥ 3 by adding one, two, or three edges between the vertices in the 3-vertex class. [ABSTRACT FROM AUTHOR]

An edge cut C of a graph G is tight if | C ∩ M | = 1 for every perfect matching M of G. Barrier cuts and 2-separation cuts are called ELP-cuts , which are two important types of tight cuts in matching covered graphs. Edmonds, Lovász and Pulleyblank proved that if a matching covered graph has a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho, Lucchesi, and Murty made a stronger conjecture: given any nontrivial tight cut C in a matching covered graph G , there exists a nontrivial ELP-cut D in G which does not cross C. We confirm the conjecture in this paper. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A proper total weighting of G is a mapping w : V ∪ E ⟶ R such that the following sum for each v ∈ V : w (v) + ∑ e ∈ E (v) w (e) gives a proper vertex colouring of G. For any a , b ∈ N + , we say that G is total weight (a , b) -choosable if for any { S v : v ∈ V } ⊂ [ R ] a and { S e : v ∈ E } ⊂ [ R ] b , there exists a proper total weighting w of G such that w (v) ∈ S v for v ∈ V and w (e) ∈ S e for e ∈ E. A strengthening of the 1-2-3 Conjecture states that every graph without an isolated edge is total weight (1 , 3) -choosable. In this paper, we prove that every graph without an isolated edge is total weight (1 , 17) -choosable. We also prove some new results on the total weight choosability of bipartite graphs. [ABSTRACT FROM AUTHOR]

The extremal number ex (n , F) of a graph F is the maximum number of edges in an n -vertex graph not containing F as a subgraph. A real number r ∈ [ 1 , 2 ] is realisable if there exists a graph F with ex (n , F) = Θ (n r). Several decades ago, Erdős and Simonovits conjectured that every rational number in [ 1 , 2 ] is realisable. Despite decades of effort, the only known realisable numbers are 0 , 1 , 7 5 , 2 , and the numbers of the form 1 + 1 m , 2 − 1 m , 2 − 2 m for integers m ≥ 1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than the two numbers 1 and 2. In this paper, we make progress on the conjecture of Erdős and Simonovits. First, we show that 2 − a b is realisable for any integers a , b ≥ 1 with b > a and b ≡ ± 1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2 − 1 m in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. [ABSTRACT FROM AUTHOR]

The reconfiguration graph C k (G) for the k -colourings of a graph G has a vertex for each proper k -colouring of G , and two vertices of C k (G) are adjacent precisely when those k -colourings differ on a single vertex of G. Much work has focused on bounding the maximum value of diam C k (G) over all n -vertex graphs G. We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if L is a list-assignment for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C L (G) ≤ n (G) + μ (G). We also conjecture that if (L , H) is a correspondence cover for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C (L , H) (G) ≤ n (G) + τ (G). (Here μ (G) and τ (G) denote the matching number and vertex cover number of G.) For every graph G , we give constructions showing that both conjectures are best possible, which also hints towards an exact form of Cereceda's Conjecture for regular graphs. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) diam C L (G) ≤ n (G) + 2 μ (G) and diam C (L , H) (G) ≤ n (G) + 2 τ (G). Our second main result proves that both conjectured bounds hold, whenever all v satisfy | L (v) | ≥ 2 d (v) + 1. We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree. The full paper can also be found at arxiv.org/abs/2204.07928. [ABSTRACT FROM AUTHOR]

Connected graphs whose second largest eigenvalue λ 2 does not exceed 1 have been investigated in the last four decades. Over the years only few particular classes with this spectral property are completely determined. For example, they include bipartite graphs, line graphs and threshold graphs. In this paper we determine all connected (K 4 − e) -free graphs, i.e., the graphs that do not contain an induced subgraph isomorphic to the graph obtained by removing an edge from the complete graph of order 4; such graphs are also called diamond-free graphs. Since every triangle-free graph is automatically diamond-free, our results includes all triangle-free graphs with λ 2 ≤ 1. Moreover, it includes all connected bipartite graphs with the same spectral property, and therefore strengthens the result of Petrović (J. Combin. Theory B, 1991). [ABSTRACT FROM AUTHOR]

The paper studies wsat (G , H) which is the minimum number of edges in a weakly H -saturated subgraph of G. We prove that wsat (K n , H) is 'stable' – remains the same after independent removal of every edge of K n with constant probability – for all pattern graphs H such that there exists a 'local' set of edges percolating in K n. This is true, for example, for cliques and complete bipartite graphs. We also find a threshold probability for the weak K 1 , t -saturation stability. [ABSTRACT FROM AUTHOR]

Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes. • We consider the resource provision problem for users with cost minimization and model the identified problem by considering two types of cost: replication cost and transmission cost. We first discuss a simple case, and one optimal solution is proposed. We then consider a more complicated case in which each user can upload multiple replications on fog nodes in the provisioning process. Two models are discussed: the 0–1 transmission cost model and the different transmission cost model. • We propose an optimal solution for the 0–1 transmission cost model. Then we prove that the problem under the different transmission cost model is NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. • Various simulations were conducted to compare our joint optimization methods with several state-of-the-art ones based on two real datasets: the Mobike dataset and the Microsoft GPS trajectory dataset. The results are shown from different perspectives to provide conclusions. [ABSTRACT FROM AUTHOR]

Previously, Ohsugi and Hibi gave a combinatorial description of bipartite graphs G whose toric edge ideal I G is generated by quadrics, showing that every cycle of G of length at least 6 must have a chord. This corresponds to the Green-Lazarsfeld condition N 1. In this paper, we investigate the higher syzygies of I G and give combinatorial descriptions of the Green-Lazarsfeld conditions N p of toric edge ideals of bipartite graphs for all p ≥ 1. In particular, we show that I G is linearly presented (i.e. satisfies condition N 2) if and only if the bipartite complement of G is a tree of diameter at most 3. We also investigate the regularity of linearly presented toric edge ideals and give criteria for polyomino ideals to satisfy the Green-Lazarsfeld conditions. [ABSTRACT FROM AUTHOR]

Methods of finding sequence similarity play a significant role in computational biology. Owing to the rapid increase of genome sequences in public databases, the evolutionary relationship of species becomes more challenging. But traditional alignment-based methods are found inappropriate due to their time-consuming nature. Therefore, it is necessary to find a faster method, which applies to species phylogeny. In this paper, a new graph-theory based alignment-free sequence comparison method is proposed. A complete-bipartite graph is used to represent each genome sequence based on its nucleotide triplets. Subsequently, with the help of the weights of edges of the graph, a vector descriptor is formed. Finally, the phylogenetic tree is drawn using the UPGMA algorithm. In the present case, the datasets for comparison are related to mammals, viruses, and bacteria. In most of the cases, the phylogeny in the present case is found to be more satisfactory as compared to earlier methods. • A new graph-theory based alignment-free genome sequence comparison. • Use of complete bipartite graph to represent genome sequences. • Descriptor based on the weights of the edges of the graph. • Comparison of the phylogenetic trees of different mammals, viruses, and bacteria. • Less time complexity compared to that of earlier methods. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are a type of directed acyclic graph that represent how a set X of present-day species are descended from a common ancestor by processes of speciation and reticulate evolution. In the absence of reticulate evolution, such networks are simply phylogenetic (evolutionary) trees. Moreover, phylogenetic networks that are not trees can sometimes be represented as phylogenetic trees with additional directed edges placed between their edges. Such networks are called tree-based , and the class of phylogenetic networks that are tree-based has recently been characterised. In this paper, we establish a number of new characterisations of tree-based networks in terms of path partitions and antichains (in the spirit of Dilworth's theorem), as well as via matchings in a bipartite graph. We also show that a temporal network is tree-based if and only if it satisfies an antichain-to-leaf condition. In the second part of the paper, we define three indices that measure the extent to which an arbitrary phylogenetic network deviates from being tree-based. We describe how these three indices can be computed efficiently using classical results concerning maximum-sized matchings in bipartite graphs. [ABSTRACT FROM AUTHOR]

Let G be a finite group, and let cs (G) denote the set of sizes of the conjugacy classes of G. The prime graph built on cs (G) , that we denote by Δ (G) , is the (simple undirected) graph whose vertices are the prime divisors of the numbers in cs (G) , and two distinct vertices p , q are adjacent if and only if pq divides some number in cs (G). A rephrasing of the main theorem in [8] is that the complement Δ ‾ (G) of the graph Δ (G) does not contain any cycle of length 3. In this paper we generalize this result, showing that Δ ‾ (G) does not contain any cycle of odd length , i.e., it is a bipartite graph. In other words, the vertex set V (G) of Δ (G) is covered by two subsets, each inducing a complete subgraph (a clique). As an immediate consequence, setting ω (G) to be the maximum size of a clique in Δ (G) , the inequality | V (G) | ≤ 2 ω (G) holds for every finite group G. [ABSTRACT FROM AUTHOR]

A graph Γ is symmetric or arc-transitive if its automorphism group Aut (Γ) is transitive on the arc set of the graph, and Γ is basic if Aut (Γ) has no non-trivial normal subgroup N such that the quotient graph Γ N has the same valency as Γ. In this paper, we classify symmetric basic graphs of order 2 q p n and valency 5, where q < p are two primes and n is a positive integer. It is shown that such a graph is isomorphic to a family of Cayley graphs on dihedral groups of order 2 q with 5 | (q − 1) , the complete graph K 6 of order 6, the complete bipartite graph K 5 , 5 of order 10, or one of the nine sporadic coset graphs associated with non-abelian simple groups. As an application, connected pentavalent symmetric graphs of order k p n for some small integers k and n are classified. [ABSTRACT FROM AUTHOR]

In this paper, we establish a couple of results on extremal problems in bipartite graphs. Firstly, we show that every sufficiently large bipartite graph with average degree D and with n vertices on each side has a balanced independent set containing (1 − ϵ) log D D n vertices from each side for small ϵ > 0. Secondly, we prove that the vertex set of every sufficiently large balanced bipartite graph with maximum degree at most Δ can be partitioned into (1 + ϵ) Δ log Δ balanced independent sets. Both of these results are algorithmic and best possible up to a factor of 2, which might be hard to improve as evidenced by the phenomenon known as 'algorithmic barrier' in the literature. The first result improves a recent theorem of Axenovich, Sereni, Snyder, and Weber in a slightly more general setting. The second result improves a theorem of Feige and Kogan about coloring balanced bipartite graphs. [ABSTRACT FROM AUTHOR]

The famous Erdős-Falconer distance problems aim to quantify the extent to which large sets must determine many distinct distances. The problems in both the Euclidean setting and the discrete setting have received much attention. An interesting generalization of Erdős-Falconer problems is to find locating point configurations with prescribed metric structure within large subsets. In this paper, we consider such problem in the discrete setting. We say a distance graph H in F q n under Hamming metric means a graph H = (V , E) with vertices as the points in V ⊆ F q n and edges being assigned by Hamming distance between the pairs of vertices. We call a subset A ⊆ F q n contains an isometric copy of distance graph H , if there exists an embedding ϕ : V (H) → A such that for every edge u v ∈ E (H) , the Hamming distance between ϕ (u) and ϕ (v) is equal to the Hamming distance between u and v. When q is a fixed prime power and n goes to infinity, we show that for any given bipartite graph H with ex (n , H) = O (n) , any subset A ⊆ F q n contains a positive proportion of all possible isometric copies of distance graphs H whose edges are assigned by the same Hamming distance, if | A | > q (1 − c) n for some c = c (q , H) > 0. Our methods also work for general bipartite graphs. Moreover, we will give the quantitative bounds for the above constant c = c (q , H). Unlike using analytical method as before, our ideas are more combinatorial, which mainly include two techniques. The first one is the celebrated dependent random choice, which is like glue, sticking several small structures together. The second one is a new extension of the modular version of the classical Delsarte's inequality. In particular, this extension itself is of independent interest, which also helps us build a surprising connection between our main results and the extremal number of the bipartite graphs. [ABSTRACT FROM AUTHOR]

Abstract In this paper we give a new characterization of the dual polar graphs, extending the work of Brouwer and Wilbrink on regular near polygons. Also as a consequence of our characterization we confirm a conjecture of the authors on non-bipartite distance-regular graphs with smallest eigenvalue at most − k / 2 , where k is the valency of the distance-regular graph, in the case where c 2 ≥ 3 and a 1 = 1. [ABSTRACT FROM AUTHOR]

This paper defines the related notions of bipartite and Eulerian minors for binary matroids. Using these definitions, it characterizes graphic matroids within the classes of bipartite binary matroids and Eulerian binary matroids by the exclusion of certain bipartite minors and Eulerian minors, respectively. This result on Eulerian minors in binary matroids extends a result of Chudnovsky et al. who characterized planar graphs within the class of bipartite graphs by the exclusion of K 3 , 3 as a bipartite minor. [ABSTRACT FROM AUTHOR]

Many famous graphs are edge-primitive. Weiss (1973) and Guo et al. (2013) determined edge-primitive graphs of valency 3 and 5, respectively. In this paper, we study edge-primitive graphs of any prime valency. It is proved that all such graphs are 2-arc-transitive and the full automorphism groups are almost simple with the only exception the graphs being the complete bipartite graphs, and a complete classification is given of such graphs with soluble edge stabilizers, which widely extends the classifications of Weiss and Guo et al. (notice that the edge stabilizers of edge-primitive graphs with valency at most 5 are soluble). [ABSTRACT FROM AUTHOR]

A map is said to be even-closed if all of its automorphisms act like even permutations on the vertex set. In this paper the study of even-closed regular maps is approached by analysing two distinguished families. The first family consists of embeddings of a well-known family of graphs on distinct orientable surfaces, whereas in the second family we consider all graphs having orientable-regular embeddings on a particular surface. In particular, the classification of even-closed orientable-regular embeddings of the complete bipartite graphs K n , n and classification of even-closed orientable-regular maps on the torus are given. [ABSTRACT FROM AUTHOR]

Highlights • Mid level discriminative features for action recognition. • Extended to zero shot learning setup. • Results on KTH, UCF-101, HMDB-51 and HOHA comparable to the state of the art. In this paper, we propose a novel mid-level feature representation for the recognition of actions in videos. This descriptor proves to posses relevant discriminative power when used in a generic action recognition pipeline. It is well known that mid-level feature descriptors learnt using class-oriented information are potentially more distinctive than the low-level features extracted in a bottom-up unsupervised fashion. In this regard, we introduce the notion of concepts , a mid-level feature representation capable of tracking the dynamics of motion salient regions over consecutive frames in a video sequence. Our feature representation is based on the idea of region correspondence over consecutive frames and we make use of an unsupervised iterative bipartite graph matching algorithm to extract representative visual concepts from action videos. The progression of such salient regions, which are also consistent in appearance, are henceforth represented as chain graphs. Finally, we adopt an intuitive time-series pooling strategy to extract discriminant features from the chains, which are then used in a dictionary learning based classification framework. Given the high variability of the movements of different human body parts in separate actions, the extracted conceptual descriptors are proved to capture the different dynamic characteristics by exclusively encoding the interaction parts associated to the chains. Further, we use such descriptors in a semi-supervised, clustering-based zero-shot action recognition setting, showing good performance and without resorting to costly attribute annotation. We validate the proposed framework on four public datasets namely KTH, UCF-101, HOHA and HMDB-51, reporting increased (and comparable in some cases) classification accuracies with respect to the state of the art. [ABSTRACT FROM AUTHOR]

It is a classical result that an unrooted tree T having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. Moreover, if each non-leaf vertex of T has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in T is the following: for each non-leaf vertex v , choose a leaf in each of the three components of T − v , group these three leaves into three pairs, and take the union of this set over all choices of v . This forms a so-called ‘triplet cover’ for T . In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for T uniquely determine T and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, ‘sparse’, and ‘shellable’. [ABSTRACT FROM AUTHOR]

Ryser's Conjecture states that any r -partite r -uniform hypergraph has a vertex cover of size at most r − 1 times the size of the largest matching. For r = 2 , the conjecture is simply König's Theorem and every bipartite graph is a witness for its tightness. The conjecture has also been proven for r = 3 by Aharoni using topological methods, but the proof does not give information on the extremal 3-uniform hypergraphs. Our goal in this paper is to characterize those hypergraphs which are tight for Aharoni's Theorem. Our proof of this characterization is also based on topological machinery, particularly utilizing results on the (topological) connectedness of the independence complex of the line graph of the link graphs of 3-uniform Ryser-extremal hypergraphs. We use this information to nail down the elements of a structure we call home-base hypergraph . While there is a single minimal home-base hypergraph with matching number k for every positive integer k ∈ N , home-base hypergraphs with matching number k are far from being unique. There are infinitely many of them and each of them is composed of k copies of two different kinds of basic structures, whose hyperedges can intersect in various restricted, but intricate ways. Our characterization also proves an old and wide open strengthening of Ryser's Conjecture, due to Lovász, for the 3-uniform extremal case, that is, for hypergraphs with τ = 2 ν . [ABSTRACT FROM AUTHOR]

Drug-disease associations provide important information for drug discovery and drug repositioning. Drug-disease associations can induce different effects, and the therapeutic effect attracts wide spread interest. Therefore, developing drug-disease association prediction methods is an important task, and differentiating therapeutic associations from other associations is also very important. In this paper, we formulate the known drug-disease associations as a bipartite network, and then present a novel representation for drugs and diseases based on the bipartite network and linear neighborhood similarity. Thus, we propose the network topological similarity-based inference method (NTSIM) to predict unobserved drug-disease associations. Further, we extend the work to the association classification, and propose the network topological similarity-based classification method (NTSIM-C) to differentiate therapeutic associations from others. Compared with existing drug-disease association prediction methods, NTSIM can produce superior performances in predicting drug-disease associations, and NTSIM-C can accurately classify drug-disease associations. Further, we analyze the capability of proposed methods by using several case studies. The studies show the usefulness of NTSIM and NTSIM-C in the real applications. In conclusion, NTSIM and NTSIM-C are promising for predicting drug-disease associations and their therapeutic functions. [ABSTRACT FROM AUTHOR]