5372255
Holes in Graphs
The celebrated Regularity Lemma of Szemeredi asserts that every sufficiently large graph $G$ can be partitioned in such a way that most pairs of the partition sets span $\epsilon$-regular subgraphs. In applications, however, the graph $G$ has to be dense and the partition sets are typically very small. If only one $\epsilon$-regular pair is needed, a much bigger one can be found, even if the original graph is sparse. In this paper we show that every graph with density $d$ contains a large, relatively dense $\epsilon$-regular pair. We mainly focus on a related concept of an $(\epsilon,\sigma)$-dense pair, for which our bound is, up to a constant, best possible.
17089555
Counting Small Cliques in 3-uniform Hypergraphs
Many applications of Szemeredi's Regularity Lemma for graphs are based on the following counting result. If ${\mathcal G}$ is an $s$-partite graph with partition $V({\mathcal G}) =\bigcup_{i=1}^{s} V_i$, $\vert V_i\vert =m$ for all $i\in [s]$, and all pairs $(V_i, V_j)$, $1\leq i < j\leq s$, are $\epsilon$-regular of density $d$, then $\mathcal{G}$ contains $(1\pm f(\epsilon))d^{({s\atop 2})}m^s$ cliques $K_{s}$, provided $\epsilon<\epsilon(d)$, where $f(\epsilon)$ tends to 0 as $\epsilon$ tends to 0.Guided by the regularity lemma for 3-uniform hypergraphs established earlier by Frankl and Rodl, Nagle and Rodl proved a corresponding counting lemma. Their proof is rather technical, mostly due to the fact that the ‘quasi-random’ hypergraph arising after application of Frankl and Rodl's regularity lemma is ‘sparse’, and consequently difficult to handle.When the ‘quasi-random’ hypergraph is ‘dense’ Kohayakawa, Rodl and Skokan (J. Combin. Theory Ser. A 97 307–352) found a simpler proof of the counting lemma. Their result applies even to $k$-uniform hypergraphs for arbitrary $k$. While the Frankl–Rodl regularity lemma will not render the dense case, in this paper, for $k=3$, we are nevertheless able to reduce the harder, sparse case to the dense case.Namely, we prove that a ‘dense substructure’ randomly chosen from the ‘sparse $\delta$-regular structure’ is $\delta$-regular as well. This allows us to count the number of cliques (and other subhypergraphs) using the Kohayakawa–Rodl–Skokan result, and provides an alternative proof of the counting lemma in the sparse case. Since the counting lemma in the dense case applies to $k$-uniform hypergraphs for arbitrary $k$, there is a possibility that the approach of this paper can be adopted to the general case as well.
2551506
Chromatic Equivalence Classes of Certain Generalized Polygon Trees, II
Let P(G) denote the chromatic polynomial of a graph G. Two graphs G and H are chromatically equivalent, if P(G)=P(H). A set of graphs S is called a chromatic equivalence class if for any graph H that is chromatically equivalent with a graph G in S, then [email protected]?S. Peng et al. (Discrete Math. 172 (1997) 103-114), studied the chromatic equivalence classes of certain generalized polygon trees. In this paper, we continue that study and present a solution to Problem 2 in Koh and Teo (Discrete Math. 172 (1997) 59-78).
15008277
The interoperability problem: bringing together mobile agents and agent communication languages
Interoperability is a central issue far both the mobile agents community and the wider agents community. Unfortunately, the interoperability concerns are different between the two communities. As a result, inter-agent communication is an issue that has been addressed in a limited manner by the mobile agents community. Supplementing mobile agents with the ability to interact a a higher level with other mobile or static agents, or agentified information sources is a necessity in the vastly heterogeneous arena where mobile agents are called to compete. An agent communication language (ACL) has been interpreted by the agents community as a tool with the capacity to integrate disparate sources of information. Such a perspective does not seem to be shared by the mobile agents community. We investigate the origins of the differences of perspective on agent to agent communication and examine the reasons for the relative lack of interest on ACLs by mobile agents researchers and explore the integration of ACLs into mobile agents frameworks.
11039476
On the chromatic uniqueness of certain bipartite graphs
Let K(p, q), p ⩽ q, denote the complete bipartite graph in which the two partite sets consist of p and q vertices, respectively. We denote by K-r(p, q), the family of all graphs obtained by deleting any r distinct edges from K(p, q). Teo and Koh showed that K-1(p, q) is chromatically unique (in short χ-unique) for all p, q such that 3 ⩽ p ⩽ q. In this paper, we obtain a sufficient condition for a graph in K-2(p, q) to be χ-unique. Using this result, we then prove that each graph in K-2(p, p + d) is χ-unique for p ⩾ 4and 0 ⩽ d ⩽ 3. For d ⩾ 4, the graphs in K-2(p, q + d) are χ-unique if p > (A + √B)/4d2, where A and B are polynomials in d. We also show that each graph (≇K(4, 4) – K(1, 3)) in K-3(p, p + d) is χ-unique, for p ⩾ 4 and d=0, 1; and all graphs in K-3(p, p + 2) are χ-unique if and only if all graphs in K-4(p + 1, p + 1) are χ-unique, where p ⩾ 4. Finally we prove that every graph in K-4(p, p + 1) is χ-unique for p ⩾ 5.
33972996
Chromatic equivalence classes of certain cycles with edges
Abstract Let P(G) denote the chromatic polynomial of a graph G . Two graphs G and H are chromatically equivalent, written G∼H , if P(G)=P(H) . A graph G is chromatically unique if for any graph H , G∼H implies that G is isomorphic with H . In this paper, we give the necessary and sufficient conditions for a family of generalized polygon trees to be chromatically unique.
723568
A Bayesian Network Approach to Ontology Mapping
This paper presents our ongoing effort on developing a principled methodology for automatic ontology mapping based on BayesOWL, a probabilistic framework we developed for modeling uncertainty in semantic web. In this approach, the source and target ontologies are first translated into Bayesian networks (BN); the concept mapping between the two ontologies are treated as evidential reasoning between the two translated BNs. Probabilities needed for constructing conditional probability tables (CPT) during translation and for measuring semantic similarity during mapping are learned using text classification techniques where each concept in an ontology is associated with a set of semantically relevant text documents, which are obtained by ontology guided web mining. The basic ideas of this approach are validated by positive results from computer experiments on two small real-world ontologies.