Search

We investigate natural Turán problems for mixed graphs, generalizations of graphs where edges can be either directed or undirected. We study a natural Turán density coefficient that measures how large a fraction of directed edges an F -free mixed graph can have; we establish an analogue of the Erdős-Stone-Simonovits theorem and give a variational characterization of the Turán density coefficient of any mixed graph (along with an associated extremal F -free family). This characterization enables us to highlight an important divergence between classical extremal numbers and the Turán density coefficient. We show that Turán density coefficients can be irrational, but are always algebraic; for every positive integer k , we construct a family of mixed graphs whose Turán density coefficient has algebraic degree k. [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]

A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph K n is asymptotically minimised by the random colouring, or equivalently, t H (W) + t H (1 − W) ≥ 2 1 − e (H) holds for every graphon W : [ 0 , 1 ] 2 → [ 0 , 1 ] , where t H (.) denotes the homomorphism density of the graph H. Paths and cycles being common is one of the earliest cornerstones in extremal graph theory, due to Mulholland and Smith (1959), Goodman (1959), and Sidorenko (1989). We prove a graph homomorphism inequality that extends the commonality of paths and cycles. Namely, t H (W) + t H (1 − W) ≥ t K 2 (W) e (H) + t K 2 (1 − W) e (H) whenever H is a path or a cycle and W : [ 0 , 1 ] 2 → R is a bounded symmetric measurable function. This answers a question of Sidorenko from 1989, who proved a slightly weaker result for even-length paths to prove the commonality of odd cycles. Furthermore, it also settles a recent conjecture of Behague, Morrison, and Noel in a strong form, who asked if the inequality holds for graphons W and odd cycles H. Our proof uses Schur convexity of complete homogeneous symmetric functions, which may be of independent interest. [ABSTRACT FROM AUTHOR]

In 1995, Komlós, Sárközy and Szemerédi showed that every large n -vertex graph with minimum degree at least (1 / 2 + γ) n contains all spanning trees of bounded degree. We consider a generalization of this result to loose spanning hypertrees in 3-graphs, that is, linear hypergraphs obtained by successively appending edges sharing a single vertex with a previous edge. We show that for all γ and Δ, and n large, every n -vertex 3-uniform hypergraph of minimum vertex degree (5 / 9 + γ) ( n 2 ) contains every loose spanning tree T with maximum vertex degree Δ. This bound is asymptotically tight, since some loose trees contain perfect matchings. [ABSTRACT FROM AUTHOR]

Let X be a family of subsets of a finite set E. A matroid on E is called an X -matroid if each set in X is a circuit. We develop techniques for determining when there exists a unique maximal X -matroid in the weak order poset of all X -matroids on E and formulate a conjecture which would characterise the rank function of this unique maximal matroid when it exists. The conjecture suggests a new type of matroid rank function which extends the concept of weakly saturated sequences from extremal graph theory. We verify the conjecture for various families X and show that, if true, the conjecture could have important applications in such areas as combinatorial rigidity and low rank matrix completion. [ABSTRACT FROM AUTHOR]

