An official website of the United States government
Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $$\Delta $$ , then for every integer $$k \geq \Delta +1$$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $$1$$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $$\Delta $$ , then for each $$k \geq \Delta + 1$$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings are equitable with respect to every G -invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $$\Delta $$ -colourings of graphs with small average degree. Namely, we prove that if $$\Delta \geq 3$$ , G does not contain a clique on $$\Delta + 1$$ vertices and $$\mu $$ is an atomless G -invariant probability measure such that the average degree of G with respect to $$\mu $$ is at most $$\Delta /5$$ , then G has a $$\mu $$ -equitable $$\Delta $$ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.
more »
« less
Node diversification in complex networks by decentralized colouring
Abstract We develop a decentralized colouring approach to diversify the nodes in a complex network. The key is the introduction of a local conflict index (LCI) that measures the colour conflicts arising at each node which can be efficiently computed using only local information. We demonstrate via both synthetic and real-world networks that the proposed approach significantly outperforms random colouring as measured by the size of the largest colour-induced connected component. Interestingly, for scale-free networks further improvement of diversity can be achieved by tuning a degree-biasing weighting parameter in the LCI.
more »
« less
- Award ID(s):
- 1736209
- PAR ID:
- 10117076
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- Journal of Complex Networks
- Volume:
- 7
- Issue:
- 4
- ISSN:
- 2051-1329
- Page Range / eLocation ID:
- p. 554-563
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of Kn? We consider how big a connected component can we guarantee in any r-edge colouring of Kn if we allow ourselves to use up to s colours. This is actually an instance of a more general question of Bollobás from about 20 years ago which asks for a k-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided n is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form. We also consider a generalisation in a similar direction of a question first considered by Erdős and Rényi in 1956, who considered given n and m, what is the smallest number of m-cliques which can cover all edges of Kn? This problem is essentially equivalent to the question of what is the minimum number of vertices that are certain to be incident to at least one edge of some colour in any r-edge colouring of Kn. We consider what happens if we allow ourselves to use up to s colours. We obtain a more complete understanding of the answer to this question for large n, in particular determining it up to a constant factor for all 1≤s≤r, as well as obtaining much more precise results for various ranges including the correct asymptotics for essentially the whole range.more » « less
-
Abstract Extending a result of Christiansen, we prove that every multigraph admits a proper edge colouring which islocal, that is, for every edge with end‐points , where (resp. ) denotes the degree of a vertex (resp. the maximum edge multiplicity at ). This is derived from a local version of the Fan Equation.more » « less
-
Abstract Animal signals evolve in an ecological context. Locally adapting animal sexual signals can be especially important for initiating or reinforcing reproductive isolation during the early stages of speciation. Previous studies have demonstrated that dewlap colour inAnolislizards can be highly variable between populations in relation to both biotic and abiotic adaptive drivers at relatively large geographical scales. Here, we investigated differentiation of dewlap colouration among habitat types at a small spatial scale, within multiple islands of the West Indies, to test the hypothesis that similar local adaptive processes occur over smaller spatial scales. We explored variation in dewlap colouration in the most widespread species of anole,Anolis sagrei, across three characteristic habitats spanning the Bahamas and the Cayman Islands, namely beach scrub, primary coppice forest and mangrove forest. Using reflectance spectrometry paired with supervised machine learning, we found significant differences in spectral properties of the dewlap between habitats within small islands, sometimes over very short distances. Passive divergence in dewlap phenotype associated with isolation‐by‐distance did not seem to explain our results. On the other hand, these habitat‐specific dewlap differences varied in magnitude and direction across islands, and thus, our primary test for adaptation—parallel responses across islands—was not supported. We suggest that neutral processes or selection could be involved in several ways, including sexual selection. Our results shed new light on the scale at which signal colour polymorphism can be maintained in the presence of gene flow, and the relative role of local adaptation and other processes in driving these patterns of dewlap colour variation across islands.more » « less
-
We present a machine learning method for detecting and staging cervical dysplastic tissue using light scattering data based on a convolutional neural network (CNN) architecture. Depth-resolved angular scattering measurements from two clinical trials were used to generate independent training and validation sets as input of our model. We report 90.3% sensitivity, 85.7% specificity, and 87.5% accuracy in classifying cervical dysplasia, showing the uniformity of classification of a/LCI scans across different instruments. Further, our deep learning approach significantly improved processing speeds over the traditional Mie theory inverse light scattering analysis (ILSA) method, with a hundredfold reduction in processing time, offering a promising approach for a/LCI in the clinic for assessing cervical dysplasia.more » « less