• Data driven inflammatory subgroups show connectivity differences in psychosis. • High inflammation subgroup has lower DMNa activity vs the low inflammation group. • High inflammation subgroup has lower DMNa functional connectivity vs the low group. • High inflammation subgroup has lower multiplex participation vs the low group. • Network findings in high inflammation subgroups correlate with worse cognition. High-inflammation subgroups of patients with psychosis demonstrate cognitive deficits and neuroanatomical alterations. Systemic inflammation assessed using IL-6 and C-reactive protein may alter functional connectivity within and between resting-state networks, but the cognitive and clinical implications of these alterations remain unknown. We aim to determine the relationships of elevated peripheral inflammation subgroups with resting-state functional networks and cognition in psychosis spectrum disorders. Serum and resting-state fMRI were collected from psychosis probands (schizophrenia, schizoaffective, psychotic bipolar disorder) and healthy controls (HC) from the B-SNIP1 (Chicago site) study who were stratified into inflammatory subgroups based on factor and cluster analyses of 13 cytokines (HC Low n = 32, Proband Low n = 65, Proband High n = 29). Nine resting-state networks derived from independent component analysis were used to assess functional and multilayer connectivity. Inter-network connectivity was measured using Fisher z-transformation of correlation coefficients. Network organization was assessed by investigating networks of positive and negative connections separately, as well as investigating multilayer networks using both positive and negative connections. Cognition was assessed using the Brief Assessment of Cognition in Schizophrenia. Linear regressions, Spearman correlations, permutations tests and multiple comparison corrections were used for analyses in R. Anterior default mode network (DMNa) connectivity was significantly reduced in the Proband High compared to Proband Low (Cohen's d = -0.74, p = 0.002) and HC Low (d = -0.85, p = 0.0008) groups. Inter-network connectivity between the DMNa and the right-frontoparietal networks was lower in Proband High compared to Proband Low (d = -0.66, p = 0.004) group. Compared to Proband Low, the Proband High group had lower negative (d = 0.54, p = 0.021) and positive network (d = 0.49, p = 0.042) clustering coefficient, and lower multiplex network participation coefficient (d = -0.57, p = 0.014). Network findings in high inflammation subgroups correlate with worse verbal fluency, verbal memory, symbol coding, and overall cognition. These results expand on our understanding of the potential effects of peripheral inflammatory signatures and/or subgroups on network dysfunction in psychosis and how they relate to worse cognitive performance. Additionally, the novel multiplex approach taken in this study demonstrated how inflammation may disrupt the brain's ability to maintain healthy co-activation patterns between the resting-state networks while inhibiting certain connections between them. [ABSTRACT FROM AUTHOR]

Let H be a graph. We show that if r is large enough as a function of H , then the r -partite Turán graph maximizes the number of copies of H among all K r + 1 -free graphs on a given number of vertices. This confirms a conjecture of Gerbner and Palmer. [ABSTRACT FROM AUTHOR]

A 0 , 1 matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers k , there exists a square regular 0 , 1 matrix with binary rank k , such that the Boolean rank of its complement is k Ω ˜ (log ⁡ k). This settles, in a strong form, a question of Pullman (1988) [27] and a conjecture of Hefner et al. (1990) [18]. The result can be viewed as a regular analogue of a recent result of Balodis et al. (2021) [2] , motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers k , there exists a regular graph with biclique partition number k and chromatic number k Ω ˜ (log ⁡ k). [ABSTRACT FROM AUTHOR]

In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called edge-ordered if its edges are linearly ordered. This notion allows us to study graphs (and in particular their maximum number of edges) when a subgraph is forbidden with a specific edge-order but the same underlying graph may appear with a different edge-order. We prove an Erdős-Stone-Simonovits-type theorem for edge-ordered graphs—we identify the relevant parameter for the Turán number of an edge-ordered graph and call it the order chromatic number. We establish several important properties of this parameter. We also study Turán numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in discrete geometry. [ABSTRACT FROM AUTHOR]

In this paper, all graphs are assumed to be finite. For s ≥ 1 and a graph Γ, if for every pair of isomorphic connected induced subgraphs on at most s vertices there exists an automorphism of Γ mapping the first to the second, then we say that Γ is s -connected-set-homogeneous, and if every isomorphism between two isomorphic connected induced subgraphs on at most s vertices can be extended to an automorphism of Γ, then we say that Γ is s -connected-homogeneous. For n ≥ 1 , a graph Γ is said to be locally 2 K n if the subgraph [ Γ (u) ] induced on the set of vertices of Γ adjacent to a given vertex u is isomorphic to 2 K n. Note that 2-connected-set-homogeneous but not 2-connected-homogeneous graphs are just the half-arc-transitive graphs which are a quite active topic in algebraic graph theory. Motivated by this, we posed the problem of characterizing or classifying 3-connected-set-homogeneous graphs of girth 3 which are not 3-connected-homogeneous in Zhou (2021) [54]. Until now, there have been only two known families of 3-connected-set-homogeneous graphs of girth 3 which are not 3-connected-homogeneous, and these graphs are locally 2 K n with n = 2 or 4. In this paper, we complete the classification of finite 3-connected-set-homogeneous graphs which are locally 2 K n with n ≥ 2 , and all such graphs are line graphs of some specific 2-arc-transitive graphs. Furthermore, we give a good description of finite 3-connected-set-homogeneous but not 3-connected-homogeneous graphs which are locally 2 K n and have solvable automorphism groups. This is then used to construct some new 3-connected-set-homogeneous but not 3-connected-homogeneous graphs as well as some new 2-arc-transitive graphs. [ABSTRACT FROM AUTHOR]

The chromatic index χ ′ (G) of a graph G is the least number of colors assigned to the edges of G such that no two adjacent edges receive the same color. The total chromatic number χ ″ (G) of a graph G is the least number of colors assigned to the edges and vertices of G such that no two adjacent edges receive the same color, no two adjacent vertices receive the same color and no edge has the same color as its two endpoints. The chromatic index and the total chromatic number are two of few fundamental graph parameters, and their correlation has always been a subject of intensive study in graph theory. By definition, χ ′ (G) ≤ χ ″ (G) for every graph G. In 1984, Goldberg conjectured that for any multigraph G , if χ ′ (G) ≥ Δ (G) + 3 then χ ″ (G) = χ ′ (G). In this paper, we show that Goldberg's conjecture is asymptotically true. More specifically, we prove that for a multigraph G with maximum degree Δ sufficiently large, χ ″ (G) = χ ′ (G) provided χ ′ (G) ≥ Δ + 10 Δ 35 / 36. When χ ′ (G) ≥ Δ (G) + 2 , the chromatic index χ ′ (G) is completely determined by the fractional chromatic index. Consequently, the total chromatic number χ ″ (G) can be computed in polynomial-time in this case. [ABSTRACT FROM AUTHOR]

A basic result in graph theory says that any n -vertex tournament with in- and out-degrees larger than n − 2 4 contains a Hamilton cycle, and this is tight. In 1990, Bollobás and Häggkvist significantly extended this by showing that for any fixed k and ε > 0 , and sufficiently large n , all tournaments with degrees at least n 4 + ε n contain the k -th power of a Hamilton cycle. Up until now, there has not been any progress on determining a more accurate error term in the degree condition, neither in understanding how large n should be in the Bollobás-Häggkvist theorem. We essentially resolve both of these questions. First, we show that if the degrees are at least n 4 + c n 1 − 1 / ⌈ k / 2 ⌉ for some constant c = c (k) , then the tournament contains the k -th power of a Hamilton cycle. In particular, in order to guarantee the square of a Hamilton cycle, one only needs a constant additive term. We also present a construction which, modulo a well known conjecture on Turán numbers for complete bipartite graphs, shows that the error term must be of order at least n 1 − 1 / ⌈ (k − 1) / 2 ⌉ , which matches our upper bound for all even k. For odd k , we believe that the lower bound can be improved. Indeed, we show that for k = 3 , there are tournaments with degrees n 4 + Ω (n 1 / 5) and no cube of a Hamilton cycle. In addition, our results imply that the Bollobás-Häggkvist theorem already holds for n = ε − Θ (k) , which is best possible. [ABSTRACT FROM AUTHOR]

We present a method which provides a unified framework for most stability theorems that have been proved in graph and hypergraph theory. Our main result reduces stability for a large class of hypergraph problems to the simpler question of checking that a hypergraph H with large minimum degree that omits the forbidden structures is vertex-extendable. This means that if v is a vertex of H and H − v is a subgraph of the extremal configuration(s), then H is also a subgraph of the extremal configuration(s). In many cases vertex-extendability is quite easy to verify. We illustrate our approach by giving new short proofs of hypergraph stability results of Pikhurko, Hefetz-Keevash, Brandt-Irwin-Jiang, Bene Watts-Norin-Yepremyan and others. Since our method always yields minimum degree stability, which is the strongest form of stability, in some of these cases our stability results are stronger than what was known earlier. Along the way, we clarify the different notions of stability that have been previously studied. [ABSTRACT FROM AUTHOR]

We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let c (ℓ) be the limit of the ratio of the maximum number of cycles of length ℓ in an n -vertex tournament and the expected number of cycles of length ℓ in the random n -vertex tournament, when n tends to infinity. It is well-known that c (3) = 1 and c (4) = 4 / 3. We show that c (ℓ) = 1 if and only if ℓ is not divisible by four, which settles a conjecture of Bartley and Day. If ℓ is divisible by four, we show that 1 + 2 ⋅ (2 / π) ℓ ≤ c (ℓ) ≤ 1 + (2 / π + o (1)) ℓ and determine the value c (ℓ) exactly for ℓ = 8. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length ℓ when ℓ is not divisible by four or ℓ ∈ { 4 , 8 }. [ABSTRACT FROM AUTHOR]

Minors play a key role in graph theory, and extremal problems on forbidding minors have attracted appreciable amount of interest in the past decades. In this paper, we focus on spectral extrema of K s , t -minor free graphs, and determine extremal graphs with maximum spectral radius over all K s , t -minor free graphs of sufficiently large order. This generalizes and improves several previous results. For t ≥ s ≥ 2 , our result completely solves Tait's conjecture. For t ≥ s = 1 , our result gives a spectral analogue of a theorem due to Ding, Johnson and Seymour, which determines the maximum number of edges in K 1 , t -minor free connected graphs. Some spectral and structural tools, such as, local edge maximality, local degree sequence majorization and double eigenvectors transformation, are used to characterize structural properties of extremal graphs. [ABSTRACT FROM AUTHOR]

Let ⊲ be a relation between graphs. We say a graph G is ⊲ -ubiquitous if whenever Γ is a graph with n G ⊲ Γ for all n ∈ N , then one also has ℵ 0 G ⊲ Γ , where αG is the disjoint union of α many copies of G. The Ubiquity Conjecture of Andreae, a well-known open problem in the theory of infinite graphs, asserts that every locally finite connected graph is ubiquitous with respect to the minor relation. In this paper we show that all trees are ubiquitous with respect to the topological minor relation, irrespective of their cardinality. This answers a question of Andreae from 1979. [ABSTRACT FROM AUTHOR]

For the interpolation of graph signals with generalized shifts of a graph basis function (GBF), we introduce the concept of positive definite functions on graphs. This concept merges kernel-based interpolation with spectral theory on graphs and can be regarded as a graph analog of radial basis function interpolation in Euclidean spaces or spherical basis functions. We provide several descriptions of positive definite functions on graphs, the most relevant one is a Bochner-type characterization in terms of positive Fourier coefficients. These descriptions allow us to design GBF's and to study GBF interpolation in more detail. We are able to characterize the native spaces of the interpolants. We provide explicit estimates for the interpolation error and obtain bounds for the numerical stability. As a final application, we show how GBF interpolation can be used to get quadrature formulas on graphs. [ABSTRACT FROM AUTHOR]

We consider the problem of characterizing the 'duality gap' between sparse synthesis- and cosparse analysis-driven signal models through the lens of spectral graph theory, in an effort to comprehend their precise equivalencies and discrepancies. By detecting and exploiting the inherent connectivity structure, and hence, distinct set of properties, of rank-deficient graph difference matrices such as the graph Laplacian, we are able to substantiate differences between the cosparse analysis and sparse synthesis models, according to which the former constitutes a constrained and translated instance of the latter. In view of a general union of subspaces model, we conduct a study of the associated subspaces and their composition, which further facilitates the refinement of specialized uniqueness and recovery guarantees, and discover an underlying structured sparsity model based on the graph incidence matrix. Furthermore, for circulant graphs, we provide an exact characterization of underlying subspaces by deriving closed-form expressions as well as demonstrating transitional properties between equivalence and non-equivalence for a parametric generalization of the graph Laplacian. [ABSTRACT FROM AUTHOR]

In this paper, we extend the chromatic symmetric function X to a chromatic k-multisymmetric function X k , defined for graphs equipped with a partition of their vertex set into k parts. We demonstrate that this new function retains the basic properties and basis expansions of X , and we give a method for systematically deriving new linear relationships for X from previous ones by passing them through X k. In particular, we show how to take advantage of homogeneous sets of G (those S ⊆ V (G) such that each vertex of V (G) ﹨ S is either adjacent to all of S or is nonadjacent to all of S) to relate the chromatic symmetric function of G to those of simpler graphs. Furthermore, we show how extending this idea to homogeneous pairs S 1 ⊔ S 2 ⊆ V (G) generalizes the process used by Guay-Paquet to reduce the Stanley-Stembridge conjecture to unit interval graphs. [ABSTRACT FROM AUTHOR]

We introduce the following combinatorial problem. Let G be a triangle-free regular graph with edge density ρ. (In this paper all densities are normalized by n , n 2 2 etc. rather than by n − 1 , ( n 2 ) , ...) What is the minimum value a (ρ) for which there always exist two non-adjacent vertices such that the density of their common neighbourhood is ≤ a (ρ) ? We prove a variety of upper bounds on the function a (ρ) that are tight for the values ρ = 2 / 5 , 5 / 16 , 3 / 10 , 11 / 50 , with C 5 , Clebsch, Petersen and Higman-Sims being respective extremal configurations. Our proofs are entirely combinatorial and are largely based on counting densities in the style of flag algebras. For small values of ρ , our bound attaches a combinatorial meaning to so-called Krein conditions that might be interesting in its own right. We also prove that for any ϵ > 0 there are only finitely many values of ρ with a (ρ) ≥ ϵ but this finiteness result is somewhat purely existential (the bound is double exponential in 1 / ϵ). [ABSTRACT FROM AUTHOR]

One of the most fundamental results in structural graph theory is the "two-paths theorem" that characterizes 2-linkage by planarity. As an extension of the theorem, we consider the following problem for a fixed graph H with four vertices: Given a graph G and an injective map from V (H) to V (G) , is there a subdivision of H in G with four branch vertices specified by the map? Hence the case H = 2 K 2 corresponds to the 2-linkage problem. In this paper, for any fixed H with four vertices, we give a structural characterization of 6-connected graphs G with no such subdivision of H. As a corollary, we prove that every 7-connected graph contains a subdivision of K 4 with prescribed branch vertices. This generalizes a result of McCarty, Wang and Yu which states that every 7-connected graph is 4-ordered. We also prove that every triangle-free 6-connected graph contains a subdivision of K 4 with prescribed branch vertices. This solves a special case of a conjecture of Mader. [ABSTRACT FROM AUTHOR]

• We introduce the MELD data model: a diffusion framework for multiscale clustering. • We show how cluster coherence and separation interact with diffusion in MELD clusterings. • We introduce the M-LUND multiscale clustering algorithm and guarantee its performance. • We guarantee that M-LUND recovers the MELD data model from many datasets. • We show M-LUND extracts latent multiscale structure in synthetic and real datasets. Clustering algorithms partition a dataset into groups of similar points. The clustering problem is very general, and different partitions of the same dataset could be considered correct and useful. To fully understand such data, it must be considered at a variety of scales, ranging from coarse to fine. We introduce the Multiscale Environment for Learning by Diffusion (MELD) data model, which is a family of clusterings parameterized by nonlinear diffusion on the dataset. We show that the MELD data model precisely captures latent multiscale structure in data and facilitates its analysis. To efficiently learn the multiscale structure observed in many real datasets, we introduce the Multiscale Learning by Unsupervised Nonlinear Diffusion (M-LUND) clustering algorithm, which is derived from a diffusion process at a range of temporal scales. We provide theoretical guarantees for the algorithm's performance and establish its computational efficiency. Finally, we show that the M-LUND clustering algorithm detects the latent structure in a range of synthetic and real datasets. [ABSTRACT FROM AUTHOR]

We propose a new point of view in the study of Fourier analysis on graphs, taking advantage of localization in the Fourier domain. For a signal f on vertices of a weighted graph G with Laplacian matrix L , standard Fourier analysis of f relies on the study of functions g (L) f for some filters g on I L , the smallest interval containing the Laplacian spectrum sp (L) ⊂ I L. We show that for carefully chosen partitions I L = ⊔ 1 ≤ k ≤ K I k (I k ⊂ I L), there are many advantages in understanding the collection (g (L I k ) f) 1 ≤ k ≤ K instead of g (L) f directly, where L I is the projected matrix P I (L) L. First, the partition provides a convenient modelling for the study of theoretical properties of Fourier analysis and allows for new results in graph signal analysis (e.g. noise level estimation, Fourier support approximation). We extend the study of spectral graph wavelets to wavelets localized in the Fourier domain, called LocLets, and we show that well-known frames can be written in terms of LocLets. From a practical perspective, we highlight the interest of the proposed localized Fourier analysis through many experiments that show significant improvements in two different tasks on large graphs, noise level estimation and signal denoising. Moreover, efficient strategies permit to compute sequence (g (L I k ) f) 1 ≤ k ≤ K with the same time complexity as for the computation of g (L) f. [ABSTRACT FROM AUTHOR]

• 36% of first episode schizophrenia patients were in the high inflammation subtype. • The high inflammation subtype exhibited greater cortical thickness compared to the low inflammation subtype. • The low inflammation subtype had lower cortical and subcortical measures compared to controls. • Global and nodal network topological differences were found between subtypes and controls. • Individual cytokines and inflammatory signatures were associated with cognition and symptom measures. Peripheral inflammation is implicated in schizophrenia, however, not all individuals demonstrate inflammatory alterations. Recent studies identified inflammatory subtypes in chronic psychosis with high inflammation having worse cognitive performance and displaying neuroanatomical enlargement compared to low inflammation subtypes. It is unclear if inflammatory subtypes exist earlier in the disease course, thus, we aim to identify inflammatory subtypes in antipsychotic naïve First-Episode Schizophrenia (FES). 12 peripheral inflammatory markers, clinical, cognitive, and neuroanatomical measures were collected from a naturalistic study of antipsychotic-naïve FES patients. A combination of unsupervised principal component analysis and hierarchical clustering was used to categorize inflammatory subtypes from their cytokine data (17 FES High, 30 FES Low, and 33 healthy controls (HCs)). Linear regression analysis was used to assess subtype differences. Neuroanatomical correlations with clinical and cognitive measures were performed using partial Spearman correlations. Graph theoretical analyses were performed to assess global and local network properties across inflammatory subtypes. The FES High group made up 36% of the FES group and demonstrated significantly greater levels of IL1β, IL6, IL8, and TNFα compared to FES Low, and higher levels of IL1β and IL8 compared to HCs. FES High had greater right parahippocampal, caudal anterior cingulate, and bank superior sulcus thicknesses compared to FES Low. Compared to HCs, FES Low showed smaller bilateral amygdala volumes and widespread cortical thickness. FES High and FES Low groups demonstrated less efficient topological organization compared to HCs. Individual cytokines and/or inflammatory signatures were positively associated with cognition and symptom measures. Inflammatory subtypes are present in antipsychotic-naïve FES and are associated with inflammation-mediated cortical expansion. These findings support our previous findings in chronic psychosis and point towards a connection between inflammation and blood–brain barrier disruption. Thus, identifying inflammatory subtypes may provide a novel therapeutic avenue for biomarker-guided treatment involving anti-inflammatory medications. [ABSTRACT FROM AUTHOR]

We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension d admit a proper labeled sample compression scheme of size d. This considerably extends results of Moran and Warmuth on ample classes, of Ben-David and Litman on affine arrangements of hyperplanes, and of the authors on complexes of uniform oriented matroids, and is a step towards the sample compression conjecture – one of the oldest open problems in computational learning theory. On the one hand, our approach exploits the rich combinatorial cell structure of COMs via oriented matroid theory. On the other hand, viewing tope graphs of COMs as partial cubes creates a fruitful link to metric graph theory. [ABSTRACT FROM AUTHOR]

The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition , which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set. [ABSTRACT FROM AUTHOR]

Hadwiger's conjecture, among the most famous open problems in graph theory, states that every graph that does not contain K t as a minor is properly (t − 1) -colorable. The purpose of this work is to demonstrate that a natural extension of Hadwiger's problem to hypergraph coloring exists, and to derive some first partial results and applications. Generalizing ordinary graph minors to hypergraphs, we say that a hypergraph H 1 is a minor of a hypergraph H 2 , if a hypergraph isomorphic to H 1 can be obtained from H 2 via a finite sequence of the following operations: • deleting vertices and hyperedges, • contracting a hyperedge (i.e., merging the vertices of the hyperedge into a single vertex). First we show that a weak extension of Hadwiger's conjecture to hypergraphs holds true: For every t ≥ 1 , there exists a finite (smallest) integer h (t) such that every hypergraph with no K t -minor is h (t) -colorable, and we prove 3 2 (t − 1) ≤ h (t) ≤ 2 g (t) where g (t) denotes the maximum chromatic number of graphs with no K t -minor. Using the recent result by Delcourt and Postle that g (t) = O (t log log t) , this yields h (t) = O (t log log t). We further conjecture that h (t) = 3 2 (t − 1) , i.e., that every hypergraph with no K t -minor is 3 2 (t − 1) -colorable for all t ≥ 1 , and prove this conjecture for all hypergraphs with independence number at most 2. By considering special classes of hypergraphs, the above additionally has some interesting applications for ordinary graph coloring, such as: • every graph G is O (k t log log t) -colorable or contains a K t -minor model all whose branch-sets are k -edge-connected, • every graph G is O (q t log log t) -colorable or contains a K t -minor model all whose branch-sets are modulo- q -connected (i.e., every pair of vertices in the same branch-set has a connecting path of prescribed length modulo q), • by considering cycle hypergraphs of digraphs, we obtain known results on strong minors in digraphs with large dichromatic number as special cases. We also construct digraphs with dichromatic number 3 2 (t − 1) not containing the complete digraph on t vertices as a strong minor, thus answering a question by Mészáros and the author in the negative. [ABSTRACT FROM AUTHOR]

Brualdi–Hoffman–Turán-type problem asks what is the maximum spectral radius λ 1 (G) of an H -free graph G on m edges? This problem gives a spectral perspective on the existence of a subgraph H. A significant result, due to Nikiforov, states that λ 1 (G) ≤ 2 m (1 − 1 r) for every K r + 1 -free graph G (Nikiforov, 2002). Bollobás and Nikiforov further conjectured λ 1 2 (G) + λ 2 2 (G) ≤ 2 m (1 − 1 r) for every K r + 1 -free graph G (Bollobás and Nikiforov, 2007). Let C k + denote the graph obtained from a k -cycle by adding a chord between two vertices of distance two. Zhai, Lin and Shu conjectured that for k ≥ 2 and m sufficiently large, if G is a C 2 k + 1 -free or C 2 k + 2 -free graph, then λ 1 (G) ≤ k − 1 + 4 m − k 2 + 1 2 , with equality if and only if G ≅ K k ∇ (m k − k − 1 2) K 1 (Zhai et al., 2021). This conjecture was also included in a survey of Liu and Ning as one of twenty unsolved problems in spectral graph theory. Recently, Y.T. Li posed a stronger conjecture, which states that the above spectral bound holds for C 2 k + 1 + -free and C 2 k + 2 + -free graphs. In this paper, we confirm these two conjectures by using k -core method and spectral techniques. This presents a new approach to study Brualdi–Hoffman–Turán problems [ABSTRACT FROM AUTHOR]

• MCNs were constructed by applying Jensen-Shannon divergence to regional joint probability distributions derived from different morphological features. • MCNs showed efficient small-word organization and high test-retest reliability, aligned with cortical cytoarchitectonics and symmetry and axonal connectivity, and explained inter-individual variance in behavior and cognition. • MCNs built based on multiple features performed better than those derived from different single features in most aspects mentioned above. Morphological features sourced from structural magnetic resonance imaging can be used to infer human brain connectivity. Although integrating different morphological features may theoretically be beneficial for obtaining more precise morphological connectivity networks (MCNs), the empirical evidence to support this supposition is scarce. Moreover, the incorporation of different morphological features remains an open question. In this study, we proposed a method to construct cortical MCNs based on multiple morphological features. Specifically, we adopted a multi-dimensional kernel density estimation algorithm to fit regional joint probability distributions (PDs) from different combinations of four morphological features, and estimated inter-regional similarity in the joint PDs via Jensen-Shannon divergence. We evaluated the method by comparing the resultant MCNs with those built based on different single morphological features in terms of topological organization, test-retest reliability, biological plausibility, and behavioral and cognitive relevance. We found that, compared to MCNs built based on different single morphological features, MCNs derived from multiple morphological features displayed less segregated, but more integrated network architecture and different hubs, had higher test-retest reliability, encompassed larger proportions of inter-hemispheric edges and edges between brain regions within the same cytoarchitectonic class, and explained more inter-individual variance in behavior and cognition. These findings were largely reproducible when different brain atlases were used for cortical parcellation. Further analysis of macaque MCNs revealed weak, but significant correlations with axonal connectivity from tract-tracing, independent of the number of morphological features. Altogether, this paper proposes a new method for integrating different morphological features, which will be beneficial for constructing MCNs. [ABSTRACT FROM AUTHOR]

• Seven brain regions show both reduced cortical thickness and abnormal QSM levels in AD patients. • We observed significant correlations across AD patients between region-specific cortical thickness and network topology. • Decreased correlation between QSM value and structural network efficiency in AD patients at individual level across brain regions with reduced cortical thickness and aberrant QSM value. Aberrant susceptibility due to iron level abnormality and brain network disconnections are observed in Alzheimer's disease (AD), with disrupted iron homeostasis hypothesized to be linked to AD pathology and neuronal loss. However, whether associations exist between abnormal quantitative susceptibility mapping (QSM), brain atrophy, and altered brain connectome in AD remains unclear. Based on multi-parametric brain imaging data from 30 AD patients and 26 healthy controls enrolled at the China-Japan Friendship Hospital, we investigated the abnormality of the QSM signal and volumetric measure across 246 brain regions in AD patients. The structural and functional connectomes were constructed based on diffusion MRI tractography and functional connectivity, respectively. The network topology was quantified using graph theory analyses. We identified seven brain regions with both reduced cortical thickness and abnormal QSM (p < 0.05) in AD, including the right superior frontal gyrus, left superior temporal gyrus, right fusiform gyrus, left superior parietal lobule, right superior parietal lobule, left inferior parietal lobule, and left precuneus. Correlations between cortical thickness and network topology computed across patients in the AD group resulted in statistically significant correlations in five of these regions, with higher correlations in functional compared to structural topology. We computed the correlation between network topological metrics, QSM value and cortical thickness across regions at both individual and group-averaged levels, resulting in a measure we call spatial correlations. We found a decrease in the spatial correlation of QSM and the global efficiency of the structural network in AD patients at the individual level. These findings may provide insights into the complex relationships among QSM, brain atrophy, and brain connectome in AD. [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]

Models and metrics to measure ecological connectivity are now well-developed and widely used in research and applications to mitigate the ecological impacts of climate change and anthropogenic habitat loss. Despite the prevalent application of connectivity models, however, relatively little is known about the performance of these methods in predicting functional connectivity patterns and organism movement. Our goal in this paper was to compare different connectivity models in their abilities to predict a wide range of simulated animal movement patterns. We used the Pathwalker software to evaluate the performance of several connectivity model predictions based on graph theory, resistant kernels, and factorial least-cost paths. In addition, we assessed the efficacy of synoptic and patch-based approaches to defining source points for analysis. In total, we produced 28 different simulations of animal movement. As we expected, we found that the choice of connectivity model used was the variable that most influenced prediction accuracy. Moreover, we found that the resistant kernels approach consistently provided the strongest correlations to the simulated underlying movement processes. The results also suggested that the agent-based simulation approach itself can often be the best analytical framework to map functional connectivity for ecological research and conservation applications, given its biological realism and flexibility to implement combinations of movement mechanism, dispersal threshold, directional bias, destination bias and spatial composition of source locations for analysis. In doing so, we provide novel insights to guide future functional connectivity analyses. In future research, we could use the same model for several different species groups and see how this reliability depends on the species analyzed. This could bring to light other elements that play an essential role in predicting connectivity. • The connectivity method is what influences predictions the most. • Using a synoptic approach better predicts walker movements than a patch-based one. • Agent-based simulation approach may often be the best analytical framework to map functional connectivity. • Simulation model flexibility is a key factor in determining connectivity. • Resistant kernel-based has the best performance in predicting simulated movement patterns. [ABSTRACT FROM AUTHOR]

Random hyperspherical harmonics are Gaussian Laplace eigenfunctions on the unit d -dimensional sphere (d ≥ 2). We study the convergence in Total Variation distance for their nonlinear statistics in the high energy limit, i.e., for diverging sequences of Laplace eigenvalues. Our approach takes advantage of a recent result by Bally, Caramellino and Poly (2020): combining the Central Limit Theorem in Wasserstein distance obtained by Marinucci and Rossi (2015) for Hermite-rank 2 functionals with new results on the asymptotic behavior of their Malliavin-Sobolev norms, we are able to establish second order Gaussian fluctuations in this stronger probability metric as soon as the functional is regular enough. Our argument requires some novel estimates on moments of products of Gegenbauer polynomials that may be of independent interest, which we prove via the link between graph theory and diagram formulas. [ABSTRACT FROM AUTHOR]

We generalize subgraph densities, arising in dense graph limit theory, to Markov spaces (symmetric measures on the square of a standard Borel space). More generally, we define an analogue of the set of homomorphisms in the form of a measure on maps of a finite graph into a Markov space. The existence of such homomorphism measures is not always guaranteed, but can be established under rather natural smoothness conditions on the Markov space and sparseness conditions on the graph. This continues a direction in graph limit theory in which such measures are viewed as limits of graph sequences. [ABSTRACT FROM AUTHOR]

• In this paper, we characterize Hamming and Johnson graphs by their spectral gap. • We confirm Babai's conjecture on the motion of distance-regular graphs of bounded diameter. • Our characterization of Hamming graphs involves only inequality constraints. One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with μ ≥ 2 and second largest eigenvalue θ 1 = b 1 − 1. In this paper we give a classification under the (weaker) approximate eigenvalue constraint θ 1 ≥ (1 − ε) b 1 for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs of bounded diameter. This conjecture asserts that if X is a primitive distance-regular graph with n vertices, and X is not a Hamming graph or a Johnson graph, then the automorphism group Aut (X) has minimal degree ≥ c n for some constant c > 0. It follows that Aut (X) satisfies strong structural constraints. [ABSTRACT FROM AUTHOR]

For p ∈ N , a coloring λ of the vertices of a graph G is p-centered if for every connected subgraph H of G , either H receives more than p colors under λ or there is a color that appears exactly once in H. Centered colorings play an important role in the theory of sparse graph classes introduced by Nešetřil and Ossona de Mendez [31,32] , as they structurally characterize classes of bounded expansion — one of the key sparsity notions in this theory. More precisely, a class of graphs C has bounded expansion if and only if there is a function f : N → N such that every graph G ∈ C for every p ∈ N admits a p -centered coloring with at most f (p) colors. Unfortunately, known proofs for the existence of such colorings yield large upper bounds on the function f governing the number of colors needed, even for as simple classes as planar graphs. In this paper, we prove that every K t -minor-free graph admits a p -centered coloring with O (p g (t)) colors for some function g. In the special case that the graph is embeddable in a fixed surface Σ we show that it admits a p -centered coloring with O (p 19) colors, with the degree of the polynomial independent of the genus of Σ. This provides the first polynomial upper bounds on the number of colors needed in p -centered colorings of graphs drawn from proper minor-closed classes, which answers an open problem posed by Dvořák [1]. As an algorithmic application, we use our main result to prove that if C is a fixed proper minor-closed class of graphs, then given graphs H and G , on p and n vertices, respectively, where G ∈ C , it can be decided whether H is a subgraph of G in time 2 O (p log ⁡ p) ⋅ n O (1) and space n O (1). [ABSTRACT FROM AUTHOR]

Generalized Turán problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem, maximizing the number of cliques of a fixed order in a graph with fixed number of vertices and bounded maximum degree, was recently completely resolved by Chase. Kirsch and Radcliffe raised a natural variant of this problem where the number of edges is fixed instead of the number of vertices. In this paper, we determine the maximum number of cliques of a fixed order in a graph with fixed number of edges and bounded maximum degree, resolving a conjecture by Kirsch and Radcliffe. We also give a complete characterization of the extremal graphs. [ABSTRACT FROM AUTHOR]

Anari, Gharan, and Vinzant proved (complete) log-concavity of the basis generating functions for all matroids. From the viewpoint of combinatorial Hodge theory, it is natural to ask whether these functions are "strictly" log-concave for simple matroids. In this paper, we show this strictness for simple graphic matroids, that is, we show that Kirchhoff polynomials of simple graphs are strictly log-concave. Our key observation is that the Kirchhoff polynomial of a complete graph can be seen as the (irreducible) relative invariant of a certain prehomogeneous vector space, which may be independently interesting in its own right. Furthermore, we prove that for any a i ∈ R > 0 , a 1 x 1 + ⋯ + a n x n ∈ R M 1 satisfies the strong Lefschetz property (moreover, Hodge–Riemann bilinear relation) at degree one of the Artinian Gorenstein algebra R M ⁎ associated to a graphic matroid M , which is defined by Maeno and Numata for all matroids. [ABSTRACT FROM AUTHOR]

Half-arc-transitive graphs are a fascinating topic which connects graph theory, Riemann surfaces and group theory. Although fruitful results have been obtained over the last half a century, it is still challenging to construct half-arc-transitive graphs with prescribed vertex stabilizers. Until recently, there have been only six known connected tetravalent half-arc-transitive graphs with nonabelian vertex stabilizers, and the question whether there exists a connected tetravalent half-arc-transitive graph with nonabelian vertex stabilizer of order 2 s for every s ⩾ 3 has been wide open. This question is answered in the affirmative in this paper via the construction of a connected tetravalent half-arc-transitive graph with vertex stabilizer D 8 2 × C 2 m for each integer m ⩾ 1 , where D 8 2 is the direct product of two copies of the dihedral group of order 8 and C 2 m is the direct product of m copies of the cyclic group of order 2. The graphs constructed have surprisingly many significant properties in various contexts. [ABSTRACT FROM AUTHOR]

Let M = (T , C , P) be a security model, where T is a rooted tree, C is a multiset of costs and P is a multiset of prizes and let (T , c , p) be a security system, where c and p are bijections of costs and prizes. The problems of computing an optimal attack on a security system and of determining an edge e ∈ E (T) such that the maximum sum of prizes obtained from an optimal attack in (T , c , p) is minimized when c (e) = ∞ are considered. An O (G 2 n) -time algorithm to compute an optimal attack as well as an O (G 2 n 2) -time algorithm to determine such an edge are given, in addition to a (1- ϵ) FPTAS with the time bound O (1 ϵ 2 n 3 log ⁡ G) and a (1+ ϵ) FPTAS with the time bound O (1 ϵ 2 n 4 log ⁡ G) for the first and second problems, respectively. [ABSTRACT FROM AUTHOR]

By bringing computing capacity from a remote cloud environment closer to the user, fog computing is introduced. As a result, users can access the services from more nearby computing environments, resulting in better quality of service and lower latency on the network. From the service providers' point of view, this addresses the network latency and congestion issues. This is achieved by deploying the services in cloud and fog computing environments. The responsibility of service providers is to manage the heterogeneous resources available in both computing environments. In recent years, resource management strategies have made it possible to efficiently allocate resources from nearby fog and clouds to users' applications. Unfortunately, these existing resource management strategies fail to give the desired result when the service providers have the opportunity to allocate the resources to the users' application from fog nodes that are at a multi-hop distance from the nearby fog node. The complexity of this resource management problem drastically increases in a MultiFog-Cloud environment. This problem motivates us to revisit and present a novel Heuristic Resource Allocation and Optimization algorithm in a MultiFog-Cloud (HeRAFC) environment. Taking users' application priority, execution time, and communication latency into account, HeRAFC optimizes resource utilization and minimizes cloud load. The proposed algorithm is evaluated and compared with related algorithms. The simulation results show the efficiency of the proposed HeRAFC over other algorithms. • The resource allocation problem in a multifog-cloud environment is studied. • The physical infrastructure of multifog-cloud is modeled using graph theory. • The resource allocation problem is formulated with a mixed ILP model. • The proposed algorithm can also deploy the user's task on nearby fog nodes. • Simulation results outperform other related algorithms in said environment. [ABSTRACT FROM AUTHOR]

[Display omitted] • Viscosities for Ethyl lactate + Glycols systems were measured. • Excess functions and Thermodynamic parameters of activation for viscous flow of binary mixtures were calculated. • Theoretical modeling of viscosity with various predictive and correlative approaches was done. • The intermolecular interactions in terms of Graph theory and Density functional theory were analysed. Polyethylene glycol and its oligomers are potential hydrogen bond donors that act as a green, effective, non-toxic, non-corrosive and recyclable molecular component for extractive desulfurization of liquid fuels and variety of other applications. The aim of this investigation is to explore the molecular interactions via variations in viscosity that occur on mixing these glycols with green solvent ethyl lactate. Dynamic viscosities (η) for pure solvents and binary mixtures of ethyl lactate and glycols oligomers (mono/di/tri/tetra-ethylene glycol) were measured at varying temperatures T/(K) = (298.15–313.15; with an interval of 5). Viscosity deviations (Δ η) along with excess thermodynamic parameters of activation for viscous flow as Gibbs free energy (Δ G ∗ E) , Enthalpy (Δ H ∗ E) and Entropy (Δ S ∗ E) were derived from experimental data. The Δ η and Δ G ∗ E values were further correlated using Redlich-Kister polynomial expression. The experimentally obtained viscosity values were compared with 10 generalised literature models (Arrhenius, Kendall, Kendall-Monroe, Grunberg-Nissan, Hind, Katti-Chaudhri, Heric, McAllister three-body, McAllister four-body and Jouyban-Acree models). The average standard deviation percentages (ASD %) were calculated for all the models to compare the quality of correlation with experimental data. The minimal ASD % for McAllister four-body and Jouyban-Acree models in the working systems indicate that the multiparameter relations have the best capability of reproducing the experimental values. The temperature induced variations were also discussed together with molecular interactions. Further, quantum mechanical density-functional theory and graph theoretical approaches were used to explore the extent of interactions among the components. [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]

• Contralateral healthy-hemisphere cortical thickness structural connectomes were created from MRI in children undergoing epilepsy surgery. • Higher global efficiency in the contralateral structural connectome was associated with more than 10 points gain in IQ following epilepsy surgery. • Network segregation was similar in those improving more than 10 IQ points following epilepsy surgery and those with no change in IQ. Aims of epilepsy surgery in childhood include optimising seizure control and facilitating cognitive development. Predicting which children will improve cognitively is challenging. We investigated the association of the pre-operative structural connectome of the contralateral non-operated hemisphere with improvement in intelligence quotient (IQ) post-operatively. Consecutive children who had undergone unilateral resective procedures for epilepsy at a single centre were retrospectively identified. We included those with pre-operative volume T1-weighted non-contrast brain magnetic resonance imaging (MRI), no visible contralateral MRI abnormalities, and both pre-operative and two years post-operative IQ assessment. The MRI of the hemisphere contralateral to the side of resection was anatomically parcellated into 34 cortical regions and the covariance of cortical thickness between regions was used to create binary and weighted group connectomes. Eleven patients with a post-operative IQ increase of at least 10 points at two years were compared with twenty-four patients with no change in IQ score. Children who gained at least 10 IQ points post-operatively had a more efficiently structured contralateral hemisphere connectome with higher global efficiency (0.74) compared to those whose IQ did not change at two years (0.58, p = 0.014). This was consistent across thresholds and both binary and weighted networks. There were no statistically significant group differences in age, sex, age at onset of epilepsy, pre-operative IQ, mean cortical thickness, side or site of procedure, two year post-operative Engel scores or use of anti-seizure medications between the two groups. Surgical procedures to reduce or stop seizures may allow children with an efficiently structured contralateral hemisphere to achieve their cognitive potential. [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]

Anthropogenic activities alter the underlying surface conditions and arrangements of landscape features in a drainage basin, interfering with the pollutant (e.g., dissolved nitrogen, phosphorus) transport network configuration and altering the hydrological response. Assessing the impact of anthropogenic activities on hydrological connectivity for natural-artificial catchment is critical to understand the hydrological-driven ecosystem processes, services and biodiversity. However, quantifying this impact at catchment scale remains challenging. In this study, a new framework was proposed to quantify the impact of anthropogenic activities on hydrological connectivity combined with graph theory and network analysis. This framework was exemplified in a natural-artificial catchment of the Yangtze River basin of China. Based on remote sensing and field-investigated data, three transport networks were constructed, including natural transport network (N1), ditch–road transport network (N2), and terrace–dominated transport network (N3), which reflected the different human intervention. The results showed that human intervention improved the connectivity of the nodes and enhanced the complexity of the catchment transport network structure. Anthropogenic activities significantly decreased the hydrological structural connectivity of the catchment. In particular, compared with the N1 network, the critical nodes for hydrological connectivity which were judged by connectivity indexes were reduced by 92.94% and 95.29% in the N2 and N3 network, respectively. Furthermore, the ditch–road construction had a greater impact than terraces in decreasing hydrological structural connectivity at catchment scale. This framework has proven effective in quantifying the hydrological connectivity analysis under different human intervention at the catchment scale and facilitates the improvement of catchment management strategies. • A new framework was proposed to identify catchment hydrological connectivity. • Graph theory combined with network analysis were integrated into the framework. • Three transport networks were constructed to exemplify the framework. • Ditches, roads, and terraces significantly decreased hydrological connectivity. [ABSTRACT FROM AUTHOR]

• Lower structural network global efficiency and higher average path lengths are associated with cognitive impairment in children with epilepsy (CWE). • Higher network-normalised average path lengths and daily seizures are independently associated with cognitive impairment in multivariable analyses. • The intelligence quotient (IQ) correlates with global efficiency and normalised average path lengths from structural connectomes of CWE. Cognitive impairment is common in children with epilepsy (CWE), but understanding the underlying pathological processes is challenging. We aimed to investigate the association of structural brain network organisation with cognition. This was a retrospective cohort study of CWE without structural brain abnormalities, comparing whole brain network characteristics between those with cognitive impairment and those with intact cognition. We created structural whole-brain connectomes from anatomical and diffusion tensor magnetic resonance imaging using the number of streamlines and tract-averaged fractional anisotropy. We assessed the differences in average path length and global network efficiency between children with cognitive impairment and those without,using multivariable analyses to account for possible clinical group differences. Twenty-eight CWE and cognitive impairment had lower whole brain network global efficiency compared with 34 children with intact cognition (0.54, standard deviation (SD):0.003 vs. 0.56, SD:0.002, p < 0.001), which is equivalent to longer normalized network average path lengths (1.14, SD:0.05 vs. 1.10, SD:0.02, p = 0.003). In multivariable logistic regression cognitive impairment was not significantly associated with age of onset, duration of epilepsy, or number of antiseizure medications, but was independently associated with daily seizures (p = 0.04) and normalized average path length (p = 0.007). Higher structural network average path length and lower global network efficiency may be imaging biomarkers of cognitive impairment in epilepsy. Understanding what leads to changes in structural connectivity could aid identification of modifiable risk factors for cognitive impairment. These findings are only applicable to the specific cohort studied, and further confirmation in other cohorts is required. [ABSTRACT FROM AUTHOR]

Traditional methods for the analysis of compositional data consider the log-ratios between all different pairs of variables with equal weight, typically in the form of aggregated contributions. This is not meaningful in contexts where it is known that a relationship only exists between very specific variables (e.g. for metabolomic pathways), while for other pairs a relationship does not exist. Modeling absence or presence of relationships is done in graph theory, where the vertices represent the variables, and the connections refer to relations. This paper links compositional data analysis with graph signal processing, and it extends the Aitchison geometry to a setting where only selected log-ratios can be considered. The presented framework retains the desirable properties of scale invariance and compositional coherence. A real data example from bioinformatics underlines the usefulness of this approach. [ABSTRACT FROM AUTHOR]

A linear configuration is said to be common in an Abelian group G if every 2-coloring of G yields at least the number of monochromatic instances of a randomly chosen coloring. Saad and Wolf asked whether, analogously to a result by Jagger, Šťovíček and Thomason in graph theory, every configuration containing a 4-term arithmetic progression is uncommon. We prove this in F p n for p ≥ 5 and large n and in Z p for large primes p. [ABSTRACT FROM AUTHOR]

We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function f : Z + → Z + , such that for every integer g > 0 , every graph of treewidth at least f (g) contains the (g × g) -grid as a minor. For every integer g > 0 , let f (g) be the smallest value for which the theorem holds. Establishing tight bounds on f (g) is an important graph-theoretic question. Robertson and Seymour showed that f (g) = Ω (g 2 log ⁡ g) must hold. For a long time, the best known upper bounds on f (g) were super-exponential in g. The first polynomial upper bound of f (g) = O (g 98 poly log ⁡ g) was proved by Chekuri and Chuzhoy. It was later improved to f (g) = O (g 36 poly log ⁡ g) , and then to f (g) = O (g 19 poly log ⁡ g). In this paper we further improve this bound to f (g) = O (g 9 poly log ⁡ g). We believe that our proof is significantly simpler than the proofs of the previous bounds. Moreover, while there are natural barriers that seem to prevent previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this paper can lead to even tighter bounds on f (g). [ABSTRACT FROM AUTHOR]